1 /* Instruction scheduling pass. Selective scheduler and pipeliner.
2 Copyright (C) 2006-2015 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
27 #include "diagnostic-core.h"
34 #include "insn-config.h"
35 #include "insn-attr.h"
40 #include "sched-int.h"
41 #include "langhooks.h"
42 #include "rtlhooks-def.h"
43 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
45 #ifdef INSN_SCHEDULING
48 #include "sel-sched-ir.h"
49 /* We don't have to use it except for sel_print_insn. */
50 #include "sel-sched-dump.h"
52 /* A vector holding bb info for whole scheduling pass. */
53 vec
<sel_global_bb_info_def
>
54 sel_global_bb_info
= vNULL
;
56 /* A vector holding bb info. */
57 vec
<sel_region_bb_info_def
>
58 sel_region_bb_info
= vNULL
;
60 /* A pool for allocating all lists. */
61 pool_allocator
<_list_node
> sched_lists_pool ("sel-sched-lists", 500);
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
> loop_nests
= vNULL
;
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 vec
<rtx_note
*> 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_insn
*exit_insn
= NULL
;
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
> &);
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);
159 static bool bb_has_removable_jump_to_p (basic_block
, basic_block
);
161 static bool insn_is_the_only_one_in_bb_p (insn_t
);
162 static void create_initial_data_sets (basic_block
);
164 static void free_av_set (basic_block
);
165 static void invalidate_av_set (basic_block
);
166 static void extend_insn_data (void);
167 static void sel_init_new_insn (insn_t
, int, int = -1);
168 static void finish_insns (void);
170 /* Various list functions. */
172 /* Copy an instruction list L. */
174 ilist_copy (ilist_t l
)
176 ilist_t head
= NULL
, *tailp
= &head
;
180 ilist_add (tailp
, ILIST_INSN (l
));
181 tailp
= &ILIST_NEXT (*tailp
);
188 /* Invert an instruction list L. */
190 ilist_invert (ilist_t l
)
196 ilist_add (&res
, ILIST_INSN (l
));
203 /* Add a new boundary to the LP list with parameters TO, PTR, and DC. */
205 blist_add (blist_t
*lp
, insn_t to
, ilist_t ptr
, deps_t dc
)
210 bnd
= BLIST_BND (*lp
);
215 BND_AV1 (bnd
) = NULL
;
219 /* Remove the list note pointed to by LP. */
221 blist_remove (blist_t
*lp
)
223 bnd_t b
= BLIST_BND (*lp
);
225 av_set_clear (&BND_AV (b
));
226 av_set_clear (&BND_AV1 (b
));
227 ilist_clear (&BND_PTR (b
));
232 /* Init a fence tail L. */
234 flist_tail_init (flist_tail_t l
)
236 FLIST_TAIL_HEAD (l
) = NULL
;
237 FLIST_TAIL_TAILP (l
) = &FLIST_TAIL_HEAD (l
);
240 /* Try to find fence corresponding to INSN in L. */
242 flist_lookup (flist_t l
, insn_t insn
)
246 if (FENCE_INSN (FLIST_FENCE (l
)) == insn
)
247 return FLIST_FENCE (l
);
255 /* Init the fields of F before running fill_insns. */
257 init_fence_for_scheduling (fence_t f
)
259 FENCE_BNDS (f
) = NULL
;
260 FENCE_PROCESSED_P (f
) = false;
261 FENCE_SCHEDULED_P (f
) = false;
264 /* Add new fence consisting of INSN and STATE to the list pointed to by LP. */
266 flist_add (flist_t
*lp
, insn_t insn
, state_t state
, deps_t dc
, void *tc
,
267 insn_t last_scheduled_insn
, vec
<rtx_insn
*, va_gc
> *executing_insns
,
268 int *ready_ticks
, int ready_ticks_size
, insn_t sched_next
,
269 int cycle
, int cycle_issued_insns
, int issue_more
,
270 bool starts_cycle_p
, bool after_stall_p
)
275 f
= FLIST_FENCE (*lp
);
277 FENCE_INSN (f
) = insn
;
279 gcc_assert (state
!= NULL
);
280 FENCE_STATE (f
) = state
;
282 FENCE_CYCLE (f
) = cycle
;
283 FENCE_ISSUED_INSNS (f
) = cycle_issued_insns
;
284 FENCE_STARTS_CYCLE_P (f
) = starts_cycle_p
;
285 FENCE_AFTER_STALL_P (f
) = after_stall_p
;
287 gcc_assert (dc
!= NULL
);
290 gcc_assert (tc
!= NULL
|| targetm
.sched
.alloc_sched_context
== NULL
);
293 FENCE_LAST_SCHEDULED_INSN (f
) = last_scheduled_insn
;
294 FENCE_ISSUE_MORE (f
) = issue_more
;
295 FENCE_EXECUTING_INSNS (f
) = executing_insns
;
296 FENCE_READY_TICKS (f
) = ready_ticks
;
297 FENCE_READY_TICKS_SIZE (f
) = ready_ticks_size
;
298 FENCE_SCHED_NEXT (f
) = sched_next
;
300 init_fence_for_scheduling (f
);
303 /* Remove the head node of the list pointed to by LP. */
305 flist_remove (flist_t
*lp
)
307 if (FENCE_INSN (FLIST_FENCE (*lp
)))
308 fence_clear (FLIST_FENCE (*lp
));
312 /* Clear the fence list pointed to by LP. */
314 flist_clear (flist_t
*lp
)
320 /* Add ORIGINAL_INSN the def list DL honoring CROSSES_CALL. */
322 def_list_add (def_list_t
*dl
, insn_t original_insn
, bool crosses_call
)
327 d
= DEF_LIST_DEF (*dl
);
329 d
->orig_insn
= original_insn
;
330 d
->crosses_call
= crosses_call
;
334 /* Functions to work with target contexts. */
336 /* Bulk target context. It is convenient for debugging purposes to ensure
337 that there are no uninitialized (null) target contexts. */
338 static tc_t bulk_tc
= (tc_t
) 1;
340 /* Target hooks wrappers. In the future we can provide some default
341 implementations for them. */
343 /* Allocate a store for the target context. */
345 alloc_target_context (void)
347 return (targetm
.sched
.alloc_sched_context
348 ? targetm
.sched
.alloc_sched_context () : bulk_tc
);
351 /* Init target context TC.
352 If CLEAN_P is true, then make TC as it is beginning of the scheduler.
353 Overwise, copy current backend context to TC. */
355 init_target_context (tc_t tc
, bool clean_p
)
357 if (targetm
.sched
.init_sched_context
)
358 targetm
.sched
.init_sched_context (tc
, clean_p
);
361 /* Allocate and initialize a target context. Meaning of CLEAN_P is the same as
362 int init_target_context (). */
364 create_target_context (bool clean_p
)
366 tc_t tc
= alloc_target_context ();
368 init_target_context (tc
, clean_p
);
372 /* Copy TC to the current backend context. */
374 set_target_context (tc_t tc
)
376 if (targetm
.sched
.set_sched_context
)
377 targetm
.sched
.set_sched_context (tc
);
380 /* TC is about to be destroyed. Free any internal data. */
382 clear_target_context (tc_t tc
)
384 if (targetm
.sched
.clear_sched_context
)
385 targetm
.sched
.clear_sched_context (tc
);
388 /* Clear and free it. */
390 delete_target_context (tc_t tc
)
392 clear_target_context (tc
);
394 if (targetm
.sched
.free_sched_context
)
395 targetm
.sched
.free_sched_context (tc
);
398 /* Make a copy of FROM in TO.
399 NB: May be this should be a hook. */
401 copy_target_context (tc_t to
, tc_t from
)
403 tc_t tmp
= create_target_context (false);
405 set_target_context (from
);
406 init_target_context (to
, false);
408 set_target_context (tmp
);
409 delete_target_context (tmp
);
412 /* Create a copy of TC. */
414 create_copy_of_target_context (tc_t tc
)
416 tc_t copy
= alloc_target_context ();
418 copy_target_context (copy
, tc
);
423 /* Clear TC and initialize it according to CLEAN_P. The meaning of CLEAN_P
424 is the same as in init_target_context (). */
426 reset_target_context (tc_t tc
, bool clean_p
)
428 clear_target_context (tc
);
429 init_target_context (tc
, clean_p
);
432 /* Functions to work with dependence contexts.
433 Dc (aka deps context, aka deps_t, aka struct deps_desc *) is short for dependence
434 context. It accumulates information about processed insns to decide if
435 current insn is dependent on the processed ones. */
437 /* Make a copy of FROM in TO. */
439 copy_deps_context (deps_t to
, deps_t from
)
441 init_deps (to
, false);
442 deps_join (to
, from
);
445 /* Allocate store for dep context. */
447 alloc_deps_context (void)
449 return XNEW (struct deps_desc
);
452 /* Allocate and initialize dep context. */
454 create_deps_context (void)
456 deps_t dc
= alloc_deps_context ();
458 init_deps (dc
, false);
462 /* Create a copy of FROM. */
464 create_copy_of_deps_context (deps_t from
)
466 deps_t to
= alloc_deps_context ();
468 copy_deps_context (to
, from
);
472 /* Clean up internal data of DC. */
474 clear_deps_context (deps_t dc
)
479 /* Clear and free DC. */
481 delete_deps_context (deps_t dc
)
483 clear_deps_context (dc
);
487 /* Clear and init DC. */
489 reset_deps_context (deps_t dc
)
491 clear_deps_context (dc
);
492 init_deps (dc
, false);
495 /* This structure describes the dependence analysis hooks for advancing
496 dependence context. */
497 static struct sched_deps_info_def advance_deps_context_sched_deps_info
=
501 NULL
, /* start_insn */
502 NULL
, /* finish_insn */
503 NULL
, /* start_lhs */
504 NULL
, /* finish_lhs */
505 NULL
, /* start_rhs */
506 NULL
, /* finish_rhs */
508 haifa_note_reg_clobber
,
510 NULL
, /* note_mem_dep */
516 /* Process INSN and add its impact on DC. */
518 advance_deps_context (deps_t dc
, insn_t insn
)
520 sched_deps_info
= &advance_deps_context_sched_deps_info
;
521 deps_analyze_insn (dc
, insn
);
525 /* Functions to work with DFA states. */
527 /* Allocate store for a DFA state. */
531 return xmalloc (dfa_state_size
);
534 /* Allocate and initialize DFA state. */
538 state_t state
= state_alloc ();
541 advance_state (state
);
545 /* Free DFA state. */
547 state_free (state_t state
)
552 /* Make a copy of FROM in TO. */
554 state_copy (state_t to
, state_t from
)
556 memcpy (to
, from
, dfa_state_size
);
559 /* Create a copy of FROM. */
561 state_create_copy (state_t from
)
563 state_t to
= state_alloc ();
565 state_copy (to
, from
);
570 /* Functions to work with fences. */
572 /* Clear the fence. */
574 fence_clear (fence_t f
)
576 state_t s
= FENCE_STATE (f
);
577 deps_t dc
= FENCE_DC (f
);
578 void *tc
= FENCE_TC (f
);
580 ilist_clear (&FENCE_BNDS (f
));
582 gcc_assert ((s
!= NULL
&& dc
!= NULL
&& tc
!= NULL
)
583 || (s
== NULL
&& dc
== NULL
&& tc
== NULL
));
588 delete_deps_context (dc
);
591 delete_target_context (tc
);
592 vec_free (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
/* last_scheduled_insn */,
620 NULL
, /* executing_insns */
621 XCNEWVEC (int, ready_ticks_size
), /* ready_ticks */
623 NULL
/* 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_insn
*last_scheduled_insn
,
643 vec
<rtx_insn
*, va_gc
> *executing_insns
,
644 int *ready_ticks
, int ready_ticks_size
,
645 rtx sched_next
, int cycle
, int issue_more
, bool after_stall_p
)
647 insn_t last_scheduled_insn_old
= FENCE_LAST_SCHEDULED_INSN (f
);
649 gcc_assert (sel_bb_head_p (FENCE_INSN (f
))
650 && !sched_next
&& !FENCE_SCHED_NEXT (f
));
652 /* Check if we can decide which path fences came.
653 If we can't (or don't want to) - reset all. */
654 if (last_scheduled_insn
== NULL
655 || last_scheduled_insn_old
== NULL
656 /* This is a case when INSN is reachable on several paths from
657 one insn (this can happen when pipelining of outer loops is on and
658 there are two edges: one going around of inner loop and the other -
659 right through it; in such case just reset everything). */
660 || last_scheduled_insn
== last_scheduled_insn_old
)
662 state_reset (FENCE_STATE (f
));
665 reset_deps_context (FENCE_DC (f
));
666 delete_deps_context (dc
);
668 reset_target_context (FENCE_TC (f
), true);
669 delete_target_context (tc
);
671 if (cycle
> FENCE_CYCLE (f
))
672 FENCE_CYCLE (f
) = cycle
;
674 FENCE_LAST_SCHEDULED_INSN (f
) = NULL
;
675 FENCE_ISSUE_MORE (f
) = issue_rate
;
676 vec_free (executing_insns
);
678 if (FENCE_EXECUTING_INSNS (f
))
679 FENCE_EXECUTING_INSNS (f
)->block_remove (0,
680 FENCE_EXECUTING_INSNS (f
)->length ());
681 if (FENCE_READY_TICKS (f
))
682 memset (FENCE_READY_TICKS (f
), 0, FENCE_READY_TICKS_SIZE (f
));
686 edge edge_old
= NULL
, edge_new
= NULL
;
691 /* Find fallthrough edge. */
692 gcc_assert (BLOCK_FOR_INSN (insn
)->prev_bb
);
693 candidate
= find_fallthru_edge_from (BLOCK_FOR_INSN (insn
)->prev_bb
);
696 || (candidate
->src
!= BLOCK_FOR_INSN (last_scheduled_insn
)
697 && candidate
->src
!= BLOCK_FOR_INSN (last_scheduled_insn_old
)))
699 /* No fallthrough edge leading to basic block of INSN. */
700 state_reset (FENCE_STATE (f
));
703 reset_target_context (FENCE_TC (f
), true);
704 delete_target_context (tc
);
706 FENCE_LAST_SCHEDULED_INSN (f
) = NULL
;
707 FENCE_ISSUE_MORE (f
) = issue_rate
;
710 if (candidate
->src
== BLOCK_FOR_INSN (last_scheduled_insn
))
712 /* Would be weird if same insn is successor of several fallthrough
714 gcc_assert (BLOCK_FOR_INSN (insn
)->prev_bb
715 != BLOCK_FOR_INSN (last_scheduled_insn_old
));
717 state_free (FENCE_STATE (f
));
718 FENCE_STATE (f
) = state
;
720 delete_target_context (FENCE_TC (f
));
723 FENCE_LAST_SCHEDULED_INSN (f
) = last_scheduled_insn
;
724 FENCE_ISSUE_MORE (f
) = issue_more
;
728 /* Leave STATE, TC and LAST_SCHEDULED_INSN fields untouched. */
730 delete_target_context (tc
);
732 gcc_assert (BLOCK_FOR_INSN (insn
)->prev_bb
733 != BLOCK_FOR_INSN (last_scheduled_insn
));
736 /* Find edge of first predecessor (last_scheduled_insn_old->insn). */
737 FOR_EACH_SUCC_1 (succ
, si
, last_scheduled_insn_old
,
738 SUCCS_NORMAL
| SUCCS_SKIP_TO_LOOP_EXITS
)
742 /* No same successor allowed from several edges. */
743 gcc_assert (!edge_old
);
747 /* Find edge of second predecessor (last_scheduled_insn->insn). */
748 FOR_EACH_SUCC_1 (succ
, si
, last_scheduled_insn
,
749 SUCCS_NORMAL
| SUCCS_SKIP_TO_LOOP_EXITS
)
753 /* No same successor allowed from several edges. */
754 gcc_assert (!edge_new
);
759 /* Check if we can choose most probable predecessor. */
760 if (edge_old
== NULL
|| edge_new
== NULL
)
762 reset_deps_context (FENCE_DC (f
));
763 delete_deps_context (dc
);
764 vec_free (executing_insns
);
767 FENCE_CYCLE (f
) = MAX (FENCE_CYCLE (f
), cycle
);
768 if (FENCE_EXECUTING_INSNS (f
))
769 FENCE_EXECUTING_INSNS (f
)->block_remove (0,
770 FENCE_EXECUTING_INSNS (f
)->length ());
771 if (FENCE_READY_TICKS (f
))
772 memset (FENCE_READY_TICKS (f
), 0, FENCE_READY_TICKS_SIZE (f
));
775 if (edge_new
->probability
> edge_old
->probability
)
777 delete_deps_context (FENCE_DC (f
));
779 vec_free (FENCE_EXECUTING_INSNS (f
));
780 FENCE_EXECUTING_INSNS (f
) = executing_insns
;
781 free (FENCE_READY_TICKS (f
));
782 FENCE_READY_TICKS (f
) = ready_ticks
;
783 FENCE_READY_TICKS_SIZE (f
) = ready_ticks_size
;
784 FENCE_CYCLE (f
) = cycle
;
788 /* Leave DC and CYCLE untouched. */
789 delete_deps_context (dc
);
790 vec_free (executing_insns
);
795 /* Fill remaining invariant fields. */
797 FENCE_AFTER_STALL_P (f
) = 1;
799 FENCE_ISSUED_INSNS (f
) = 0;
800 FENCE_STARTS_CYCLE_P (f
) = 1;
801 FENCE_SCHED_NEXT (f
) = NULL
;
804 /* Add a new fence to NEW_FENCES list, initializing it from all
807 add_to_fences (flist_tail_t new_fences
, insn_t insn
,
808 state_t state
, deps_t dc
, void *tc
,
809 rtx_insn
*last_scheduled_insn
,
810 vec
<rtx_insn
*, va_gc
> *executing_insns
, int *ready_ticks
,
811 int ready_ticks_size
, rtx_insn
*sched_next
, int cycle
,
812 int cycle_issued_insns
, int issue_rate
,
813 bool starts_cycle_p
, bool after_stall_p
)
815 fence_t f
= flist_lookup (FLIST_TAIL_HEAD (new_fences
), insn
);
819 flist_add (FLIST_TAIL_TAILP (new_fences
), insn
, state
, dc
, tc
,
820 last_scheduled_insn
, executing_insns
, ready_ticks
,
821 ready_ticks_size
, sched_next
, cycle
, cycle_issued_insns
,
822 issue_rate
, starts_cycle_p
, after_stall_p
);
824 FLIST_TAIL_TAILP (new_fences
)
825 = &FLIST_NEXT (*FLIST_TAIL_TAILP (new_fences
));
829 merge_fences (f
, insn
, state
, dc
, tc
, last_scheduled_insn
,
830 executing_insns
, ready_ticks
, ready_ticks_size
,
831 sched_next
, cycle
, issue_rate
, after_stall_p
);
835 /* Move the first fence in the OLD_FENCES list to NEW_FENCES. */
837 move_fence_to_fences (flist_t old_fences
, flist_tail_t new_fences
)
840 flist_t
*tailp
= FLIST_TAIL_TAILP (new_fences
);
842 old
= FLIST_FENCE (old_fences
);
843 f
= flist_lookup (FLIST_TAIL_HEAD (new_fences
),
844 FENCE_INSN (FLIST_FENCE (old_fences
)));
847 merge_fences (f
, old
->insn
, old
->state
, old
->dc
, old
->tc
,
848 old
->last_scheduled_insn
, old
->executing_insns
,
849 old
->ready_ticks
, old
->ready_ticks_size
,
850 old
->sched_next
, old
->cycle
, old
->issue_more
,
856 FLIST_TAIL_TAILP (new_fences
) = &FLIST_NEXT (*tailp
);
857 *FLIST_FENCE (*tailp
) = *old
;
858 init_fence_for_scheduling (FLIST_FENCE (*tailp
));
860 FENCE_INSN (old
) = NULL
;
863 /* Add a new fence to NEW_FENCES list and initialize most of its data
866 add_clean_fence_to_fences (flist_tail_t new_fences
, insn_t succ
, fence_t fence
)
868 int ready_ticks_size
= get_max_uid () + 1;
870 add_to_fences (new_fences
,
871 succ
, state_create (), create_deps_context (),
872 create_target_context (true),
874 XCNEWVEC (int, ready_ticks_size
), ready_ticks_size
,
875 NULL
, FENCE_CYCLE (fence
) + 1,
876 0, issue_rate
, 1, FENCE_AFTER_STALL_P (fence
));
879 /* Add a new fence to NEW_FENCES list and initialize all of its data
880 from FENCE and SUCC. */
882 add_dirty_fence_to_fences (flist_tail_t new_fences
, insn_t succ
, fence_t fence
)
884 int * new_ready_ticks
885 = XNEWVEC (int, FENCE_READY_TICKS_SIZE (fence
));
887 memcpy (new_ready_ticks
, FENCE_READY_TICKS (fence
),
888 FENCE_READY_TICKS_SIZE (fence
) * sizeof (int));
889 add_to_fences (new_fences
,
890 succ
, state_create_copy (FENCE_STATE (fence
)),
891 create_copy_of_deps_context (FENCE_DC (fence
)),
892 create_copy_of_target_context (FENCE_TC (fence
)),
893 FENCE_LAST_SCHEDULED_INSN (fence
),
894 vec_safe_copy (FENCE_EXECUTING_INSNS (fence
)),
896 FENCE_READY_TICKS_SIZE (fence
),
897 FENCE_SCHED_NEXT (fence
),
899 FENCE_ISSUED_INSNS (fence
),
900 FENCE_ISSUE_MORE (fence
),
901 FENCE_STARTS_CYCLE_P (fence
),
902 FENCE_AFTER_STALL_P (fence
));
906 /* Functions to work with regset and nop pools. */
908 /* Returns the new regset from pool. It might have some of the bits set
909 from the previous usage. */
911 get_regset_from_pool (void)
915 if (regset_pool
.n
!= 0)
916 rs
= regset_pool
.v
[--regset_pool
.n
];
918 /* We need to create the regset. */
920 rs
= ALLOC_REG_SET (®_obstack
);
922 if (regset_pool
.nn
== regset_pool
.ss
)
923 regset_pool
.vv
= XRESIZEVEC (regset
, regset_pool
.vv
,
924 (regset_pool
.ss
= 2 * regset_pool
.ss
+ 1));
925 regset_pool
.vv
[regset_pool
.nn
++] = rs
;
933 /* Same as above, but returns the empty regset. */
935 get_clear_regset_from_pool (void)
937 regset rs
= get_regset_from_pool ();
943 /* Return regset RS to the pool for future use. */
945 return_regset_to_pool (regset rs
)
950 if (regset_pool
.n
== regset_pool
.s
)
951 regset_pool
.v
= XRESIZEVEC (regset
, regset_pool
.v
,
952 (regset_pool
.s
= 2 * regset_pool
.s
+ 1));
953 regset_pool
.v
[regset_pool
.n
++] = rs
;
956 #ifdef ENABLE_CHECKING
957 /* This is used as a qsort callback for sorting regset pool stacks.
958 X and XX are addresses of two regsets. They are never equal. */
960 cmp_v_in_regset_pool (const void *x
, const void *xx
)
962 uintptr_t r1
= (uintptr_t) *((const regset
*) x
);
963 uintptr_t r2
= (uintptr_t) *((const regset
*) xx
);
972 /* Free the regset pool possibly checking for memory leaks. */
974 free_regset_pool (void)
976 #ifdef ENABLE_CHECKING
978 regset
*v
= regset_pool
.v
;
980 int n
= regset_pool
.n
;
982 regset
*vv
= regset_pool
.vv
;
984 int nn
= regset_pool
.nn
;
988 gcc_assert (n
<= nn
);
990 /* Sort both vectors so it will be possible to compare them. */
991 qsort (v
, n
, sizeof (*v
), cmp_v_in_regset_pool
);
992 qsort (vv
, nn
, sizeof (*vv
), cmp_v_in_regset_pool
);
999 /* VV[II] was lost. */
1005 gcc_assert (diff
== regset_pool
.diff
);
1009 /* If not true - we have a memory leak. */
1010 gcc_assert (regset_pool
.diff
== 0);
1012 while (regset_pool
.n
)
1015 FREE_REG_SET (regset_pool
.v
[regset_pool
.n
]);
1018 free (regset_pool
.v
);
1019 regset_pool
.v
= NULL
;
1022 free (regset_pool
.vv
);
1023 regset_pool
.vv
= NULL
;
1027 regset_pool
.diff
= 0;
1031 /* Functions to work with nop pools. NOP insns are used as temporary
1032 placeholders of the insns being scheduled to allow correct update of
1033 the data sets. When update is finished, NOPs are deleted. */
1035 /* A vinsn that is used to represent a nop. This vinsn is shared among all
1036 nops sel-sched generates. */
1037 static vinsn_t nop_vinsn
= NULL
;
1039 /* Emit a nop before INSN, taking it from pool. */
1041 get_nop_from_pool (insn_t insn
)
1045 bool old_p
= nop_pool
.n
!= 0;
1049 nop_pat
= nop_pool
.v
[--nop_pool
.n
];
1051 nop_pat
= nop_pattern
;
1053 nop
= emit_insn_before (nop_pat
, insn
);
1056 flags
= INSN_INIT_TODO_SSID
;
1058 flags
= INSN_INIT_TODO_LUID
| INSN_INIT_TODO_SSID
;
1060 set_insn_init (INSN_EXPR (insn
), nop_vinsn
, INSN_SEQNO (insn
));
1061 sel_init_new_insn (nop
, flags
);
1066 /* Remove NOP from the instruction stream and return it to the pool. */
1068 return_nop_to_pool (insn_t nop
, bool full_tidying
)
1070 gcc_assert (INSN_IN_STREAM_P (nop
));
1071 sel_remove_insn (nop
, false, full_tidying
);
1073 /* We'll recycle this nop. */
1074 nop
->set_undeleted ();
1076 if (nop_pool
.n
== nop_pool
.s
)
1077 nop_pool
.v
= XRESIZEVEC (rtx_insn
*, nop_pool
.v
,
1078 (nop_pool
.s
= 2 * nop_pool
.s
+ 1));
1079 nop_pool
.v
[nop_pool
.n
++] = nop
;
1082 /* Free the nop pool. */
1084 free_nop_pool (void)
1093 /* Skip unspec to support ia64 speculation. Called from rtx_equal_p_cb.
1094 The callback is given two rtxes XX and YY and writes the new rtxes
1095 to NX and NY in case some needs to be skipped. */
1097 skip_unspecs_callback (const_rtx
*xx
, const_rtx
*yy
, rtx
*nx
, rtx
* ny
)
1102 if (GET_CODE (x
) == UNSPEC
1103 && (targetm
.sched
.skip_rtx_p
== NULL
1104 || targetm
.sched
.skip_rtx_p (x
)))
1106 *nx
= XVECEXP (x
, 0, 0);
1107 *ny
= CONST_CAST_RTX (y
);
1111 if (GET_CODE (y
) == UNSPEC
1112 && (targetm
.sched
.skip_rtx_p
== NULL
1113 || targetm
.sched
.skip_rtx_p (y
)))
1115 *nx
= CONST_CAST_RTX (x
);
1116 *ny
= XVECEXP (y
, 0, 0);
1123 /* Callback, called from hash_rtx_cb. Helps to hash UNSPEC rtx X in a correct way
1124 to support ia64 speculation. When changes are needed, new rtx X and new mode
1125 NMODE are written, and the callback returns true. */
1127 hash_with_unspec_callback (const_rtx x
, machine_mode mode ATTRIBUTE_UNUSED
,
1128 rtx
*nx
, machine_mode
* nmode
)
1130 if (GET_CODE (x
) == UNSPEC
1131 && targetm
.sched
.skip_rtx_p
1132 && targetm
.sched
.skip_rtx_p (x
))
1134 *nx
= XVECEXP (x
, 0 ,0);
1142 /* Returns LHS and RHS are ok to be scheduled separately. */
1144 lhs_and_rhs_separable_p (rtx lhs
, rtx rhs
)
1146 if (lhs
== NULL
|| rhs
== NULL
)
1149 /* Do not schedule constants as rhs: no point to use reg, if const
1150 can be used. Moreover, scheduling const as rhs may lead to mode
1151 mismatch cause consts don't have modes but they could be merged
1152 from branches where the same const used in different modes. */
1153 if (CONSTANT_P (rhs
))
1156 /* ??? Do not rename predicate registers to avoid ICEs in bundling. */
1157 if (COMPARISON_P (rhs
))
1160 /* Do not allow single REG to be an rhs. */
1164 /* See comment at find_used_regs_1 (*1) for explanation of this
1166 /* FIXME: remove this later. */
1170 /* This will filter all tricky things like ZERO_EXTRACT etc.
1171 For now we don't handle it. */
1172 if (!REG_P (lhs
) && !MEM_P (lhs
))
1178 /* Initialize vinsn VI for INSN. Only for use from vinsn_create (). When
1179 FORCE_UNIQUE_P is true, the resulting vinsn will not be clonable. This is
1180 used e.g. for insns from recovery blocks. */
1182 vinsn_init (vinsn_t vi
, insn_t insn
, bool force_unique_p
)
1184 hash_rtx_callback_function hrcf
;
1187 VINSN_INSN_RTX (vi
) = insn
;
1188 VINSN_COUNT (vi
) = 0;
1191 if (INSN_NOP_P (insn
))
1194 if (DF_INSN_UID_SAFE_GET (INSN_UID (insn
)) != NULL
)
1195 init_id_from_df (VINSN_ID (vi
), insn
, force_unique_p
);
1197 deps_init_id (VINSN_ID (vi
), insn
, force_unique_p
);
1199 /* Hash vinsn depending on whether it is separable or not. */
1200 hrcf
= targetm
.sched
.skip_rtx_p
? hash_with_unspec_callback
: NULL
;
1201 if (VINSN_SEPARABLE_P (vi
))
1203 rtx rhs
= VINSN_RHS (vi
);
1205 VINSN_HASH (vi
) = hash_rtx_cb (rhs
, GET_MODE (rhs
),
1206 NULL
, NULL
, false, hrcf
);
1207 VINSN_HASH_RTX (vi
) = hash_rtx_cb (VINSN_PATTERN (vi
),
1208 VOIDmode
, NULL
, NULL
,
1213 VINSN_HASH (vi
) = hash_rtx_cb (VINSN_PATTERN (vi
), VOIDmode
,
1214 NULL
, NULL
, false, hrcf
);
1215 VINSN_HASH_RTX (vi
) = VINSN_HASH (vi
);
1218 insn_class
= haifa_classify_insn (insn
);
1220 && (!targetm
.sched
.get_insn_spec_ds
1221 || ((targetm
.sched
.get_insn_spec_ds (insn
) & BEGIN_CONTROL
)
1223 VINSN_MAY_TRAP_P (vi
) = true;
1225 VINSN_MAY_TRAP_P (vi
) = false;
1228 /* Indicate that VI has become the part of an rtx object. */
1230 vinsn_attach (vinsn_t vi
)
1232 /* Assert that VI is not pending for deletion. */
1233 gcc_assert (VINSN_INSN_RTX (vi
));
1238 /* Create and init VI from the INSN. Use UNIQUE_P for determining the correct
1241 vinsn_create (insn_t insn
, bool force_unique_p
)
1243 vinsn_t vi
= XCNEW (struct vinsn_def
);
1245 vinsn_init (vi
, insn
, force_unique_p
);
1249 /* Return a copy of VI. When REATTACH_P is true, detach VI and attach
1252 vinsn_copy (vinsn_t vi
, bool reattach_p
)
1255 bool unique
= VINSN_UNIQUE_P (vi
);
1258 copy
= create_copy_of_insn_rtx (VINSN_INSN_RTX (vi
));
1259 new_vi
= create_vinsn_from_insn_rtx (copy
, unique
);
1263 vinsn_attach (new_vi
);
1269 /* Delete the VI vinsn and free its data. */
1271 vinsn_delete (vinsn_t vi
)
1273 gcc_assert (VINSN_COUNT (vi
) == 0);
1275 if (!INSN_NOP_P (VINSN_INSN_RTX (vi
)))
1277 return_regset_to_pool (VINSN_REG_SETS (vi
));
1278 return_regset_to_pool (VINSN_REG_USES (vi
));
1279 return_regset_to_pool (VINSN_REG_CLOBBERS (vi
));
1285 /* Indicate that VI is no longer a part of some rtx object.
1286 Remove VI if it is no longer needed. */
1288 vinsn_detach (vinsn_t vi
)
1290 gcc_assert (VINSN_COUNT (vi
) > 0);
1292 if (--VINSN_COUNT (vi
) == 0)
1296 /* Returns TRUE if VI is a branch. */
1298 vinsn_cond_branch_p (vinsn_t vi
)
1302 if (!VINSN_UNIQUE_P (vi
))
1305 insn
= VINSN_INSN_RTX (vi
);
1306 if (BB_END (BLOCK_FOR_INSN (insn
)) != insn
)
1309 return control_flow_insn_p (insn
);
1312 /* Return latency of INSN. */
1314 sel_insn_rtx_cost (rtx_insn
*insn
)
1318 /* A USE insn, or something else we don't need to
1319 understand. We can't pass these directly to
1320 result_ready_cost or insn_default_latency because it will
1321 trigger a fatal error for unrecognizable insns. */
1322 if (recog_memoized (insn
) < 0)
1326 cost
= insn_default_latency (insn
);
1335 /* Return the cost of the VI.
1336 !!! FIXME: Unify with haifa-sched.c: insn_cost (). */
1338 sel_vinsn_cost (vinsn_t vi
)
1340 int cost
= vi
->cost
;
1344 cost
= sel_insn_rtx_cost (VINSN_INSN_RTX (vi
));
1352 /* Functions for insn emitting. */
1354 /* Emit new insn after AFTER based on PATTERN and initialize its data from
1357 sel_gen_insn_from_rtx_after (rtx pattern
, expr_t expr
, int seqno
, insn_t after
)
1361 gcc_assert (EXPR_TARGET_AVAILABLE (expr
) == true);
1363 new_insn
= emit_insn_after (pattern
, after
);
1364 set_insn_init (expr
, NULL
, seqno
);
1365 sel_init_new_insn (new_insn
, INSN_INIT_TODO_LUID
| INSN_INIT_TODO_SSID
);
1370 /* Force newly generated vinsns to be unique. */
1371 static bool init_insn_force_unique_p
= false;
1373 /* Emit new speculation recovery insn after AFTER based on PATTERN and
1374 initialize its data from EXPR and SEQNO. */
1376 sel_gen_recovery_insn_from_rtx_after (rtx pattern
, expr_t expr
, int seqno
,
1381 gcc_assert (!init_insn_force_unique_p
);
1383 init_insn_force_unique_p
= true;
1384 insn
= sel_gen_insn_from_rtx_after (pattern
, expr
, seqno
, after
);
1385 CANT_MOVE (insn
) = 1;
1386 init_insn_force_unique_p
= false;
1391 /* Emit new insn after AFTER based on EXPR and SEQNO. If VINSN is not NULL,
1392 take it as a new vinsn instead of EXPR's vinsn.
1393 We simplify insns later, after scheduling region in
1394 simplify_changed_insns. */
1396 sel_gen_insn_from_expr_after (expr_t expr
, vinsn_t vinsn
, int seqno
,
1403 emit_expr
= set_insn_init (expr
, vinsn
? vinsn
: EXPR_VINSN (expr
),
1405 insn
= EXPR_INSN_RTX (emit_expr
);
1407 /* The insn may come from the transformation cache, which may hold already
1408 deleted insns, so mark it as not deleted. */
1409 insn
->set_undeleted ();
1411 add_insn_after (insn
, after
, BLOCK_FOR_INSN (insn
));
1413 flags
= INSN_INIT_TODO_SSID
;
1414 if (INSN_LUID (insn
) == 0)
1415 flags
|= INSN_INIT_TODO_LUID
;
1416 sel_init_new_insn (insn
, flags
);
1421 /* Move insn from EXPR after AFTER. */
1423 sel_move_insn (expr_t expr
, int seqno
, insn_t after
)
1425 insn_t insn
= EXPR_INSN_RTX (expr
);
1426 basic_block bb
= BLOCK_FOR_INSN (after
);
1427 insn_t next
= NEXT_INSN (after
);
1429 /* Assert that in move_op we disconnected this insn properly. */
1430 gcc_assert (EXPR_VINSN (INSN_EXPR (insn
)) != NULL
);
1431 SET_PREV_INSN (insn
) = after
;
1432 SET_NEXT_INSN (insn
) = next
;
1434 SET_NEXT_INSN (after
) = insn
;
1435 SET_PREV_INSN (next
) = insn
;
1437 /* Update links from insn to bb and vice versa. */
1438 df_insn_change_bb (insn
, bb
);
1439 if (BB_END (bb
) == after
)
1442 prepare_insn_expr (insn
, seqno
);
1447 /* Functions to work with right-hand sides. */
1449 /* Search for a hash value determined by UID/NEW_VINSN in a sorted vector
1450 VECT and return true when found. Use NEW_VINSN for comparison only when
1451 COMPARE_VINSNS is true. Write to INDP the index on which
1452 the search has stopped, such that inserting the new element at INDP will
1453 retain VECT's sort order. */
1455 find_in_history_vect_1 (vec
<expr_history_def
> vect
,
1456 unsigned uid
, vinsn_t new_vinsn
,
1457 bool compare_vinsns
, int *indp
)
1459 expr_history_def
*arr
;
1460 int i
, j
, len
= vect
.length ();
1468 arr
= vect
.address ();
1473 unsigned auid
= arr
[i
].uid
;
1474 vinsn_t avinsn
= arr
[i
].new_expr_vinsn
;
1477 /* When undoing transformation on a bookkeeping copy, the new vinsn
1478 may not be exactly equal to the one that is saved in the vector.
1479 This is because the insn whose copy we're checking was possibly
1480 substituted itself. */
1481 && (! compare_vinsns
1482 || vinsn_equal_p (avinsn
, new_vinsn
)))
1487 else if (auid
> uid
)
1496 /* Search for a uid of INSN and NEW_VINSN in a sorted vector VECT. Return
1497 the position found or -1, if no such value is in vector.
1498 Search also for UIDs of insn's originators, if ORIGINATORS_P is true. */
1500 find_in_history_vect (vec
<expr_history_def
> vect
, rtx insn
,
1501 vinsn_t new_vinsn
, bool originators_p
)
1505 if (find_in_history_vect_1 (vect
, INSN_UID (insn
), new_vinsn
,
1509 if (INSN_ORIGINATORS (insn
) && originators_p
)
1514 EXECUTE_IF_SET_IN_BITMAP (INSN_ORIGINATORS (insn
), 0, uid
, bi
)
1515 if (find_in_history_vect_1 (vect
, uid
, new_vinsn
, false, &ind
))
1522 /* Insert new element in a sorted history vector pointed to by PVECT,
1523 if it is not there already. The element is searched using
1524 UID/NEW_EXPR_VINSN pair. TYPE, OLD_EXPR_VINSN and SPEC_DS save
1525 the history of a transformation. */
1527 insert_in_history_vect (vec
<expr_history_def
> *pvect
,
1528 unsigned uid
, enum local_trans_type type
,
1529 vinsn_t old_expr_vinsn
, vinsn_t new_expr_vinsn
,
1532 vec
<expr_history_def
> vect
= *pvect
;
1533 expr_history_def temp
;
1537 res
= find_in_history_vect_1 (vect
, uid
, new_expr_vinsn
, true, &ind
);
1541 expr_history_def
*phist
= &vect
[ind
];
1543 /* It is possible that speculation types of expressions that were
1544 propagated through different paths will be different here. In this
1545 case, merge the status to get the correct check later. */
1546 if (phist
->spec_ds
!= spec_ds
)
1547 phist
->spec_ds
= ds_max_merge (phist
->spec_ds
, spec_ds
);
1552 temp
.old_expr_vinsn
= old_expr_vinsn
;
1553 temp
.new_expr_vinsn
= new_expr_vinsn
;
1554 temp
.spec_ds
= spec_ds
;
1557 vinsn_attach (old_expr_vinsn
);
1558 vinsn_attach (new_expr_vinsn
);
1559 vect
.safe_insert (ind
, temp
);
1563 /* Free history vector PVECT. */
1565 free_history_vect (vec
<expr_history_def
> &pvect
)
1568 expr_history_def
*phist
;
1570 if (! pvect
.exists ())
1573 for (i
= 0; pvect
.iterate (i
, &phist
); i
++)
1575 vinsn_detach (phist
->old_expr_vinsn
);
1576 vinsn_detach (phist
->new_expr_vinsn
);
1582 /* Merge vector FROM to PVECT. */
1584 merge_history_vect (vec
<expr_history_def
> *pvect
,
1585 vec
<expr_history_def
> from
)
1587 expr_history_def
*phist
;
1590 /* We keep this vector sorted. */
1591 for (i
= 0; from
.iterate (i
, &phist
); i
++)
1592 insert_in_history_vect (pvect
, phist
->uid
, phist
->type
,
1593 phist
->old_expr_vinsn
, phist
->new_expr_vinsn
,
1597 /* Compare two vinsns as rhses if possible and as vinsns otherwise. */
1599 vinsn_equal_p (vinsn_t x
, vinsn_t y
)
1601 rtx_equal_p_callback_function repcf
;
1606 if (VINSN_TYPE (x
) != VINSN_TYPE (y
))
1609 if (VINSN_HASH (x
) != VINSN_HASH (y
))
1612 repcf
= targetm
.sched
.skip_rtx_p
? skip_unspecs_callback
: NULL
;
1613 if (VINSN_SEPARABLE_P (x
))
1615 /* Compare RHSes of VINSNs. */
1616 gcc_assert (VINSN_RHS (x
));
1617 gcc_assert (VINSN_RHS (y
));
1619 return rtx_equal_p_cb (VINSN_RHS (x
), VINSN_RHS (y
), repcf
);
1622 return rtx_equal_p_cb (VINSN_PATTERN (x
), VINSN_PATTERN (y
), repcf
);
1626 /* Functions for working with expressions. */
1628 /* Initialize EXPR. */
1630 init_expr (expr_t expr
, vinsn_t vi
, int spec
, int use
, int priority
,
1631 int sched_times
, int orig_bb_index
, ds_t spec_done_ds
,
1632 ds_t spec_to_check_ds
, int orig_sched_cycle
,
1633 vec
<expr_history_def
> history
,
1634 signed char target_available
,
1635 bool was_substituted
, bool was_renamed
, bool needs_spec_check_p
,
1640 EXPR_VINSN (expr
) = vi
;
1641 EXPR_SPEC (expr
) = spec
;
1642 EXPR_USEFULNESS (expr
) = use
;
1643 EXPR_PRIORITY (expr
) = priority
;
1644 EXPR_PRIORITY_ADJ (expr
) = 0;
1645 EXPR_SCHED_TIMES (expr
) = sched_times
;
1646 EXPR_ORIG_BB_INDEX (expr
) = orig_bb_index
;
1647 EXPR_ORIG_SCHED_CYCLE (expr
) = orig_sched_cycle
;
1648 EXPR_SPEC_DONE_DS (expr
) = spec_done_ds
;
1649 EXPR_SPEC_TO_CHECK_DS (expr
) = spec_to_check_ds
;
1651 if (history
.exists ())
1652 EXPR_HISTORY_OF_CHANGES (expr
) = history
;
1654 EXPR_HISTORY_OF_CHANGES (expr
).create (0);
1656 EXPR_TARGET_AVAILABLE (expr
) = target_available
;
1657 EXPR_WAS_SUBSTITUTED (expr
) = was_substituted
;
1658 EXPR_WAS_RENAMED (expr
) = was_renamed
;
1659 EXPR_NEEDS_SPEC_CHECK_P (expr
) = needs_spec_check_p
;
1660 EXPR_CANT_MOVE (expr
) = cant_move
;
1663 /* Make a copy of the expr FROM into the expr TO. */
1665 copy_expr (expr_t to
, expr_t from
)
1667 vec
<expr_history_def
> temp
= vNULL
;
1669 if (EXPR_HISTORY_OF_CHANGES (from
).exists ())
1672 expr_history_def
*phist
;
1674 temp
= EXPR_HISTORY_OF_CHANGES (from
).copy ();
1676 temp
.iterate (i
, &phist
);
1679 vinsn_attach (phist
->old_expr_vinsn
);
1680 vinsn_attach (phist
->new_expr_vinsn
);
1684 init_expr (to
, EXPR_VINSN (from
), EXPR_SPEC (from
),
1685 EXPR_USEFULNESS (from
), EXPR_PRIORITY (from
),
1686 EXPR_SCHED_TIMES (from
), EXPR_ORIG_BB_INDEX (from
),
1687 EXPR_SPEC_DONE_DS (from
), EXPR_SPEC_TO_CHECK_DS (from
),
1688 EXPR_ORIG_SCHED_CYCLE (from
), temp
,
1689 EXPR_TARGET_AVAILABLE (from
), EXPR_WAS_SUBSTITUTED (from
),
1690 EXPR_WAS_RENAMED (from
), EXPR_NEEDS_SPEC_CHECK_P (from
),
1691 EXPR_CANT_MOVE (from
));
1694 /* Same, but the final expr will not ever be in av sets, so don't copy
1695 "uninteresting" data such as bitmap cache. */
1697 copy_expr_onside (expr_t to
, expr_t from
)
1699 init_expr (to
, EXPR_VINSN (from
), EXPR_SPEC (from
), EXPR_USEFULNESS (from
),
1700 EXPR_PRIORITY (from
), EXPR_SCHED_TIMES (from
), 0,
1701 EXPR_SPEC_DONE_DS (from
), EXPR_SPEC_TO_CHECK_DS (from
), 0,
1703 EXPR_TARGET_AVAILABLE (from
), EXPR_WAS_SUBSTITUTED (from
),
1704 EXPR_WAS_RENAMED (from
), EXPR_NEEDS_SPEC_CHECK_P (from
),
1705 EXPR_CANT_MOVE (from
));
1708 /* Prepare the expr of INSN for scheduling. Used when moving insn and when
1709 initializing new insns. */
1711 prepare_insn_expr (insn_t insn
, int seqno
)
1713 expr_t expr
= INSN_EXPR (insn
);
1716 INSN_SEQNO (insn
) = seqno
;
1717 EXPR_ORIG_BB_INDEX (expr
) = BLOCK_NUM (insn
);
1718 EXPR_SPEC (expr
) = 0;
1719 EXPR_ORIG_SCHED_CYCLE (expr
) = 0;
1720 EXPR_WAS_SUBSTITUTED (expr
) = 0;
1721 EXPR_WAS_RENAMED (expr
) = 0;
1722 EXPR_TARGET_AVAILABLE (expr
) = 1;
1723 INSN_LIVE_VALID_P (insn
) = false;
1725 /* ??? If this expression is speculative, make its dependence
1726 as weak as possible. We can filter this expression later
1727 in process_spec_exprs, because we do not distinguish
1728 between the status we got during compute_av_set and the
1729 existing status. To be fixed. */
1730 ds
= EXPR_SPEC_DONE_DS (expr
);
1732 EXPR_SPEC_DONE_DS (expr
) = ds_get_max_dep_weak (ds
);
1734 free_history_vect (EXPR_HISTORY_OF_CHANGES (expr
));
1737 /* Update target_available bits when merging exprs TO and FROM. SPLIT_POINT
1738 is non-null when expressions are merged from different successors at
1741 update_target_availability (expr_t to
, expr_t from
, insn_t split_point
)
1743 if (EXPR_TARGET_AVAILABLE (to
) < 0
1744 || EXPR_TARGET_AVAILABLE (from
) < 0)
1745 EXPR_TARGET_AVAILABLE (to
) = -1;
1748 /* We try to detect the case when one of the expressions
1749 can only be reached through another one. In this case,
1750 we can do better. */
1751 if (split_point
== NULL
)
1755 toind
= EXPR_ORIG_BB_INDEX (to
);
1756 fromind
= EXPR_ORIG_BB_INDEX (from
);
1758 if (toind
&& toind
== fromind
)
1759 /* Do nothing -- everything is done in
1760 merge_with_other_exprs. */
1763 EXPR_TARGET_AVAILABLE (to
) = -1;
1765 else if (EXPR_TARGET_AVAILABLE (from
) == 0
1767 && REG_P (EXPR_LHS (from
))
1768 && REGNO (EXPR_LHS (to
)) != REGNO (EXPR_LHS (from
)))
1769 EXPR_TARGET_AVAILABLE (to
) = -1;
1771 EXPR_TARGET_AVAILABLE (to
) &= EXPR_TARGET_AVAILABLE (from
);
1775 /* Update speculation bits when merging exprs TO and FROM. SPLIT_POINT
1776 is non-null when expressions are merged from different successors at
1779 update_speculative_bits (expr_t to
, expr_t from
, insn_t split_point
)
1781 ds_t old_to_ds
, old_from_ds
;
1783 old_to_ds
= EXPR_SPEC_DONE_DS (to
);
1784 old_from_ds
= EXPR_SPEC_DONE_DS (from
);
1786 EXPR_SPEC_DONE_DS (to
) = ds_max_merge (old_to_ds
, old_from_ds
);
1787 EXPR_SPEC_TO_CHECK_DS (to
) |= EXPR_SPEC_TO_CHECK_DS (from
);
1788 EXPR_NEEDS_SPEC_CHECK_P (to
) |= EXPR_NEEDS_SPEC_CHECK_P (from
);
1790 /* When merging e.g. control & data speculative exprs, or a control
1791 speculative with a control&data speculative one, we really have
1792 to change vinsn too. Also, when speculative status is changed,
1793 we also need to record this as a transformation in expr's history. */
1794 if ((old_to_ds
& SPECULATIVE
) || (old_from_ds
& SPECULATIVE
))
1796 old_to_ds
= ds_get_speculation_types (old_to_ds
);
1797 old_from_ds
= ds_get_speculation_types (old_from_ds
);
1799 if (old_to_ds
!= old_from_ds
)
1803 /* When both expressions are speculative, we need to change
1805 if ((old_to_ds
& SPECULATIVE
) && (old_from_ds
& SPECULATIVE
))
1809 res
= speculate_expr (to
, EXPR_SPEC_DONE_DS (to
));
1810 gcc_assert (res
>= 0);
1813 if (split_point
!= NULL
)
1815 /* Record the change with proper status. */
1816 record_ds
= EXPR_SPEC_DONE_DS (to
) & SPECULATIVE
;
1817 record_ds
&= ~(old_to_ds
& SPECULATIVE
);
1818 record_ds
&= ~(old_from_ds
& SPECULATIVE
);
1820 insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (to
),
1821 INSN_UID (split_point
), TRANS_SPECULATION
,
1822 EXPR_VINSN (from
), EXPR_VINSN (to
),
1830 /* Merge bits of FROM expr to TO expr. When SPLIT_POINT is not NULL,
1831 this is done along different paths. */
1833 merge_expr_data (expr_t to
, expr_t from
, insn_t split_point
)
1835 /* Choose the maximum of the specs of merged exprs. This is required
1836 for correctness of bookkeeping. */
1837 if (EXPR_SPEC (to
) < EXPR_SPEC (from
))
1838 EXPR_SPEC (to
) = EXPR_SPEC (from
);
1841 EXPR_USEFULNESS (to
) += EXPR_USEFULNESS (from
);
1843 EXPR_USEFULNESS (to
) = MAX (EXPR_USEFULNESS (to
),
1844 EXPR_USEFULNESS (from
));
1846 if (EXPR_PRIORITY (to
) < EXPR_PRIORITY (from
))
1847 EXPR_PRIORITY (to
) = EXPR_PRIORITY (from
);
1849 if (EXPR_SCHED_TIMES (to
) > EXPR_SCHED_TIMES (from
))
1850 EXPR_SCHED_TIMES (to
) = EXPR_SCHED_TIMES (from
);
1852 if (EXPR_ORIG_BB_INDEX (to
) != EXPR_ORIG_BB_INDEX (from
))
1853 EXPR_ORIG_BB_INDEX (to
) = 0;
1855 EXPR_ORIG_SCHED_CYCLE (to
) = MIN (EXPR_ORIG_SCHED_CYCLE (to
),
1856 EXPR_ORIG_SCHED_CYCLE (from
));
1858 EXPR_WAS_SUBSTITUTED (to
) |= EXPR_WAS_SUBSTITUTED (from
);
1859 EXPR_WAS_RENAMED (to
) |= EXPR_WAS_RENAMED (from
);
1860 EXPR_CANT_MOVE (to
) |= EXPR_CANT_MOVE (from
);
1862 merge_history_vect (&EXPR_HISTORY_OF_CHANGES (to
),
1863 EXPR_HISTORY_OF_CHANGES (from
));
1864 update_target_availability (to
, from
, split_point
);
1865 update_speculative_bits (to
, from
, split_point
);
1868 /* Merge bits of FROM expr to TO expr. Vinsns in the exprs should be equal
1869 in terms of vinsn_equal_p. SPLIT_POINT is non-null when expressions
1870 are merged from different successors at a split point. */
1872 merge_expr (expr_t to
, expr_t from
, insn_t split_point
)
1874 vinsn_t to_vi
= EXPR_VINSN (to
);
1875 vinsn_t from_vi
= EXPR_VINSN (from
);
1877 gcc_assert (vinsn_equal_p (to_vi
, from_vi
));
1879 /* Make sure that speculative pattern is propagated into exprs that
1880 have non-speculative one. This will provide us with consistent
1881 speculative bits and speculative patterns inside expr. */
1882 if ((EXPR_SPEC_DONE_DS (from
) != 0
1883 && EXPR_SPEC_DONE_DS (to
) == 0)
1884 /* Do likewise for volatile insns, so that we always retain
1885 the may_trap_p bit on the resulting expression. */
1886 || (VINSN_MAY_TRAP_P (EXPR_VINSN (from
))
1887 && !VINSN_MAY_TRAP_P (EXPR_VINSN (to
))))
1888 change_vinsn_in_expr (to
, EXPR_VINSN (from
));
1890 merge_expr_data (to
, from
, split_point
);
1891 gcc_assert (EXPR_USEFULNESS (to
) <= REG_BR_PROB_BASE
);
1894 /* Clear the information of this EXPR. */
1896 clear_expr (expr_t expr
)
1899 vinsn_detach (EXPR_VINSN (expr
));
1900 EXPR_VINSN (expr
) = NULL
;
1902 free_history_vect (EXPR_HISTORY_OF_CHANGES (expr
));
1905 /* For a given LV_SET, mark EXPR having unavailable target register. */
1907 set_unavailable_target_for_expr (expr_t expr
, regset lv_set
)
1909 if (EXPR_SEPARABLE_P (expr
))
1911 if (REG_P (EXPR_LHS (expr
))
1912 && register_unavailable_p (lv_set
, EXPR_LHS (expr
)))
1914 /* If it's an insn like r1 = use (r1, ...), and it exists in
1915 different forms in each of the av_sets being merged, we can't say
1916 whether original destination register is available or not.
1917 However, this still works if destination register is not used
1918 in the original expression: if the branch at which LV_SET we're
1919 looking here is not actually 'other branch' in sense that same
1920 expression is available through it (but it can't be determined
1921 at computation stage because of transformations on one of the
1922 branches), it still won't affect the availability.
1923 Liveness of a register somewhere on a code motion path means
1924 it's either read somewhere on a codemotion path, live on
1925 'other' branch, live at the point immediately following
1926 the original operation, or is read by the original operation.
1927 The latter case is filtered out in the condition below.
1928 It still doesn't cover the case when register is defined and used
1929 somewhere within the code motion path, and in this case we could
1930 miss a unifying code motion along both branches using a renamed
1931 register, but it won't affect a code correctness since upon
1932 an actual code motion a bookkeeping code would be generated. */
1933 if (register_unavailable_p (VINSN_REG_USES (EXPR_VINSN (expr
)),
1935 EXPR_TARGET_AVAILABLE (expr
) = -1;
1937 EXPR_TARGET_AVAILABLE (expr
) = false;
1943 reg_set_iterator rsi
;
1945 EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_SETS (EXPR_VINSN (expr
)),
1947 if (bitmap_bit_p (lv_set
, regno
))
1949 EXPR_TARGET_AVAILABLE (expr
) = false;
1953 EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_CLOBBERS (EXPR_VINSN (expr
)),
1955 if (bitmap_bit_p (lv_set
, regno
))
1957 EXPR_TARGET_AVAILABLE (expr
) = false;
1963 /* Try to make EXPR speculative. Return 1 when EXPR's pattern
1964 or dependence status have changed, 2 when also the target register
1965 became unavailable, 0 if nothing had to be changed. */
1967 speculate_expr (expr_t expr
, ds_t ds
)
1970 rtx_insn
*orig_insn_rtx
;
1972 ds_t target_ds
, current_ds
;
1974 /* Obtain the status we need to put on EXPR. */
1975 target_ds
= (ds
& SPECULATIVE
);
1976 current_ds
= EXPR_SPEC_DONE_DS (expr
);
1977 ds
= ds_full_merge (current_ds
, target_ds
, NULL_RTX
, NULL_RTX
);
1979 orig_insn_rtx
= EXPR_INSN_RTX (expr
);
1981 res
= sched_speculate_insn (orig_insn_rtx
, ds
, &spec_pat
);
1986 EXPR_SPEC_DONE_DS (expr
) = ds
;
1987 return current_ds
!= ds
? 1 : 0;
1991 rtx_insn
*spec_insn_rtx
=
1992 create_insn_rtx_from_pattern (spec_pat
, NULL_RTX
);
1993 vinsn_t spec_vinsn
= create_vinsn_from_insn_rtx (spec_insn_rtx
, false);
1995 change_vinsn_in_expr (expr
, spec_vinsn
);
1996 EXPR_SPEC_DONE_DS (expr
) = ds
;
1997 EXPR_NEEDS_SPEC_CHECK_P (expr
) = true;
1999 /* Do not allow clobbering the address register of speculative
2001 if (register_unavailable_p (VINSN_REG_USES (EXPR_VINSN (expr
)),
2002 expr_dest_reg (expr
)))
2004 EXPR_TARGET_AVAILABLE (expr
) = false;
2020 /* Return a destination register, if any, of EXPR. */
2022 expr_dest_reg (expr_t expr
)
2024 rtx dest
= VINSN_LHS (EXPR_VINSN (expr
));
2026 if (dest
!= NULL_RTX
&& REG_P (dest
))
2032 /* Returns the REGNO of the R's destination. */
2034 expr_dest_regno (expr_t expr
)
2036 rtx dest
= expr_dest_reg (expr
);
2038 gcc_assert (dest
!= NULL_RTX
);
2039 return REGNO (dest
);
2042 /* For a given LV_SET, mark all expressions in JOIN_SET, but not present in
2043 AV_SET having unavailable target register. */
2045 mark_unavailable_targets (av_set_t join_set
, av_set_t av_set
, regset lv_set
)
2048 av_set_iterator avi
;
2050 FOR_EACH_EXPR (expr
, avi
, join_set
)
2051 if (av_set_lookup (av_set
, EXPR_VINSN (expr
)) == NULL
)
2052 set_unavailable_target_for_expr (expr
, lv_set
);
2056 /* Returns true if REG (at least partially) is present in REGS. */
2058 register_unavailable_p (regset regs
, rtx reg
)
2060 unsigned regno
, end_regno
;
2062 regno
= REGNO (reg
);
2063 if (bitmap_bit_p (regs
, regno
))
2066 end_regno
= END_REGNO (reg
);
2068 while (++regno
< end_regno
)
2069 if (bitmap_bit_p (regs
, regno
))
2075 /* Av set functions. */
2077 /* Add a new element to av set SETP.
2078 Return the element added. */
2080 av_set_add_element (av_set_t
*setp
)
2082 /* Insert at the beginning of the list. */
2087 /* Add EXPR to SETP. */
2089 av_set_add (av_set_t
*setp
, expr_t expr
)
2093 gcc_assert (!INSN_NOP_P (EXPR_INSN_RTX (expr
)));
2094 elem
= av_set_add_element (setp
);
2095 copy_expr (_AV_SET_EXPR (elem
), expr
);
2098 /* Same, but do not copy EXPR. */
2100 av_set_add_nocopy (av_set_t
*setp
, expr_t expr
)
2104 elem
= av_set_add_element (setp
);
2105 *_AV_SET_EXPR (elem
) = *expr
;
2108 /* Remove expr pointed to by IP from the av_set. */
2110 av_set_iter_remove (av_set_iterator
*ip
)
2112 clear_expr (_AV_SET_EXPR (*ip
->lp
));
2113 _list_iter_remove (ip
);
2116 /* Search for an expr in SET, such that it's equivalent to SOUGHT_VINSN in the
2117 sense of vinsn_equal_p function. Return NULL if no such expr is
2118 in SET was found. */
2120 av_set_lookup (av_set_t set
, vinsn_t sought_vinsn
)
2125 FOR_EACH_EXPR (expr
, i
, set
)
2126 if (vinsn_equal_p (EXPR_VINSN (expr
), sought_vinsn
))
2131 /* Same, but also remove the EXPR found. */
2133 av_set_lookup_and_remove (av_set_t
*setp
, vinsn_t sought_vinsn
)
2138 FOR_EACH_EXPR_1 (expr
, i
, setp
)
2139 if (vinsn_equal_p (EXPR_VINSN (expr
), sought_vinsn
))
2141 _list_iter_remove_nofree (&i
);
2147 /* Search for an expr in SET, such that it's equivalent to EXPR in the
2148 sense of vinsn_equal_p function of their vinsns, but not EXPR itself.
2149 Returns NULL if no such expr is in SET was found. */
2151 av_set_lookup_other_equiv_expr (av_set_t set
, expr_t expr
)
2156 FOR_EACH_EXPR (cur_expr
, i
, set
)
2158 if (cur_expr
== expr
)
2160 if (vinsn_equal_p (EXPR_VINSN (cur_expr
), EXPR_VINSN (expr
)))
2167 /* If other expression is already in AVP, remove one of them. */
2169 merge_with_other_exprs (av_set_t
*avp
, av_set_iterator
*ip
, expr_t expr
)
2173 expr2
= av_set_lookup_other_equiv_expr (*avp
, expr
);
2176 /* Reset target availability on merge, since taking it only from one
2177 of the exprs would be controversial for different code. */
2178 EXPR_TARGET_AVAILABLE (expr2
) = -1;
2179 EXPR_USEFULNESS (expr2
) = 0;
2181 merge_expr (expr2
, expr
, NULL
);
2183 /* Fix usefulness as it should be now REG_BR_PROB_BASE. */
2184 EXPR_USEFULNESS (expr2
) = REG_BR_PROB_BASE
;
2186 av_set_iter_remove (ip
);
2193 /* Return true if there is an expr that correlates to VI in SET. */
2195 av_set_is_in_p (av_set_t set
, vinsn_t vi
)
2197 return av_set_lookup (set
, vi
) != NULL
;
2200 /* Return a copy of SET. */
2202 av_set_copy (av_set_t set
)
2206 av_set_t res
= NULL
;
2208 FOR_EACH_EXPR (expr
, i
, set
)
2209 av_set_add (&res
, expr
);
2214 /* Join two av sets that do not have common elements by attaching second set
2215 (pointed to by FROMP) to the end of first set (TO_TAILP must point to
2216 _AV_SET_NEXT of first set's last element). */
2218 join_distinct_sets (av_set_t
*to_tailp
, av_set_t
*fromp
)
2220 gcc_assert (*to_tailp
== NULL
);
2225 /* Makes set pointed to by TO to be the union of TO and FROM. Clear av_set
2226 pointed to by FROMP afterwards. */
2228 av_set_union_and_clear (av_set_t
*top
, av_set_t
*fromp
, insn_t insn
)
2233 /* Delete from TOP all exprs, that present in FROMP. */
2234 FOR_EACH_EXPR_1 (expr1
, i
, top
)
2236 expr_t expr2
= av_set_lookup (*fromp
, EXPR_VINSN (expr1
));
2240 merge_expr (expr2
, expr1
, insn
);
2241 av_set_iter_remove (&i
);
2245 join_distinct_sets (i
.lp
, fromp
);
2248 /* Same as above, but also update availability of target register in
2249 TOP judging by TO_LV_SET and FROM_LV_SET. */
2251 av_set_union_and_live (av_set_t
*top
, av_set_t
*fromp
, regset to_lv_set
,
2252 regset from_lv_set
, insn_t insn
)
2256 av_set_t
*to_tailp
, in_both_set
= NULL
;
2258 /* Delete from TOP all expres, that present in FROMP. */
2259 FOR_EACH_EXPR_1 (expr1
, i
, top
)
2261 expr_t expr2
= av_set_lookup_and_remove (fromp
, EXPR_VINSN (expr1
));
2265 /* It may be that the expressions have different destination
2266 registers, in which case we need to check liveness here. */
2267 if (EXPR_SEPARABLE_P (expr1
))
2269 int regno1
= (REG_P (EXPR_LHS (expr1
))
2270 ? (int) expr_dest_regno (expr1
) : -1);
2271 int regno2
= (REG_P (EXPR_LHS (expr2
))
2272 ? (int) expr_dest_regno (expr2
) : -1);
2274 /* ??? We don't have a way to check restrictions for
2275 *other* register on the current path, we did it only
2276 for the current target register. Give up. */
2277 if (regno1
!= regno2
)
2278 EXPR_TARGET_AVAILABLE (expr2
) = -1;
2280 else if (EXPR_INSN_RTX (expr1
) != EXPR_INSN_RTX (expr2
))
2281 EXPR_TARGET_AVAILABLE (expr2
) = -1;
2283 merge_expr (expr2
, expr1
, insn
);
2284 av_set_add_nocopy (&in_both_set
, expr2
);
2285 av_set_iter_remove (&i
);
2288 /* EXPR1 is present in TOP, but not in FROMP. Check it on
2290 set_unavailable_target_for_expr (expr1
, from_lv_set
);
2294 /* These expressions are not present in TOP. Check liveness
2295 restrictions on TO_LV_SET. */
2296 FOR_EACH_EXPR (expr1
, i
, *fromp
)
2297 set_unavailable_target_for_expr (expr1
, to_lv_set
);
2299 join_distinct_sets (i
.lp
, &in_both_set
);
2300 join_distinct_sets (to_tailp
, fromp
);
2303 /* Clear av_set pointed to by SETP. */
2305 av_set_clear (av_set_t
*setp
)
2310 FOR_EACH_EXPR_1 (expr
, i
, setp
)
2311 av_set_iter_remove (&i
);
2313 gcc_assert (*setp
== NULL
);
2316 /* Leave only one non-speculative element in the SETP. */
2318 av_set_leave_one_nonspec (av_set_t
*setp
)
2322 bool has_one_nonspec
= false;
2324 /* Keep all speculative exprs, and leave one non-speculative
2326 FOR_EACH_EXPR_1 (expr
, i
, setp
)
2328 if (!EXPR_SPEC_DONE_DS (expr
))
2330 if (has_one_nonspec
)
2331 av_set_iter_remove (&i
);
2333 has_one_nonspec
= true;
2338 /* Return the N'th element of the SET. */
2340 av_set_element (av_set_t set
, int n
)
2345 FOR_EACH_EXPR (expr
, i
, set
)
2353 /* Deletes all expressions from AVP that are conditional branches (IFs). */
2355 av_set_substract_cond_branches (av_set_t
*avp
)
2360 FOR_EACH_EXPR_1 (expr
, i
, avp
)
2361 if (vinsn_cond_branch_p (EXPR_VINSN (expr
)))
2362 av_set_iter_remove (&i
);
2365 /* Multiplies usefulness attribute of each member of av-set *AVP by
2366 value PROB / ALL_PROB. */
2368 av_set_split_usefulness (av_set_t av
, int prob
, int all_prob
)
2373 FOR_EACH_EXPR (expr
, i
, av
)
2374 EXPR_USEFULNESS (expr
) = (all_prob
2375 ? (EXPR_USEFULNESS (expr
) * prob
) / all_prob
2379 /* Leave in AVP only those expressions, which are present in AV,
2380 and return it, merging history expressions. */
2382 av_set_code_motion_filter (av_set_t
*avp
, av_set_t av
)
2387 FOR_EACH_EXPR_1 (expr
, i
, avp
)
2388 if ((expr2
= av_set_lookup (av
, EXPR_VINSN (expr
))) == NULL
)
2389 av_set_iter_remove (&i
);
2391 /* When updating av sets in bookkeeping blocks, we can add more insns
2392 there which will be transformed but the upper av sets will not
2393 reflect those transformations. We then fail to undo those
2394 when searching for such insns. So merge the history saved
2395 in the av set of the block we are processing. */
2396 merge_history_vect (&EXPR_HISTORY_OF_CHANGES (expr
),
2397 EXPR_HISTORY_OF_CHANGES (expr2
));
2402 /* Dependence hooks to initialize insn data. */
2404 /* This is used in hooks callable from dependence analysis when initializing
2405 instruction's data. */
2408 /* Where the dependence was found (lhs/rhs). */
2411 /* The actual data object to initialize. */
2414 /* True when the insn should not be made clonable. */
2415 bool force_unique_p
;
2417 /* True when insn should be treated as of type USE, i.e. never renamed. */
2419 } deps_init_id_data
;
2422 /* Setup ID for INSN. FORCE_UNIQUE_P is true when INSN should not be
2425 setup_id_for_insn (idata_t id
, insn_t insn
, bool force_unique_p
)
2429 /* Determine whether INSN could be cloned and return appropriate vinsn type.
2430 That clonable insns which can be separated into lhs and rhs have type SET.
2431 Other clonable insns have type USE. */
2432 type
= GET_CODE (insn
);
2434 /* Only regular insns could be cloned. */
2435 if (type
== INSN
&& !force_unique_p
)
2437 else if (type
== JUMP_INSN
&& simplejump_p (insn
))
2439 else if (type
== DEBUG_INSN
)
2440 type
= !force_unique_p
? USE
: INSN
;
2442 IDATA_TYPE (id
) = type
;
2443 IDATA_REG_SETS (id
) = get_clear_regset_from_pool ();
2444 IDATA_REG_USES (id
) = get_clear_regset_from_pool ();
2445 IDATA_REG_CLOBBERS (id
) = get_clear_regset_from_pool ();
2448 /* Start initializing insn data. */
2450 deps_init_id_start_insn (insn_t insn
)
2452 gcc_assert (deps_init_id_data
.where
== DEPS_IN_NOWHERE
);
2454 setup_id_for_insn (deps_init_id_data
.id
, insn
,
2455 deps_init_id_data
.force_unique_p
);
2456 deps_init_id_data
.where
= DEPS_IN_INSN
;
2459 /* Start initializing lhs data. */
2461 deps_init_id_start_lhs (rtx lhs
)
2463 gcc_assert (deps_init_id_data
.where
== DEPS_IN_INSN
);
2464 gcc_assert (IDATA_LHS (deps_init_id_data
.id
) == NULL
);
2466 if (IDATA_TYPE (deps_init_id_data
.id
) == SET
)
2468 IDATA_LHS (deps_init_id_data
.id
) = lhs
;
2469 deps_init_id_data
.where
= DEPS_IN_LHS
;
2473 /* Finish initializing lhs data. */
2475 deps_init_id_finish_lhs (void)
2477 deps_init_id_data
.where
= DEPS_IN_INSN
;
2480 /* Note a set of REGNO. */
2482 deps_init_id_note_reg_set (int regno
)
2484 haifa_note_reg_set (regno
);
2486 if (deps_init_id_data
.where
== DEPS_IN_RHS
)
2487 deps_init_id_data
.force_use_p
= true;
2489 if (IDATA_TYPE (deps_init_id_data
.id
) != PC
)
2490 SET_REGNO_REG_SET (IDATA_REG_SETS (deps_init_id_data
.id
), regno
);
2493 /* Make instructions that set stack registers to be ineligible for
2494 renaming to avoid issues with find_used_regs. */
2495 if (IN_RANGE (regno
, FIRST_STACK_REG
, LAST_STACK_REG
))
2496 deps_init_id_data
.force_use_p
= true;
2500 /* Note a clobber of REGNO. */
2502 deps_init_id_note_reg_clobber (int regno
)
2504 haifa_note_reg_clobber (regno
);
2506 if (deps_init_id_data
.where
== DEPS_IN_RHS
)
2507 deps_init_id_data
.force_use_p
= true;
2509 if (IDATA_TYPE (deps_init_id_data
.id
) != PC
)
2510 SET_REGNO_REG_SET (IDATA_REG_CLOBBERS (deps_init_id_data
.id
), regno
);
2513 /* Note a use of REGNO. */
2515 deps_init_id_note_reg_use (int regno
)
2517 haifa_note_reg_use (regno
);
2519 if (IDATA_TYPE (deps_init_id_data
.id
) != PC
)
2520 SET_REGNO_REG_SET (IDATA_REG_USES (deps_init_id_data
.id
), regno
);
2523 /* Start initializing rhs data. */
2525 deps_init_id_start_rhs (rtx rhs
)
2527 gcc_assert (deps_init_id_data
.where
== DEPS_IN_INSN
);
2529 /* And there was no sel_deps_reset_to_insn (). */
2530 if (IDATA_LHS (deps_init_id_data
.id
) != NULL
)
2532 IDATA_RHS (deps_init_id_data
.id
) = rhs
;
2533 deps_init_id_data
.where
= DEPS_IN_RHS
;
2537 /* Finish initializing rhs data. */
2539 deps_init_id_finish_rhs (void)
2541 gcc_assert (deps_init_id_data
.where
== DEPS_IN_RHS
2542 || deps_init_id_data
.where
== DEPS_IN_INSN
);
2543 deps_init_id_data
.where
= DEPS_IN_INSN
;
2546 /* Finish initializing insn data. */
2548 deps_init_id_finish_insn (void)
2550 gcc_assert (deps_init_id_data
.where
== DEPS_IN_INSN
);
2552 if (IDATA_TYPE (deps_init_id_data
.id
) == SET
)
2554 rtx lhs
= IDATA_LHS (deps_init_id_data
.id
);
2555 rtx rhs
= IDATA_RHS (deps_init_id_data
.id
);
2557 if (lhs
== NULL
|| rhs
== NULL
|| !lhs_and_rhs_separable_p (lhs
, rhs
)
2558 || deps_init_id_data
.force_use_p
)
2560 /* This should be a USE, as we don't want to schedule its RHS
2561 separately. However, we still want to have them recorded
2562 for the purposes of substitution. That's why we don't
2563 simply call downgrade_to_use () here. */
2564 gcc_assert (IDATA_TYPE (deps_init_id_data
.id
) == SET
);
2565 gcc_assert (!lhs
== !rhs
);
2567 IDATA_TYPE (deps_init_id_data
.id
) = USE
;
2571 deps_init_id_data
.where
= DEPS_IN_NOWHERE
;
2574 /* This is dependence info used for initializing insn's data. */
2575 static struct sched_deps_info_def deps_init_id_sched_deps_info
;
2577 /* This initializes most of the static part of the above structure. */
2578 static const struct sched_deps_info_def const_deps_init_id_sched_deps_info
=
2582 deps_init_id_start_insn
,
2583 deps_init_id_finish_insn
,
2584 deps_init_id_start_lhs
,
2585 deps_init_id_finish_lhs
,
2586 deps_init_id_start_rhs
,
2587 deps_init_id_finish_rhs
,
2588 deps_init_id_note_reg_set
,
2589 deps_init_id_note_reg_clobber
,
2590 deps_init_id_note_reg_use
,
2591 NULL
, /* note_mem_dep */
2592 NULL
, /* note_dep */
2595 0, /* use_deps_list */
2596 0 /* generate_spec_deps */
2599 /* Initialize INSN's lhs and rhs in ID. When FORCE_UNIQUE_P is true,
2600 we don't actually need information about lhs and rhs. */
2602 setup_id_lhs_rhs (idata_t id
, insn_t insn
, bool force_unique_p
)
2604 rtx pat
= PATTERN (insn
);
2606 if (NONJUMP_INSN_P (insn
)
2607 && GET_CODE (pat
) == SET
2610 IDATA_RHS (id
) = SET_SRC (pat
);
2611 IDATA_LHS (id
) = SET_DEST (pat
);
2614 IDATA_LHS (id
) = IDATA_RHS (id
) = NULL
;
2617 /* Possibly downgrade INSN to USE. */
2619 maybe_downgrade_id_to_use (idata_t id
, insn_t insn
)
2621 bool must_be_use
= false;
2623 rtx lhs
= IDATA_LHS (id
);
2624 rtx rhs
= IDATA_RHS (id
);
2626 /* We downgrade only SETs. */
2627 if (IDATA_TYPE (id
) != SET
)
2630 if (!lhs
|| !lhs_and_rhs_separable_p (lhs
, rhs
))
2632 IDATA_TYPE (id
) = USE
;
2636 FOR_EACH_INSN_DEF (def
, insn
)
2638 if (DF_REF_INSN (def
)
2639 && DF_REF_FLAGS_IS_SET (def
, DF_REF_PRE_POST_MODIFY
)
2640 && loc_mentioned_in_p (DF_REF_LOC (def
), IDATA_RHS (id
)))
2647 /* Make instructions that set stack registers to be ineligible for
2648 renaming to avoid issues with find_used_regs. */
2649 if (IN_RANGE (DF_REF_REGNO (def
), FIRST_STACK_REG
, LAST_STACK_REG
))
2658 IDATA_TYPE (id
) = USE
;
2661 /* Setup register sets describing INSN in ID. */
2663 setup_id_reg_sets (idata_t id
, insn_t insn
)
2665 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
2667 regset tmp
= get_clear_regset_from_pool ();
2669 FOR_EACH_INSN_INFO_DEF (def
, insn_info
)
2671 unsigned int regno
= DF_REF_REGNO (def
);
2673 /* Post modifies are treated like clobbers by sched-deps.c. */
2674 if (DF_REF_FLAGS_IS_SET (def
, (DF_REF_MUST_CLOBBER
2675 | DF_REF_PRE_POST_MODIFY
)))
2676 SET_REGNO_REG_SET (IDATA_REG_CLOBBERS (id
), regno
);
2677 else if (! DF_REF_FLAGS_IS_SET (def
, DF_REF_MAY_CLOBBER
))
2679 SET_REGNO_REG_SET (IDATA_REG_SETS (id
), regno
);
2682 /* For stack registers, treat writes to them as writes
2683 to the first one to be consistent with sched-deps.c. */
2684 if (IN_RANGE (regno
, FIRST_STACK_REG
, LAST_STACK_REG
))
2685 SET_REGNO_REG_SET (IDATA_REG_SETS (id
), FIRST_STACK_REG
);
2688 /* Mark special refs that generate read/write def pair. */
2689 if (DF_REF_FLAGS_IS_SET (def
, DF_REF_CONDITIONAL
)
2690 || regno
== STACK_POINTER_REGNUM
)
2691 bitmap_set_bit (tmp
, regno
);
2694 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
2696 unsigned int regno
= DF_REF_REGNO (use
);
2698 /* When these refs are met for the first time, skip them, as
2699 these uses are just counterparts of some defs. */
2700 if (bitmap_bit_p (tmp
, regno
))
2701 bitmap_clear_bit (tmp
, regno
);
2702 else if (! DF_REF_FLAGS_IS_SET (use
, DF_REF_CALL_STACK_USAGE
))
2704 SET_REGNO_REG_SET (IDATA_REG_USES (id
), regno
);
2707 /* For stack registers, treat reads from them as reads from
2708 the first one to be consistent with sched-deps.c. */
2709 if (IN_RANGE (regno
, FIRST_STACK_REG
, LAST_STACK_REG
))
2710 SET_REGNO_REG_SET (IDATA_REG_USES (id
), FIRST_STACK_REG
);
2715 return_regset_to_pool (tmp
);
2718 /* Initialize instruction data for INSN in ID using DF's data. */
2720 init_id_from_df (idata_t id
, insn_t insn
, bool force_unique_p
)
2722 gcc_assert (DF_INSN_UID_SAFE_GET (INSN_UID (insn
)) != NULL
);
2724 setup_id_for_insn (id
, insn
, force_unique_p
);
2725 setup_id_lhs_rhs (id
, insn
, force_unique_p
);
2727 if (INSN_NOP_P (insn
))
2730 maybe_downgrade_id_to_use (id
, insn
);
2731 setup_id_reg_sets (id
, insn
);
2734 /* Initialize instruction data for INSN in ID. */
2736 deps_init_id (idata_t id
, insn_t insn
, bool force_unique_p
)
2738 struct deps_desc _dc
, *dc
= &_dc
;
2740 deps_init_id_data
.where
= DEPS_IN_NOWHERE
;
2741 deps_init_id_data
.id
= id
;
2742 deps_init_id_data
.force_unique_p
= force_unique_p
;
2743 deps_init_id_data
.force_use_p
= false;
2745 init_deps (dc
, false);
2747 memcpy (&deps_init_id_sched_deps_info
,
2748 &const_deps_init_id_sched_deps_info
,
2749 sizeof (deps_init_id_sched_deps_info
));
2751 if (spec_info
!= NULL
)
2752 deps_init_id_sched_deps_info
.generate_spec_deps
= 1;
2754 sched_deps_info
= &deps_init_id_sched_deps_info
;
2756 deps_analyze_insn (dc
, insn
);
2760 deps_init_id_data
.id
= NULL
;
2764 struct sched_scan_info_def
2766 /* This hook notifies scheduler frontend to extend its internal per basic
2767 block data structures. This hook should be called once before a series of
2768 calls to bb_init (). */
2769 void (*extend_bb
) (void);
2771 /* This hook makes scheduler frontend to initialize its internal data
2772 structures for the passed basic block. */
2773 void (*init_bb
) (basic_block
);
2775 /* This hook notifies scheduler frontend to extend its internal per insn data
2776 structures. This hook should be called once before a series of calls to
2778 void (*extend_insn
) (void);
2780 /* This hook makes scheduler frontend to initialize its internal data
2781 structures for the passed insn. */
2782 void (*init_insn
) (insn_t
);
2785 /* A driver function to add a set of basic blocks (BBS) to the
2786 scheduling region. */
2788 sched_scan (const struct sched_scan_info_def
*ssi
, bb_vec_t bbs
)
2797 FOR_EACH_VEC_ELT (bbs
, i
, bb
)
2800 if (ssi
->extend_insn
)
2801 ssi
->extend_insn ();
2804 FOR_EACH_VEC_ELT (bbs
, i
, bb
)
2808 FOR_BB_INSNS (bb
, insn
)
2809 ssi
->init_insn (insn
);
2813 /* Implement hooks for collecting fundamental insn properties like if insn is
2814 an ASM or is within a SCHED_GROUP. */
2816 /* True when a "one-time init" data for INSN was already inited. */
2818 first_time_insn_init (insn_t insn
)
2820 return INSN_LIVE (insn
) == NULL
;
2823 /* Hash an entry in a transformed_insns hashtable. */
2825 hash_transformed_insns (const void *p
)
2827 return VINSN_HASH_RTX (((const struct transformed_insns
*) p
)->vinsn_old
);
2830 /* Compare the entries in a transformed_insns hashtable. */
2832 eq_transformed_insns (const void *p
, const void *q
)
2835 VINSN_INSN_RTX (((const struct transformed_insns
*) p
)->vinsn_old
);
2837 VINSN_INSN_RTX (((const struct transformed_insns
*) q
)->vinsn_old
);
2839 if (INSN_UID (i1
) == INSN_UID (i2
))
2841 return rtx_equal_p (PATTERN (i1
), PATTERN (i2
));
2844 /* Free an entry in a transformed_insns hashtable. */
2846 free_transformed_insns (void *p
)
2848 struct transformed_insns
*pti
= (struct transformed_insns
*) p
;
2850 vinsn_detach (pti
->vinsn_old
);
2851 vinsn_detach (pti
->vinsn_new
);
2855 /* Init the s_i_d data for INSN which should be inited just once, when
2856 we first see the insn. */
2858 init_first_time_insn_data (insn_t insn
)
2860 /* This should not be set if this is the first time we init data for
2862 gcc_assert (first_time_insn_init (insn
));
2864 /* These are needed for nops too. */
2865 INSN_LIVE (insn
) = get_regset_from_pool ();
2866 INSN_LIVE_VALID_P (insn
) = false;
2868 if (!INSN_NOP_P (insn
))
2870 INSN_ANALYZED_DEPS (insn
) = BITMAP_ALLOC (NULL
);
2871 INSN_FOUND_DEPS (insn
) = BITMAP_ALLOC (NULL
);
2872 INSN_TRANSFORMED_INSNS (insn
)
2873 = htab_create (16, hash_transformed_insns
,
2874 eq_transformed_insns
, free_transformed_insns
);
2875 init_deps (&INSN_DEPS_CONTEXT (insn
), true);
2879 /* Free almost all above data for INSN that is scheduled already.
2880 Used for extra-large basic blocks. */
2882 free_data_for_scheduled_insn (insn_t insn
)
2884 gcc_assert (! first_time_insn_init (insn
));
2886 if (! INSN_ANALYZED_DEPS (insn
))
2889 BITMAP_FREE (INSN_ANALYZED_DEPS (insn
));
2890 BITMAP_FREE (INSN_FOUND_DEPS (insn
));
2891 htab_delete (INSN_TRANSFORMED_INSNS (insn
));
2893 /* This is allocated only for bookkeeping insns. */
2894 if (INSN_ORIGINATORS (insn
))
2895 BITMAP_FREE (INSN_ORIGINATORS (insn
));
2896 free_deps (&INSN_DEPS_CONTEXT (insn
));
2898 INSN_ANALYZED_DEPS (insn
) = NULL
;
2900 /* Clear the readonly flag so we would ICE when trying to recalculate
2901 the deps context (as we believe that it should not happen). */
2902 (&INSN_DEPS_CONTEXT (insn
))->readonly
= 0;
2905 /* Free the same data as above for INSN. */
2907 free_first_time_insn_data (insn_t insn
)
2909 gcc_assert (! first_time_insn_init (insn
));
2911 free_data_for_scheduled_insn (insn
);
2912 return_regset_to_pool (INSN_LIVE (insn
));
2913 INSN_LIVE (insn
) = NULL
;
2914 INSN_LIVE_VALID_P (insn
) = false;
2917 /* Initialize region-scope data structures for basic blocks. */
2919 init_global_and_expr_for_bb (basic_block bb
)
2921 if (sel_bb_empty_p (bb
))
2924 invalidate_av_set (bb
);
2927 /* Data for global dependency analysis (to initialize CANT_MOVE and
2931 /* Previous insn. */
2935 /* Determine if INSN is in the sched_group, is an asm or should not be
2936 cloned. After that initialize its expr. */
2938 init_global_and_expr_for_insn (insn_t insn
)
2943 if (NOTE_INSN_BASIC_BLOCK_P (insn
))
2945 init_global_data
.prev_insn
= NULL
;
2949 gcc_assert (INSN_P (insn
));
2951 if (SCHED_GROUP_P (insn
))
2952 /* Setup a sched_group. */
2954 insn_t prev_insn
= init_global_data
.prev_insn
;
2957 INSN_SCHED_NEXT (prev_insn
) = insn
;
2959 init_global_data
.prev_insn
= insn
;
2962 init_global_data
.prev_insn
= NULL
;
2964 if (GET_CODE (PATTERN (insn
)) == ASM_INPUT
2965 || asm_noperands (PATTERN (insn
)) >= 0)
2966 /* Mark INSN as an asm. */
2967 INSN_ASM_P (insn
) = true;
2970 bool force_unique_p
;
2973 /* Certain instructions cannot be cloned, and frame related insns and
2974 the insn adjacent to NOTE_INSN_EPILOGUE_BEG cannot be moved out of
2976 if (prologue_epilogue_contains (insn
))
2978 if (RTX_FRAME_RELATED_P (insn
))
2979 CANT_MOVE (insn
) = 1;
2983 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
2984 if (REG_NOTE_KIND (note
) == REG_SAVE_NOTE
2985 && ((enum insn_note
) INTVAL (XEXP (note
, 0))
2986 == NOTE_INSN_EPILOGUE_BEG
))
2988 CANT_MOVE (insn
) = 1;
2992 force_unique_p
= true;
2995 if (CANT_MOVE (insn
)
2996 || INSN_ASM_P (insn
)
2997 || SCHED_GROUP_P (insn
)
2999 /* Exception handling insns are always unique. */
3000 || (cfun
->can_throw_non_call_exceptions
&& can_throw_internal (insn
))
3001 /* TRAP_IF though have an INSN code is control_flow_insn_p (). */
3002 || control_flow_insn_p (insn
)
3003 || volatile_insn_p (PATTERN (insn
))
3004 || (targetm
.cannot_copy_insn_p
3005 && targetm
.cannot_copy_insn_p (insn
)))
3006 force_unique_p
= true;
3008 force_unique_p
= false;
3010 if (targetm
.sched
.get_insn_spec_ds
)
3012 spec_done_ds
= targetm
.sched
.get_insn_spec_ds (insn
);
3013 spec_done_ds
= ds_get_max_dep_weak (spec_done_ds
);
3018 /* Initialize INSN's expr. */
3019 init_expr (INSN_EXPR (insn
), vinsn_create (insn
, force_unique_p
), 0,
3020 REG_BR_PROB_BASE
, INSN_PRIORITY (insn
), 0, BLOCK_NUM (insn
),
3021 spec_done_ds
, 0, 0, vNULL
, true,
3022 false, false, false, CANT_MOVE (insn
));
3025 init_first_time_insn_data (insn
);
3028 /* Scan the region and initialize instruction data for basic blocks BBS. */
3030 sel_init_global_and_expr (bb_vec_t bbs
)
3032 /* ??? It would be nice to implement push / pop scheme for sched_infos. */
3033 const struct sched_scan_info_def ssi
=
3035 NULL
, /* extend_bb */
3036 init_global_and_expr_for_bb
, /* init_bb */
3037 extend_insn_data
, /* extend_insn */
3038 init_global_and_expr_for_insn
/* init_insn */
3041 sched_scan (&ssi
, bbs
);
3044 /* Finalize region-scope data structures for basic blocks. */
3046 finish_global_and_expr_for_bb (basic_block bb
)
3048 av_set_clear (&BB_AV_SET (bb
));
3049 BB_AV_LEVEL (bb
) = 0;
3052 /* Finalize INSN's data. */
3054 finish_global_and_expr_insn (insn_t insn
)
3056 if (LABEL_P (insn
) || NOTE_INSN_BASIC_BLOCK_P (insn
))
3059 gcc_assert (INSN_P (insn
));
3061 if (INSN_LUID (insn
) > 0)
3063 free_first_time_insn_data (insn
);
3064 INSN_WS_LEVEL (insn
) = 0;
3065 CANT_MOVE (insn
) = 0;
3067 /* We can no longer assert this, as vinsns of this insn could be
3068 easily live in other insn's caches. This should be changed to
3069 a counter-like approach among all vinsns. */
3070 gcc_assert (true || VINSN_COUNT (INSN_VINSN (insn
)) == 1);
3071 clear_expr (INSN_EXPR (insn
));
3075 /* Finalize per instruction data for the whole region. */
3077 sel_finish_global_and_expr (void)
3083 bbs
.create (current_nr_blocks
);
3085 for (i
= 0; i
< current_nr_blocks
; i
++)
3086 bbs
.quick_push (BASIC_BLOCK_FOR_FN (cfun
, BB_TO_BLOCK (i
)));
3088 /* Clear AV_SETs and INSN_EXPRs. */
3090 const struct sched_scan_info_def ssi
=
3092 NULL
, /* extend_bb */
3093 finish_global_and_expr_for_bb
, /* init_bb */
3094 NULL
, /* extend_insn */
3095 finish_global_and_expr_insn
/* init_insn */
3098 sched_scan (&ssi
, bbs
);
3108 /* In the below hooks, we merely calculate whether or not a dependence
3109 exists, and in what part of insn. However, we will need more data
3110 when we'll start caching dependence requests. */
3112 /* Container to hold information for dependency analysis. */
3117 /* A variable to track which part of rtx we are scanning in
3118 sched-deps.c: sched_analyze_insn (). */
3121 /* Current producer. */
3124 /* Current consumer. */
3127 /* Is SEL_DEPS_HAS_DEP_P[DEPS_IN_X] is true, then X has a dependence.
3128 X is from { INSN, LHS, RHS }. */
3129 ds_t has_dep_p
[DEPS_IN_NOWHERE
];
3130 } has_dependence_data
;
3132 /* Start analyzing dependencies of INSN. */
3134 has_dependence_start_insn (insn_t insn ATTRIBUTE_UNUSED
)
3136 gcc_assert (has_dependence_data
.where
== DEPS_IN_NOWHERE
);
3138 has_dependence_data
.where
= DEPS_IN_INSN
;
3141 /* Finish analyzing dependencies of an insn. */
3143 has_dependence_finish_insn (void)
3145 gcc_assert (has_dependence_data
.where
== DEPS_IN_INSN
);
3147 has_dependence_data
.where
= DEPS_IN_NOWHERE
;
3150 /* Start analyzing dependencies of LHS. */
3152 has_dependence_start_lhs (rtx lhs ATTRIBUTE_UNUSED
)
3154 gcc_assert (has_dependence_data
.where
== DEPS_IN_INSN
);
3156 if (VINSN_LHS (has_dependence_data
.con
) != NULL
)
3157 has_dependence_data
.where
= DEPS_IN_LHS
;
3160 /* Finish analyzing dependencies of an lhs. */
3162 has_dependence_finish_lhs (void)
3164 has_dependence_data
.where
= DEPS_IN_INSN
;
3167 /* Start analyzing dependencies of RHS. */
3169 has_dependence_start_rhs (rtx rhs ATTRIBUTE_UNUSED
)
3171 gcc_assert (has_dependence_data
.where
== DEPS_IN_INSN
);
3173 if (VINSN_RHS (has_dependence_data
.con
) != NULL
)
3174 has_dependence_data
.where
= DEPS_IN_RHS
;
3177 /* Start analyzing dependencies of an rhs. */
3179 has_dependence_finish_rhs (void)
3181 gcc_assert (has_dependence_data
.where
== DEPS_IN_RHS
3182 || has_dependence_data
.where
== DEPS_IN_INSN
);
3184 has_dependence_data
.where
= DEPS_IN_INSN
;
3187 /* Note a set of REGNO. */
3189 has_dependence_note_reg_set (int regno
)
3191 struct deps_reg
*reg_last
= &has_dependence_data
.dc
->reg_last
[regno
];
3193 if (!sched_insns_conditions_mutex_p (has_dependence_data
.pro
,
3195 (has_dependence_data
.con
)))
3197 ds_t
*dsp
= &has_dependence_data
.has_dep_p
[has_dependence_data
.where
];
3199 if (reg_last
->sets
!= NULL
3200 || reg_last
->clobbers
!= NULL
)
3201 *dsp
= (*dsp
& ~SPECULATIVE
) | DEP_OUTPUT
;
3203 if (reg_last
->uses
|| reg_last
->implicit_sets
)
3204 *dsp
= (*dsp
& ~SPECULATIVE
) | DEP_ANTI
;
3208 /* Note a clobber of REGNO. */
3210 has_dependence_note_reg_clobber (int regno
)
3212 struct deps_reg
*reg_last
= &has_dependence_data
.dc
->reg_last
[regno
];
3214 if (!sched_insns_conditions_mutex_p (has_dependence_data
.pro
,
3216 (has_dependence_data
.con
)))
3218 ds_t
*dsp
= &has_dependence_data
.has_dep_p
[has_dependence_data
.where
];
3221 *dsp
= (*dsp
& ~SPECULATIVE
) | DEP_OUTPUT
;
3223 if (reg_last
->uses
|| reg_last
->implicit_sets
)
3224 *dsp
= (*dsp
& ~SPECULATIVE
) | DEP_ANTI
;
3228 /* Note a use of REGNO. */
3230 has_dependence_note_reg_use (int regno
)
3232 struct deps_reg
*reg_last
= &has_dependence_data
.dc
->reg_last
[regno
];
3234 if (!sched_insns_conditions_mutex_p (has_dependence_data
.pro
,
3236 (has_dependence_data
.con
)))
3238 ds_t
*dsp
= &has_dependence_data
.has_dep_p
[has_dependence_data
.where
];
3241 *dsp
= (*dsp
& ~SPECULATIVE
) | DEP_TRUE
;
3243 if (reg_last
->clobbers
|| reg_last
->implicit_sets
)
3244 *dsp
= (*dsp
& ~SPECULATIVE
) | DEP_ANTI
;
3246 /* Merge BE_IN_SPEC bits into *DSP when the dependency producer
3247 is actually a check insn. We need to do this for any register
3248 read-read dependency with the check unless we track properly
3249 all registers written by BE_IN_SPEC-speculated insns, as
3250 we don't have explicit dependence lists. See PR 53975. */
3253 ds_t pro_spec_checked_ds
;
3255 pro_spec_checked_ds
= INSN_SPEC_CHECKED_DS (has_dependence_data
.pro
);
3256 pro_spec_checked_ds
= ds_get_max_dep_weak (pro_spec_checked_ds
);
3258 if (pro_spec_checked_ds
!= 0)
3259 *dsp
= ds_full_merge (*dsp
, pro_spec_checked_ds
,
3260 NULL_RTX
, NULL_RTX
);
3265 /* Note a memory dependence. */
3267 has_dependence_note_mem_dep (rtx mem ATTRIBUTE_UNUSED
,
3268 rtx pending_mem ATTRIBUTE_UNUSED
,
3269 insn_t pending_insn ATTRIBUTE_UNUSED
,
3270 ds_t ds ATTRIBUTE_UNUSED
)
3272 if (!sched_insns_conditions_mutex_p (has_dependence_data
.pro
,
3273 VINSN_INSN_RTX (has_dependence_data
.con
)))
3275 ds_t
*dsp
= &has_dependence_data
.has_dep_p
[has_dependence_data
.where
];
3277 *dsp
= ds_full_merge (ds
, *dsp
, pending_mem
, mem
);
3281 /* Note a dependence. */
3283 has_dependence_note_dep (insn_t pro ATTRIBUTE_UNUSED
,
3284 ds_t ds ATTRIBUTE_UNUSED
)
3286 if (!sched_insns_conditions_mutex_p (has_dependence_data
.pro
,
3287 VINSN_INSN_RTX (has_dependence_data
.con
)))
3289 ds_t
*dsp
= &has_dependence_data
.has_dep_p
[has_dependence_data
.where
];
3291 *dsp
= ds_full_merge (ds
, *dsp
, NULL_RTX
, NULL_RTX
);
3295 /* Mark the insn as having a hard dependence that prevents speculation. */
3297 sel_mark_hard_insn (rtx insn
)
3301 /* Only work when we're in has_dependence_p mode.
3302 ??? This is a hack, this should actually be a hook. */
3303 if (!has_dependence_data
.dc
|| !has_dependence_data
.pro
)
3306 gcc_assert (insn
== VINSN_INSN_RTX (has_dependence_data
.con
));
3307 gcc_assert (has_dependence_data
.where
== DEPS_IN_INSN
);
3309 for (i
= 0; i
< DEPS_IN_NOWHERE
; i
++)
3310 has_dependence_data
.has_dep_p
[i
] &= ~SPECULATIVE
;
3313 /* This structure holds the hooks for the dependency analysis used when
3314 actually processing dependencies in the scheduler. */
3315 static struct sched_deps_info_def has_dependence_sched_deps_info
;
3317 /* This initializes most of the fields of the above structure. */
3318 static const struct sched_deps_info_def const_has_dependence_sched_deps_info
=
3322 has_dependence_start_insn
,
3323 has_dependence_finish_insn
,
3324 has_dependence_start_lhs
,
3325 has_dependence_finish_lhs
,
3326 has_dependence_start_rhs
,
3327 has_dependence_finish_rhs
,
3328 has_dependence_note_reg_set
,
3329 has_dependence_note_reg_clobber
,
3330 has_dependence_note_reg_use
,
3331 has_dependence_note_mem_dep
,
3332 has_dependence_note_dep
,
3335 0, /* use_deps_list */
3336 0 /* generate_spec_deps */
3339 /* Initialize has_dependence_sched_deps_info with extra spec field. */
3341 setup_has_dependence_sched_deps_info (void)
3343 memcpy (&has_dependence_sched_deps_info
,
3344 &const_has_dependence_sched_deps_info
,
3345 sizeof (has_dependence_sched_deps_info
));
3347 if (spec_info
!= NULL
)
3348 has_dependence_sched_deps_info
.generate_spec_deps
= 1;
3350 sched_deps_info
= &has_dependence_sched_deps_info
;
3353 /* Remove all dependences found and recorded in has_dependence_data array. */
3355 sel_clear_has_dependence (void)
3359 for (i
= 0; i
< DEPS_IN_NOWHERE
; i
++)
3360 has_dependence_data
.has_dep_p
[i
] = 0;
3363 /* Return nonzero if EXPR has is dependent upon PRED. Return the pointer
3364 to the dependence information array in HAS_DEP_PP. */
3366 has_dependence_p (expr_t expr
, insn_t pred
, ds_t
**has_dep_pp
)
3370 struct deps_desc
*dc
;
3372 if (INSN_SIMPLEJUMP_P (pred
))
3373 /* Unconditional jump is just a transfer of control flow.
3377 dc
= &INSN_DEPS_CONTEXT (pred
);
3379 /* We init this field lazily. */
3380 if (dc
->reg_last
== NULL
)
3381 init_deps_reg_last (dc
);
3385 has_dependence_data
.pro
= NULL
;
3386 /* Initialize empty dep context with information about PRED. */
3387 advance_deps_context (dc
, pred
);
3391 has_dependence_data
.where
= DEPS_IN_NOWHERE
;
3392 has_dependence_data
.pro
= pred
;
3393 has_dependence_data
.con
= EXPR_VINSN (expr
);
3394 has_dependence_data
.dc
= dc
;
3396 sel_clear_has_dependence ();
3398 /* Now catch all dependencies that would be generated between PRED and
3400 setup_has_dependence_sched_deps_info ();
3401 deps_analyze_insn (dc
, EXPR_INSN_RTX (expr
));
3402 has_dependence_data
.dc
= NULL
;
3404 /* When a barrier was found, set DEPS_IN_INSN bits. */
3405 if (dc
->last_reg_pending_barrier
== TRUE_BARRIER
)
3406 has_dependence_data
.has_dep_p
[DEPS_IN_INSN
] = DEP_TRUE
;
3407 else if (dc
->last_reg_pending_barrier
== MOVE_BARRIER
)
3408 has_dependence_data
.has_dep_p
[DEPS_IN_INSN
] = DEP_ANTI
;
3410 /* Do not allow stores to memory to move through checks. Currently
3411 we don't move this to sched-deps.c as the check doesn't have
3412 obvious places to which this dependence can be attached.
3413 FIMXE: this should go to a hook. */
3415 && MEM_P (EXPR_LHS (expr
))
3416 && sel_insn_is_speculation_check (pred
))
3417 has_dependence_data
.has_dep_p
[DEPS_IN_INSN
] = DEP_ANTI
;
3419 *has_dep_pp
= has_dependence_data
.has_dep_p
;
3421 for (i
= 0; i
< DEPS_IN_NOWHERE
; i
++)
3422 ds
= ds_full_merge (ds
, has_dependence_data
.has_dep_p
[i
],
3423 NULL_RTX
, NULL_RTX
);
3429 /* Dependence hooks implementation that checks dependence latency constraints
3430 on the insns being scheduled. The entry point for these routines is
3431 tick_check_p predicate. */
3435 /* An expr we are currently checking. */
3438 /* A minimal cycle for its scheduling. */
3441 /* Whether we have seen a true dependence while checking. */
3442 bool seen_true_dep_p
;
3445 /* Update minimal scheduling cycle for tick_check_insn given that it depends
3446 on PRO with status DS and weight DW. */
3448 tick_check_dep_with_dw (insn_t pro_insn
, ds_t ds
, dw_t dw
)
3450 expr_t con_expr
= tick_check_data
.expr
;
3451 insn_t con_insn
= EXPR_INSN_RTX (con_expr
);
3453 if (con_insn
!= pro_insn
)
3458 if (/* PROducer was removed from above due to pipelining. */
3459 !INSN_IN_STREAM_P (pro_insn
)
3460 /* Or PROducer was originally on the next iteration regarding the
3462 || (INSN_SCHED_TIMES (pro_insn
)
3463 - EXPR_SCHED_TIMES (con_expr
)) > 1)
3464 /* Don't count this dependence. */
3468 if (dt
== REG_DEP_TRUE
)
3469 tick_check_data
.seen_true_dep_p
= true;
3471 gcc_assert (INSN_SCHED_CYCLE (pro_insn
) > 0);
3474 dep_def _dep
, *dep
= &_dep
;
3476 init_dep (dep
, pro_insn
, con_insn
, dt
);
3478 tick
= INSN_SCHED_CYCLE (pro_insn
) + dep_cost_1 (dep
, dw
);
3481 /* When there are several kinds of dependencies between pro and con,
3482 only REG_DEP_TRUE should be taken into account. */
3483 if (tick
> tick_check_data
.cycle
3484 && (dt
== REG_DEP_TRUE
|| !tick_check_data
.seen_true_dep_p
))
3485 tick_check_data
.cycle
= tick
;
3489 /* An implementation of note_dep hook. */
3491 tick_check_note_dep (insn_t pro
, ds_t ds
)
3493 tick_check_dep_with_dw (pro
, ds
, 0);
3496 /* An implementation of note_mem_dep hook. */
3498 tick_check_note_mem_dep (rtx mem1
, rtx mem2
, insn_t pro
, ds_t ds
)
3502 dw
= (ds_to_dt (ds
) == REG_DEP_TRUE
3503 ? estimate_dep_weak (mem1
, mem2
)
3506 tick_check_dep_with_dw (pro
, ds
, dw
);
3509 /* This structure contains hooks for dependence analysis used when determining
3510 whether an insn is ready for scheduling. */
3511 static struct sched_deps_info_def tick_check_sched_deps_info
=
3522 haifa_note_reg_clobber
,
3524 tick_check_note_mem_dep
,
3525 tick_check_note_dep
,
3530 /* Estimate number of cycles from the current cycle of FENCE until EXPR can be
3531 scheduled. Return 0 if all data from producers in DC is ready. */
3533 tick_check_p (expr_t expr
, deps_t dc
, fence_t fence
)
3536 /* Initialize variables. */
3537 tick_check_data
.expr
= expr
;
3538 tick_check_data
.cycle
= 0;
3539 tick_check_data
.seen_true_dep_p
= false;
3540 sched_deps_info
= &tick_check_sched_deps_info
;
3542 gcc_assert (!dc
->readonly
);
3544 deps_analyze_insn (dc
, EXPR_INSN_RTX (expr
));
3547 cycles_left
= tick_check_data
.cycle
- FENCE_CYCLE (fence
);
3549 return cycles_left
>= 0 ? cycles_left
: 0;
3553 /* Functions to work with insns. */
3555 /* Returns true if LHS of INSN is the same as DEST of an insn
3558 lhs_of_insn_equals_to_dest_p (insn_t insn
, rtx dest
)
3560 rtx lhs
= INSN_LHS (insn
);
3562 if (lhs
== NULL
|| dest
== NULL
)
3565 return rtx_equal_p (lhs
, dest
);
3568 /* Return s_i_d entry of INSN. Callable from debugger. */
3570 insn_sid (insn_t insn
)
3575 /* True when INSN is a speculative check. We can tell this by looking
3576 at the data structures of the selective scheduler, not by examining
3579 sel_insn_is_speculation_check (rtx insn
)
3581 return s_i_d
.exists () && !! INSN_SPEC_CHECKED_DS (insn
);
3584 /* Extracts machine mode MODE and destination location DST_LOC
3587 get_dest_and_mode (rtx insn
, rtx
*dst_loc
, machine_mode
*mode
)
3589 rtx pat
= PATTERN (insn
);
3591 gcc_assert (dst_loc
);
3592 gcc_assert (GET_CODE (pat
) == SET
);
3594 *dst_loc
= SET_DEST (pat
);
3596 gcc_assert (*dst_loc
);
3597 gcc_assert (MEM_P (*dst_loc
) || REG_P (*dst_loc
));
3600 *mode
= GET_MODE (*dst_loc
);
3603 /* Returns true when moving through JUMP will result in bookkeeping
3606 bookkeeping_can_be_created_if_moved_through_p (insn_t jump
)
3611 FOR_EACH_SUCC (succ
, si
, jump
)
3612 if (sel_num_cfg_preds_gt_1 (succ
))
3618 /* Return 'true' if INSN is the only one in its basic block. */
3620 insn_is_the_only_one_in_bb_p (insn_t insn
)
3622 return sel_bb_head_p (insn
) && sel_bb_end_p (insn
);
3625 #ifdef ENABLE_CHECKING
3626 /* Check that the region we're scheduling still has at most one
3629 verify_backedges (void)
3637 for (i
= 0; i
< current_nr_blocks
; i
++)
3638 FOR_EACH_EDGE (e
, ei
, BASIC_BLOCK_FOR_FN (cfun
, BB_TO_BLOCK (i
))->succs
)
3639 if (in_current_region_p (e
->dest
)
3640 && BLOCK_TO_BB (e
->dest
->index
) < i
)
3643 gcc_assert (n
<= 1);
3649 /* Functions to work with control flow. */
3651 /* Recompute BLOCK_TO_BB and BB_FOR_BLOCK for current region so that blocks
3652 are sorted in topological order (it might have been invalidated by
3653 redirecting an edge). */
3655 sel_recompute_toporder (void)
3658 int *postorder
, n_blocks
;
3660 postorder
= XALLOCAVEC (int, n_basic_blocks_for_fn (cfun
));
3661 n_blocks
= post_order_compute (postorder
, false, false);
3663 rgn
= CONTAINING_RGN (BB_TO_BLOCK (0));
3664 for (n
= 0, i
= n_blocks
- 1; i
>= 0; i
--)
3665 if (CONTAINING_RGN (postorder
[i
]) == rgn
)
3667 BLOCK_TO_BB (postorder
[i
]) = n
;
3668 BB_TO_BLOCK (n
) = postorder
[i
];
3672 /* Assert that we updated info for all blocks. We may miss some blocks if
3673 this function is called when redirecting an edge made a block
3674 unreachable, but that block is not deleted yet. */
3675 gcc_assert (n
== RGN_NR_BLOCKS (rgn
));
3678 /* Tidy the possibly empty block BB. */
3680 maybe_tidy_empty_bb (basic_block bb
)
3682 basic_block succ_bb
, pred_bb
, note_bb
;
3683 vec
<basic_block
> dom_bbs
;
3688 /* Keep empty bb only if this block immediately precedes EXIT and
3689 has incoming non-fallthrough edge, or it has no predecessors or
3690 successors. Otherwise remove it. */
3691 if (!sel_bb_empty_p (bb
)
3692 || (single_succ_p (bb
)
3693 && single_succ (bb
) == EXIT_BLOCK_PTR_FOR_FN (cfun
)
3694 && (!single_pred_p (bb
)
3695 || !(single_pred_edge (bb
)->flags
& EDGE_FALLTHRU
)))
3696 || EDGE_COUNT (bb
->preds
) == 0
3697 || EDGE_COUNT (bb
->succs
) == 0)
3700 /* Do not attempt to redirect complex edges. */
3701 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3702 if (e
->flags
& EDGE_COMPLEX
)
3704 else if (e
->flags
& EDGE_FALLTHRU
)
3707 /* If prev bb ends with asm goto, see if any of the
3708 ASM_OPERANDS_LABELs don't point to the fallthru
3709 label. Do not attempt to redirect it in that case. */
3710 if (JUMP_P (BB_END (e
->src
))
3711 && (note
= extract_asm_operands (PATTERN (BB_END (e
->src
)))))
3713 int i
, n
= ASM_OPERANDS_LABEL_LENGTH (note
);
3715 for (i
= 0; i
< n
; ++i
)
3716 if (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) == BB_HEAD (bb
))
3721 free_data_sets (bb
);
3723 /* Do not delete BB if it has more than one successor.
3724 That can occur when we moving a jump. */
3725 if (!single_succ_p (bb
))
3727 gcc_assert (can_merge_blocks_p (bb
->prev_bb
, bb
));
3728 sel_merge_blocks (bb
->prev_bb
, bb
);
3732 succ_bb
= single_succ (bb
);
3737 /* Save a pred/succ from the current region to attach the notes to. */
3739 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3740 if (in_current_region_p (e
->src
))
3745 if (note_bb
== NULL
)
3748 /* Redirect all non-fallthru edges to the next bb. */
3753 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3757 if (!(e
->flags
& EDGE_FALLTHRU
))
3759 /* We can not invalidate computed topological order by moving
3760 the edge destination block (E->SUCC) along a fallthru edge.
3762 We will update dominators here only when we'll get
3763 an unreachable block when redirecting, otherwise
3764 sel_redirect_edge_and_branch will take care of it. */
3766 && single_pred_p (e
->dest
))
3767 dom_bbs
.safe_push (e
->dest
);
3768 sel_redirect_edge_and_branch (e
, succ_bb
);
3772 /* If the edge is fallthru, but PRED_BB ends in a conditional jump
3773 to BB (so there is no non-fallthru edge from PRED_BB to BB), we
3774 still have to adjust it. */
3775 else if (single_succ_p (pred_bb
) && any_condjump_p (BB_END (pred_bb
)))
3777 /* If possible, try to remove the unneeded conditional jump. */
3778 if (INSN_SCHED_TIMES (BB_END (pred_bb
)) == 0
3779 && !IN_CURRENT_FENCE_P (BB_END (pred_bb
)))
3781 if (!sel_remove_insn (BB_END (pred_bb
), false, false))
3782 tidy_fallthru_edge (e
);
3785 sel_redirect_edge_and_branch (e
, succ_bb
);
3792 if (can_merge_blocks_p (bb
->prev_bb
, bb
))
3793 sel_merge_blocks (bb
->prev_bb
, bb
);
3796 /* This is a block without fallthru predecessor. Just delete it. */
3797 gcc_assert (note_bb
);
3798 move_bb_info (note_bb
, bb
);
3799 remove_empty_bb (bb
, true);
3802 if (!dom_bbs
.is_empty ())
3804 dom_bbs
.safe_push (succ_bb
);
3805 iterate_fix_dominators (CDI_DOMINATORS
, dom_bbs
, false);
3812 /* Tidy the control flow after we have removed original insn from
3813 XBB. Return true if we have removed some blocks. When FULL_TIDYING
3814 is true, also try to optimize control flow on non-empty blocks. */
3816 tidy_control_flow (basic_block xbb
, bool full_tidying
)
3818 bool changed
= true;
3821 /* First check whether XBB is empty. */
3822 changed
= maybe_tidy_empty_bb (xbb
);
3823 if (changed
|| !full_tidying
)
3826 /* Check if there is a unnecessary jump after insn left. */
3827 if (bb_has_removable_jump_to_p (xbb
, xbb
->next_bb
)
3828 && INSN_SCHED_TIMES (BB_END (xbb
)) == 0
3829 && !IN_CURRENT_FENCE_P (BB_END (xbb
)))
3831 if (sel_remove_insn (BB_END (xbb
), false, false))
3833 tidy_fallthru_edge (EDGE_SUCC (xbb
, 0));
3836 first
= sel_bb_head (xbb
);
3837 last
= sel_bb_end (xbb
);
3838 if (MAY_HAVE_DEBUG_INSNS
)
3840 if (first
!= last
&& DEBUG_INSN_P (first
))
3842 first
= NEXT_INSN (first
);
3843 while (first
!= last
&& (DEBUG_INSN_P (first
) || NOTE_P (first
)));
3845 if (first
!= last
&& DEBUG_INSN_P (last
))
3847 last
= PREV_INSN (last
);
3848 while (first
!= last
&& (DEBUG_INSN_P (last
) || NOTE_P (last
)));
3850 /* Check if there is an unnecessary jump in previous basic block leading
3851 to next basic block left after removing INSN from stream.
3852 If it is so, remove that jump and redirect edge to current
3853 basic block (where there was INSN before deletion). This way
3854 when NOP will be deleted several instructions later with its
3855 basic block we will not get a jump to next instruction, which
3858 && !sel_bb_empty_p (xbb
)
3859 && INSN_NOP_P (last
)
3860 /* Flow goes fallthru from current block to the next. */
3861 && EDGE_COUNT (xbb
->succs
) == 1
3862 && (EDGE_SUCC (xbb
, 0)->flags
& EDGE_FALLTHRU
)
3863 /* When successor is an EXIT block, it may not be the next block. */
3864 && single_succ (xbb
) != EXIT_BLOCK_PTR_FOR_FN (cfun
)
3865 /* And unconditional jump in previous basic block leads to
3866 next basic block of XBB and this jump can be safely removed. */
3867 && in_current_region_p (xbb
->prev_bb
)
3868 && bb_has_removable_jump_to_p (xbb
->prev_bb
, xbb
->next_bb
)
3869 && INSN_SCHED_TIMES (BB_END (xbb
->prev_bb
)) == 0
3870 /* Also this jump is not at the scheduling boundary. */
3871 && !IN_CURRENT_FENCE_P (BB_END (xbb
->prev_bb
)))
3873 bool recompute_toporder_p
;
3874 /* Clear data structures of jump - jump itself will be removed
3875 by sel_redirect_edge_and_branch. */
3876 clear_expr (INSN_EXPR (BB_END (xbb
->prev_bb
)));
3877 recompute_toporder_p
3878 = sel_redirect_edge_and_branch (EDGE_SUCC (xbb
->prev_bb
, 0), xbb
);
3880 gcc_assert (EDGE_SUCC (xbb
->prev_bb
, 0)->flags
& EDGE_FALLTHRU
);
3882 /* It can turn out that after removing unused jump, basic block
3883 that contained that jump, becomes empty too. In such case
3885 if (sel_bb_empty_p (xbb
->prev_bb
))
3886 changed
= maybe_tidy_empty_bb (xbb
->prev_bb
);
3887 if (recompute_toporder_p
)
3888 sel_recompute_toporder ();
3891 #ifdef ENABLE_CHECKING
3892 verify_backedges ();
3893 verify_dominators (CDI_DOMINATORS
);
3899 /* Purge meaningless empty blocks in the middle of a region. */
3901 purge_empty_blocks (void)
3905 /* Do not attempt to delete the first basic block in the region. */
3906 for (i
= 1; i
< current_nr_blocks
; )
3908 basic_block b
= BASIC_BLOCK_FOR_FN (cfun
, BB_TO_BLOCK (i
));
3910 if (maybe_tidy_empty_bb (b
))
3917 /* Rip-off INSN from the insn stream. When ONLY_DISCONNECT is true,
3918 do not delete insn's data, because it will be later re-emitted.
3919 Return true if we have removed some blocks afterwards. */
3921 sel_remove_insn (insn_t insn
, bool only_disconnect
, bool full_tidying
)
3923 basic_block bb
= BLOCK_FOR_INSN (insn
);
3925 gcc_assert (INSN_IN_STREAM_P (insn
));
3927 if (DEBUG_INSN_P (insn
) && BB_AV_SET_VALID_P (bb
))
3932 /* When we remove a debug insn that is head of a BB, it remains
3933 in the AV_SET of the block, but it shouldn't. */
3934 FOR_EACH_EXPR_1 (expr
, i
, &BB_AV_SET (bb
))
3935 if (EXPR_INSN_RTX (expr
) == insn
)
3937 av_set_iter_remove (&i
);
3942 if (only_disconnect
)
3947 clear_expr (INSN_EXPR (insn
));
3950 /* It is necessary to NULL these fields in case we are going to re-insert
3951 INSN into the insns stream, as will usually happen in the ONLY_DISCONNECT
3952 case, but also for NOPs that we will return to the nop pool. */
3953 SET_PREV_INSN (insn
) = NULL_RTX
;
3954 SET_NEXT_INSN (insn
) = NULL_RTX
;
3955 set_block_for_insn (insn
, NULL
);
3957 return tidy_control_flow (bb
, full_tidying
);
3960 /* Estimate number of the insns in BB. */
3962 sel_estimate_number_of_insns (basic_block bb
)
3965 insn_t insn
= NEXT_INSN (BB_HEAD (bb
)), next_tail
= NEXT_INSN (BB_END (bb
));
3967 for (; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
3968 if (NONDEBUG_INSN_P (insn
))
3974 /* We don't need separate luids for notes or labels. */
3976 sel_luid_for_non_insn (rtx x
)
3978 gcc_assert (NOTE_P (x
) || LABEL_P (x
));
3983 /* Find the proper seqno for inserting at INSN by successors.
3984 Return -1 if no successors with positive seqno exist. */
3986 get_seqno_by_succs (rtx_insn
*insn
)
3988 basic_block bb
= BLOCK_FOR_INSN (insn
);
3989 rtx_insn
*tmp
= insn
, *end
= BB_END (bb
);
3996 tmp
= NEXT_INSN (tmp
);
3998 return INSN_SEQNO (tmp
);
4003 FOR_EACH_SUCC_1 (succ
, si
, end
, SUCCS_NORMAL
)
4004 if (INSN_SEQNO (succ
) > 0)
4005 seqno
= MIN (seqno
, INSN_SEQNO (succ
));
4007 if (seqno
== INT_MAX
)
4013 /* Compute seqno for INSN by its preds or succs. Use OLD_SEQNO to compute
4014 seqno in corner cases. */
4016 get_seqno_for_a_jump (insn_t insn
, int old_seqno
)
4020 gcc_assert (INSN_SIMPLEJUMP_P (insn
));
4022 if (!sel_bb_head_p (insn
))
4023 seqno
= INSN_SEQNO (PREV_INSN (insn
));
4026 basic_block bb
= BLOCK_FOR_INSN (insn
);
4028 if (single_pred_p (bb
)
4029 && !in_current_region_p (single_pred (bb
)))
4031 /* We can have preds outside a region when splitting edges
4032 for pipelining of an outer loop. Use succ instead.
4033 There should be only one of them. */
4038 gcc_assert (flag_sel_sched_pipelining_outer_loops
4039 && current_loop_nest
);
4040 FOR_EACH_SUCC_1 (succ
, si
, insn
,
4041 SUCCS_NORMAL
| SUCCS_SKIP_TO_LOOP_EXITS
)
4047 gcc_assert (succ
!= NULL
);
4048 seqno
= INSN_SEQNO (succ
);
4055 cfg_preds (BLOCK_FOR_INSN (insn
), &preds
, &n
);
4058 /* For one predecessor, use simple method. */
4060 seqno
= INSN_SEQNO (preds
[0]);
4062 seqno
= get_seqno_by_preds (insn
);
4068 /* We were unable to find a good seqno among preds. */
4070 seqno
= get_seqno_by_succs (insn
);
4074 /* The only case where this could be here legally is that the only
4075 unscheduled insn was a conditional jump that got removed and turned
4076 into this unconditional one. Initialize from the old seqno
4077 of that jump passed down to here. */
4081 gcc_assert (seqno
>= 0);
4085 /* Find the proper seqno for inserting at INSN. Returns -1 if no predecessors
4086 with positive seqno exist. */
4088 get_seqno_by_preds (rtx_insn
*insn
)
4090 basic_block bb
= BLOCK_FOR_INSN (insn
);
4091 rtx_insn
*tmp
= insn
, *head
= BB_HEAD (bb
);
4097 tmp
= PREV_INSN (tmp
);
4099 return INSN_SEQNO (tmp
);
4102 cfg_preds (bb
, &preds
, &n
);
4103 for (i
= 0, seqno
= -1; i
< n
; i
++)
4104 seqno
= MAX (seqno
, INSN_SEQNO (preds
[i
]));
4111 /* Extend pass-scope data structures for basic blocks. */
4113 sel_extend_global_bb_info (void)
4115 sel_global_bb_info
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
4118 /* Extend region-scope data structures for basic blocks. */
4120 extend_region_bb_info (void)
4122 sel_region_bb_info
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
4125 /* Extend all data structures to fit for all basic blocks. */
4127 extend_bb_info (void)
4129 sel_extend_global_bb_info ();
4130 extend_region_bb_info ();
4133 /* Finalize pass-scope data structures for basic blocks. */
4135 sel_finish_global_bb_info (void)
4137 sel_global_bb_info
.release ();
4140 /* Finalize region-scope data structures for basic blocks. */
4142 finish_region_bb_info (void)
4144 sel_region_bb_info
.release ();
4148 /* Data for each insn in current region. */
4149 vec
<sel_insn_data_def
> s_i_d
= vNULL
;
4151 /* Extend data structures for insns from current region. */
4153 extend_insn_data (void)
4157 sched_extend_target ();
4158 sched_deps_init (false);
4160 /* Extend data structures for insns from current region. */
4161 reserve
= (sched_max_luid
+ 1 - s_i_d
.length ());
4162 if (reserve
> 0 && ! s_i_d
.space (reserve
))
4166 if (sched_max_luid
/ 2 > 1024)
4167 size
= sched_max_luid
+ 1024;
4169 size
= 3 * sched_max_luid
/ 2;
4172 s_i_d
.safe_grow_cleared (size
);
4176 /* Finalize data structures for insns from current region. */
4182 /* Clear here all dependence contexts that may have left from insns that were
4183 removed during the scheduling. */
4184 for (i
= 0; i
< s_i_d
.length (); i
++)
4186 sel_insn_data_def
*sid_entry
= &s_i_d
[i
];
4188 if (sid_entry
->live
)
4189 return_regset_to_pool (sid_entry
->live
);
4190 if (sid_entry
->analyzed_deps
)
4192 BITMAP_FREE (sid_entry
->analyzed_deps
);
4193 BITMAP_FREE (sid_entry
->found_deps
);
4194 htab_delete (sid_entry
->transformed_insns
);
4195 free_deps (&sid_entry
->deps_context
);
4197 if (EXPR_VINSN (&sid_entry
->expr
))
4199 clear_expr (&sid_entry
->expr
);
4201 /* Also, clear CANT_MOVE bit here, because we really don't want it
4202 to be passed to the next region. */
4203 CANT_MOVE_BY_LUID (i
) = 0;
4210 /* A proxy to pass initialization data to init_insn (). */
4211 static sel_insn_data_def _insn_init_ssid
;
4212 static sel_insn_data_t insn_init_ssid
= &_insn_init_ssid
;
4214 /* If true create a new vinsn. Otherwise use the one from EXPR. */
4215 static bool insn_init_create_new_vinsn_p
;
4217 /* Set all necessary data for initialization of the new insn[s]. */
4219 set_insn_init (expr_t expr
, vinsn_t vi
, int seqno
)
4221 expr_t x
= &insn_init_ssid
->expr
;
4223 copy_expr_onside (x
, expr
);
4226 insn_init_create_new_vinsn_p
= false;
4227 change_vinsn_in_expr (x
, vi
);
4230 insn_init_create_new_vinsn_p
= true;
4232 insn_init_ssid
->seqno
= seqno
;
4236 /* Init data for INSN. */
4238 init_insn_data (insn_t insn
)
4241 sel_insn_data_t ssid
= insn_init_ssid
;
4243 /* The fields mentioned below are special and hence are not being
4244 propagated to the new insns. */
4245 gcc_assert (!ssid
->asm_p
&& ssid
->sched_next
== NULL
4246 && !ssid
->after_stall_p
&& ssid
->sched_cycle
== 0);
4247 gcc_assert (INSN_P (insn
) && INSN_LUID (insn
) > 0);
4249 expr
= INSN_EXPR (insn
);
4250 copy_expr (expr
, &ssid
->expr
);
4251 prepare_insn_expr (insn
, ssid
->seqno
);
4253 if (insn_init_create_new_vinsn_p
)
4254 change_vinsn_in_expr (expr
, vinsn_create (insn
, init_insn_force_unique_p
));
4256 if (first_time_insn_init (insn
))
4257 init_first_time_insn_data (insn
);
4260 /* This is used to initialize spurious jumps generated by
4261 sel_redirect_edge (). OLD_SEQNO is used for initializing seqnos
4262 in corner cases within get_seqno_for_a_jump. */
4264 init_simplejump_data (insn_t insn
, int old_seqno
)
4266 init_expr (INSN_EXPR (insn
), vinsn_create (insn
, false), 0,
4267 REG_BR_PROB_BASE
, 0, 0, 0, 0, 0, 0,
4268 vNULL
, true, false, false,
4270 INSN_SEQNO (insn
) = get_seqno_for_a_jump (insn
, old_seqno
);
4271 init_first_time_insn_data (insn
);
4274 /* Perform deferred initialization of insns. This is used to process
4275 a new jump that may be created by redirect_edge. OLD_SEQNO is used
4276 for initializing simplejumps in init_simplejump_data. */
4278 sel_init_new_insn (insn_t insn
, int flags
, int old_seqno
)
4280 /* We create data structures for bb when the first insn is emitted in it. */
4282 && INSN_IN_STREAM_P (insn
)
4283 && insn_is_the_only_one_in_bb_p (insn
))
4286 create_initial_data_sets (BLOCK_FOR_INSN (insn
));
4289 if (flags
& INSN_INIT_TODO_LUID
)
4291 sched_extend_luids ();
4292 sched_init_insn_luid (insn
);
4295 if (flags
& INSN_INIT_TODO_SSID
)
4297 extend_insn_data ();
4298 init_insn_data (insn
);
4299 clear_expr (&insn_init_ssid
->expr
);
4302 if (flags
& INSN_INIT_TODO_SIMPLEJUMP
)
4304 extend_insn_data ();
4305 init_simplejump_data (insn
, old_seqno
);
4308 gcc_assert (CONTAINING_RGN (BLOCK_NUM (insn
))
4309 == CONTAINING_RGN (BB_TO_BLOCK (0)));
4313 /* Functions to init/finish work with lv sets. */
4315 /* Init BB_LV_SET of BB from DF_LR_IN set of BB. */
4317 init_lv_set (basic_block bb
)
4319 gcc_assert (!BB_LV_SET_VALID_P (bb
));
4321 BB_LV_SET (bb
) = get_regset_from_pool ();
4322 COPY_REG_SET (BB_LV_SET (bb
), DF_LR_IN (bb
));
4323 BB_LV_SET_VALID_P (bb
) = true;
4326 /* Copy liveness information to BB from FROM_BB. */
4328 copy_lv_set_from (basic_block bb
, basic_block from_bb
)
4330 gcc_assert (!BB_LV_SET_VALID_P (bb
));
4332 COPY_REG_SET (BB_LV_SET (bb
), BB_LV_SET (from_bb
));
4333 BB_LV_SET_VALID_P (bb
) = true;
4336 /* Initialize lv set of all bb headers. */
4342 /* Initialize of LV sets. */
4343 FOR_EACH_BB_FN (bb
, cfun
)
4346 /* Don't forget EXIT_BLOCK. */
4347 init_lv_set (EXIT_BLOCK_PTR_FOR_FN (cfun
));
4350 /* Release lv set of HEAD. */
4352 free_lv_set (basic_block bb
)
4354 gcc_assert (BB_LV_SET (bb
) != NULL
);
4356 return_regset_to_pool (BB_LV_SET (bb
));
4357 BB_LV_SET (bb
) = NULL
;
4358 BB_LV_SET_VALID_P (bb
) = false;
4361 /* Finalize lv sets of all bb headers. */
4367 /* Don't forget EXIT_BLOCK. */
4368 free_lv_set (EXIT_BLOCK_PTR_FOR_FN (cfun
));
4371 FOR_EACH_BB_FN (bb
, cfun
)
4376 /* Mark AV_SET for BB as invalid, so this set will be updated the next time
4377 compute_av() processes BB. This function is called when creating new basic
4378 blocks, as well as for blocks (either new or existing) where new jumps are
4379 created when the control flow is being updated. */
4381 invalidate_av_set (basic_block bb
)
4383 BB_AV_LEVEL (bb
) = -1;
4386 /* Create initial data sets for BB (they will be invalid). */
4388 create_initial_data_sets (basic_block bb
)
4391 BB_LV_SET_VALID_P (bb
) = false;
4393 BB_LV_SET (bb
) = get_regset_from_pool ();
4394 invalidate_av_set (bb
);
4397 /* Free av set of BB. */
4399 free_av_set (basic_block bb
)
4401 av_set_clear (&BB_AV_SET (bb
));
4402 BB_AV_LEVEL (bb
) = 0;
4405 /* Free data sets of BB. */
4407 free_data_sets (basic_block bb
)
4413 /* Exchange data sets of TO and FROM. */
4415 exchange_data_sets (basic_block to
, basic_block from
)
4417 /* Exchange lv sets of TO and FROM. */
4418 std::swap (BB_LV_SET (from
), BB_LV_SET (to
));
4419 std::swap (BB_LV_SET_VALID_P (from
), BB_LV_SET_VALID_P (to
));
4421 /* Exchange av sets of TO and FROM. */
4422 std::swap (BB_AV_SET (from
), BB_AV_SET (to
));
4423 std::swap (BB_AV_LEVEL (from
), BB_AV_LEVEL (to
));
4426 /* Copy data sets of FROM to TO. */
4428 copy_data_sets (basic_block to
, basic_block from
)
4430 gcc_assert (!BB_LV_SET_VALID_P (to
) && !BB_AV_SET_VALID_P (to
));
4431 gcc_assert (BB_AV_SET (to
) == NULL
);
4433 BB_AV_LEVEL (to
) = BB_AV_LEVEL (from
);
4434 BB_LV_SET_VALID_P (to
) = BB_LV_SET_VALID_P (from
);
4436 if (BB_AV_SET_VALID_P (from
))
4438 BB_AV_SET (to
) = av_set_copy (BB_AV_SET (from
));
4440 if (BB_LV_SET_VALID_P (from
))
4442 gcc_assert (BB_LV_SET (to
) != NULL
);
4443 COPY_REG_SET (BB_LV_SET (to
), BB_LV_SET (from
));
4447 /* Return an av set for INSN, if any. */
4449 get_av_set (insn_t insn
)
4453 gcc_assert (AV_SET_VALID_P (insn
));
4455 if (sel_bb_head_p (insn
))
4456 av_set
= BB_AV_SET (BLOCK_FOR_INSN (insn
));
4463 /* Implementation of AV_LEVEL () macro. Return AV_LEVEL () of INSN. */
4465 get_av_level (insn_t insn
)
4469 gcc_assert (INSN_P (insn
));
4471 if (sel_bb_head_p (insn
))
4472 av_level
= BB_AV_LEVEL (BLOCK_FOR_INSN (insn
));
4474 av_level
= INSN_WS_LEVEL (insn
);
4481 /* Variables to work with control-flow graph. */
4483 /* The basic block that already has been processed by the sched_data_update (),
4484 but hasn't been in sel_add_bb () yet. */
4485 static vec
<basic_block
>
4486 last_added_blocks
= vNULL
;
4488 /* A pool for allocating successor infos. */
4491 /* A stack for saving succs_info structures. */
4492 struct succs_info
*stack
;
4497 /* Top of the stack. */
4500 /* Maximal value of the top. */
4504 /* Functions to work with control-flow graph. */
4506 /* Return basic block note of BB. */
4508 sel_bb_head (basic_block bb
)
4512 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4514 gcc_assert (exit_insn
!= NULL_RTX
);
4519 rtx_note
*note
= bb_note (bb
);
4520 head
= next_nonnote_insn (note
);
4522 if (head
&& (BARRIER_P (head
) || BLOCK_FOR_INSN (head
) != bb
))
4529 /* Return true if INSN is a basic block header. */
4531 sel_bb_head_p (insn_t insn
)
4533 return sel_bb_head (BLOCK_FOR_INSN (insn
)) == insn
;
4536 /* Return last insn of BB. */
4538 sel_bb_end (basic_block bb
)
4540 if (sel_bb_empty_p (bb
))
4543 gcc_assert (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
4548 /* Return true if INSN is the last insn in its basic block. */
4550 sel_bb_end_p (insn_t insn
)
4552 return insn
== sel_bb_end (BLOCK_FOR_INSN (insn
));
4555 /* Return true if BB consist of single NOTE_INSN_BASIC_BLOCK. */
4557 sel_bb_empty_p (basic_block bb
)
4559 return sel_bb_head (bb
) == NULL
;
4562 /* True when BB belongs to the current scheduling region. */
4564 in_current_region_p (basic_block bb
)
4566 if (bb
->index
< NUM_FIXED_BLOCKS
)
4569 return CONTAINING_RGN (bb
->index
) == CONTAINING_RGN (BB_TO_BLOCK (0));
4572 /* Return the block which is a fallthru bb of a conditional jump JUMP. */
4574 fallthru_bb_of_jump (const rtx_insn
*jump
)
4579 if (!any_condjump_p (jump
))
4582 /* A basic block that ends with a conditional jump may still have one successor
4583 (and be followed by a barrier), we are not interested. */
4584 if (single_succ_p (BLOCK_FOR_INSN (jump
)))
4587 return FALLTHRU_EDGE (BLOCK_FOR_INSN (jump
))->dest
;
4590 /* Remove all notes from BB. */
4592 init_bb (basic_block bb
)
4594 remove_notes (bb_note (bb
), BB_END (bb
));
4595 BB_NOTE_LIST (bb
) = note_list
;
4599 sel_init_bbs (bb_vec_t bbs
)
4601 const struct sched_scan_info_def ssi
=
4603 extend_bb_info
, /* extend_bb */
4604 init_bb
, /* init_bb */
4605 NULL
, /* extend_insn */
4606 NULL
/* init_insn */
4609 sched_scan (&ssi
, bbs
);
4612 /* Restore notes for the whole region. */
4614 sel_restore_notes (void)
4619 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
4621 basic_block first
, last
;
4623 first
= EBB_FIRST_BB (bb
);
4624 last
= EBB_LAST_BB (bb
)->next_bb
;
4628 note_list
= BB_NOTE_LIST (first
);
4629 restore_other_notes (NULL
, first
);
4630 BB_NOTE_LIST (first
) = NULL
;
4632 FOR_BB_INSNS (first
, insn
)
4633 if (NONDEBUG_INSN_P (insn
))
4634 reemit_notes (insn
);
4636 first
= first
->next_bb
;
4638 while (first
!= last
);
4642 /* Free per-bb data structures. */
4644 sel_finish_bbs (void)
4646 sel_restore_notes ();
4648 /* Remove current loop preheader from this loop. */
4649 if (current_loop_nest
)
4650 sel_remove_loop_preheader ();
4652 finish_region_bb_info ();
4655 /* Return true if INSN has a single successor of type FLAGS. */
4657 sel_insn_has_single_succ_p (insn_t insn
, int flags
)
4661 bool first_p
= true;
4663 FOR_EACH_SUCC_1 (succ
, si
, insn
, flags
)
4674 /* Allocate successor's info. */
4675 static struct succs_info
*
4676 alloc_succs_info (void)
4678 if (succs_info_pool
.top
== succs_info_pool
.max_top
)
4682 if (++succs_info_pool
.max_top
>= succs_info_pool
.size
)
4685 i
= ++succs_info_pool
.top
;
4686 succs_info_pool
.stack
[i
].succs_ok
.create (10);
4687 succs_info_pool
.stack
[i
].succs_other
.create (10);
4688 succs_info_pool
.stack
[i
].probs_ok
.create (10);
4691 succs_info_pool
.top
++;
4693 return &succs_info_pool
.stack
[succs_info_pool
.top
];
4696 /* Free successor's info. */
4698 free_succs_info (struct succs_info
* sinfo
)
4700 gcc_assert (succs_info_pool
.top
>= 0
4701 && &succs_info_pool
.stack
[succs_info_pool
.top
] == sinfo
);
4702 succs_info_pool
.top
--;
4704 /* Clear stale info. */
4705 sinfo
->succs_ok
.block_remove (0, sinfo
->succs_ok
.length ());
4706 sinfo
->succs_other
.block_remove (0, sinfo
->succs_other
.length ());
4707 sinfo
->probs_ok
.block_remove (0, sinfo
->probs_ok
.length ());
4708 sinfo
->all_prob
= 0;
4709 sinfo
->succs_ok_n
= 0;
4710 sinfo
->all_succs_n
= 0;
4713 /* Compute successor info for INSN. FLAGS are the flags passed
4714 to the FOR_EACH_SUCC_1 iterator. */
4716 compute_succs_info (insn_t insn
, short flags
)
4720 struct succs_info
*sinfo
= alloc_succs_info ();
4722 /* Traverse *all* successors and decide what to do with each. */
4723 FOR_EACH_SUCC_1 (succ
, si
, insn
, SUCCS_ALL
)
4725 /* FIXME: this doesn't work for skipping to loop exits, as we don't
4726 perform code motion through inner loops. */
4727 short current_flags
= si
.current_flags
& ~SUCCS_SKIP_TO_LOOP_EXITS
;
4729 if (current_flags
& flags
)
4731 sinfo
->succs_ok
.safe_push (succ
);
4732 sinfo
->probs_ok
.safe_push (
4733 /* FIXME: Improve calculation when skipping
4734 inner loop to exits. */
4735 si
.bb_end
? si
.e1
->probability
: REG_BR_PROB_BASE
);
4736 sinfo
->succs_ok_n
++;
4739 sinfo
->succs_other
.safe_push (succ
);
4741 /* Compute all_prob. */
4743 sinfo
->all_prob
= REG_BR_PROB_BASE
;
4745 sinfo
->all_prob
+= si
.e1
->probability
;
4747 sinfo
->all_succs_n
++;
4753 /* Return the predecessors of BB in PREDS and their number in N.
4754 Empty blocks are skipped. SIZE is used to allocate PREDS. */
4756 cfg_preds_1 (basic_block bb
, insn_t
**preds
, int *n
, int *size
)
4761 gcc_assert (BLOCK_TO_BB (bb
->index
) != 0);
4763 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
4765 basic_block pred_bb
= e
->src
;
4766 insn_t bb_end
= BB_END (pred_bb
);
4768 if (!in_current_region_p (pred_bb
))
4770 gcc_assert (flag_sel_sched_pipelining_outer_loops
4771 && current_loop_nest
);
4775 if (sel_bb_empty_p (pred_bb
))
4776 cfg_preds_1 (pred_bb
, preds
, n
, size
);
4780 *preds
= XRESIZEVEC (insn_t
, *preds
,
4781 (*size
= 2 * *size
+ 1));
4782 (*preds
)[(*n
)++] = bb_end
;
4787 || (flag_sel_sched_pipelining_outer_loops
4788 && current_loop_nest
));
4791 /* Find all predecessors of BB and record them in PREDS and their number
4792 in N. Empty blocks are skipped, and only normal (forward in-region)
4793 edges are processed. */
4795 cfg_preds (basic_block bb
, insn_t
**preds
, int *n
)
4801 cfg_preds_1 (bb
, preds
, n
, &size
);
4804 /* Returns true if we are moving INSN through join point. */
4806 sel_num_cfg_preds_gt_1 (insn_t insn
)
4810 if (!sel_bb_head_p (insn
) || INSN_BB (insn
) == 0)
4813 bb
= BLOCK_FOR_INSN (insn
);
4817 if (EDGE_COUNT (bb
->preds
) > 1)
4820 gcc_assert (EDGE_PRED (bb
, 0)->dest
== bb
);
4821 bb
= EDGE_PRED (bb
, 0)->src
;
4823 if (!sel_bb_empty_p (bb
))
4830 /* Returns true when BB should be the end of an ebb. Adapted from the
4831 code in sched-ebb.c. */
4833 bb_ends_ebb_p (basic_block bb
)
4835 basic_block next_bb
= bb_next_bb (bb
);
4838 if (next_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
4839 || bitmap_bit_p (forced_ebb_heads
, next_bb
->index
)
4840 || (LABEL_P (BB_HEAD (next_bb
))
4841 /* NB: LABEL_NUSES () is not maintained outside of jump.c.
4842 Work around that. */
4843 && !single_pred_p (next_bb
)))
4846 if (!in_current_region_p (next_bb
))
4849 e
= find_fallthru_edge (bb
->succs
);
4852 gcc_assert (e
->dest
== next_bb
);
4860 /* Returns true when INSN and SUCC are in the same EBB, given that SUCC is a
4861 successor of INSN. */
4863 in_same_ebb_p (insn_t insn
, insn_t succ
)
4865 basic_block ptr
= BLOCK_FOR_INSN (insn
);
4869 if (ptr
== BLOCK_FOR_INSN (succ
))
4872 if (bb_ends_ebb_p (ptr
))
4875 ptr
= bb_next_bb (ptr
);
4882 /* Recomputes the reverse topological order for the function and
4883 saves it in REV_TOP_ORDER_INDEX. REV_TOP_ORDER_INDEX_LEN is also
4884 modified appropriately. */
4886 recompute_rev_top_order (void)
4891 if (!rev_top_order_index
4892 || rev_top_order_index_len
< last_basic_block_for_fn (cfun
))
4894 rev_top_order_index_len
= last_basic_block_for_fn (cfun
);
4895 rev_top_order_index
= XRESIZEVEC (int, rev_top_order_index
,
4896 rev_top_order_index_len
);
4899 postorder
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
4901 n_blocks
= post_order_compute (postorder
, true, false);
4902 gcc_assert (n_basic_blocks_for_fn (cfun
) == n_blocks
);
4904 /* Build reverse function: for each basic block with BB->INDEX == K
4905 rev_top_order_index[K] is it's reverse topological sort number. */
4906 for (i
= 0; i
< n_blocks
; i
++)
4908 gcc_assert (postorder
[i
] < rev_top_order_index_len
);
4909 rev_top_order_index
[postorder
[i
]] = i
;
4915 /* Clear all flags from insns in BB that could spoil its rescheduling. */
4917 clear_outdated_rtx_info (basic_block bb
)
4921 FOR_BB_INSNS (bb
, insn
)
4924 SCHED_GROUP_P (insn
) = 0;
4925 INSN_AFTER_STALL_P (insn
) = 0;
4926 INSN_SCHED_TIMES (insn
) = 0;
4927 EXPR_PRIORITY_ADJ (INSN_EXPR (insn
)) = 0;
4929 /* We cannot use the changed caches, as previously we could ignore
4930 the LHS dependence due to enabled renaming and transform
4931 the expression, and currently we'll be unable to do this. */
4932 htab_empty (INSN_TRANSFORMED_INSNS (insn
));
4936 /* Add BB_NOTE to the pool of available basic block notes. */
4938 return_bb_to_pool (basic_block bb
)
4940 rtx_note
*note
= bb_note (bb
);
4942 gcc_assert (NOTE_BASIC_BLOCK (note
) == bb
4943 && bb
->aux
== NULL
);
4945 /* It turns out that current cfg infrastructure does not support
4946 reuse of basic blocks. Don't bother for now. */
4947 /*bb_note_pool.safe_push (note);*/
4950 /* Get a bb_note from pool or return NULL_RTX if pool is empty. */
4952 get_bb_note_from_pool (void)
4954 if (bb_note_pool
.is_empty ())
4958 rtx_note
*note
= bb_note_pool
.pop ();
4960 SET_PREV_INSN (note
) = NULL_RTX
;
4961 SET_NEXT_INSN (note
) = NULL_RTX
;
4967 /* Free bb_note_pool. */
4969 free_bb_note_pool (void)
4971 bb_note_pool
.release ();
4974 /* Setup scheduler pool and successor structure. */
4976 alloc_sched_pools (void)
4980 succs_size
= MAX_WS
+ 1;
4981 succs_info_pool
.stack
= XCNEWVEC (struct succs_info
, succs_size
);
4982 succs_info_pool
.size
= succs_size
;
4983 succs_info_pool
.top
= -1;
4984 succs_info_pool
.max_top
= -1;
4987 /* Free the pools. */
4989 free_sched_pools (void)
4993 sched_lists_pool
.release ();
4994 gcc_assert (succs_info_pool
.top
== -1);
4995 for (i
= 0; i
<= succs_info_pool
.max_top
; i
++)
4997 succs_info_pool
.stack
[i
].succs_ok
.release ();
4998 succs_info_pool
.stack
[i
].succs_other
.release ();
4999 succs_info_pool
.stack
[i
].probs_ok
.release ();
5001 free (succs_info_pool
.stack
);
5005 /* Returns a position in RGN where BB can be inserted retaining
5006 topological order. */
5008 find_place_to_insert_bb (basic_block bb
, int rgn
)
5010 bool has_preds_outside_rgn
= false;
5014 /* Find whether we have preds outside the region. */
5015 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
5016 if (!in_current_region_p (e
->src
))
5018 has_preds_outside_rgn
= true;
5022 /* Recompute the top order -- needed when we have > 1 pred
5023 and in case we don't have preds outside. */
5024 if (flag_sel_sched_pipelining_outer_loops
5025 && (has_preds_outside_rgn
|| EDGE_COUNT (bb
->preds
) > 1))
5027 int i
, bbi
= bb
->index
, cur_bbi
;
5029 recompute_rev_top_order ();
5030 for (i
= RGN_NR_BLOCKS (rgn
) - 1; i
>= 0; i
--)
5032 cur_bbi
= BB_TO_BLOCK (i
);
5033 if (rev_top_order_index
[bbi
]
5034 < rev_top_order_index
[cur_bbi
])
5038 /* We skipped the right block, so we increase i. We accommodate
5039 it for increasing by step later, so we decrease i. */
5042 else if (has_preds_outside_rgn
)
5044 /* This is the case when we generate an extra empty block
5045 to serve as region head during pipelining. */
5046 e
= EDGE_SUCC (bb
, 0);
5047 gcc_assert (EDGE_COUNT (bb
->succs
) == 1
5048 && in_current_region_p (EDGE_SUCC (bb
, 0)->dest
)
5049 && (BLOCK_TO_BB (e
->dest
->index
) == 0));
5053 /* We don't have preds outside the region. We should have
5054 the only pred, because the multiple preds case comes from
5055 the pipelining of outer loops, and that is handled above.
5056 Just take the bbi of this single pred. */
5057 if (EDGE_COUNT (bb
->succs
) > 0)
5061 gcc_assert (EDGE_COUNT (bb
->preds
) == 1);
5063 pred_bbi
= EDGE_PRED (bb
, 0)->src
->index
;
5064 return BLOCK_TO_BB (pred_bbi
);
5067 /* BB has no successors. It is safe to put it in the end. */
5068 return current_nr_blocks
- 1;
5071 /* Deletes an empty basic block freeing its data. */
5073 delete_and_free_basic_block (basic_block bb
)
5075 gcc_assert (sel_bb_empty_p (bb
));
5080 bitmap_clear_bit (blocks_to_reschedule
, bb
->index
);
5082 /* Can't assert av_set properties because we use sel_aremove_bb
5083 when removing loop preheader from the region. At the point of
5084 removing the preheader we already have deallocated sel_region_bb_info. */
5085 gcc_assert (BB_LV_SET (bb
) == NULL
5086 && !BB_LV_SET_VALID_P (bb
)
5087 && BB_AV_LEVEL (bb
) == 0
5088 && BB_AV_SET (bb
) == NULL
);
5090 delete_basic_block (bb
);
5093 /* Add BB to the current region and update the region data. */
5095 add_block_to_current_region (basic_block bb
)
5097 int i
, pos
, bbi
= -2, rgn
;
5099 rgn
= CONTAINING_RGN (BB_TO_BLOCK (0));
5100 bbi
= find_place_to_insert_bb (bb
, rgn
);
5102 pos
= RGN_BLOCKS (rgn
) + bbi
;
5104 gcc_assert (RGN_HAS_REAL_EBB (rgn
) == 0
5105 && ebb_head
[bbi
] == pos
);
5107 /* Make a place for the new block. */
5110 for (i
= RGN_BLOCKS (rgn
+ 1) - 1; i
>= pos
; i
--)
5111 BLOCK_TO_BB (rgn_bb_table
[i
])++;
5113 memmove (rgn_bb_table
+ pos
+ 1,
5115 (RGN_BLOCKS (nr_regions
) - pos
) * sizeof (*rgn_bb_table
));
5117 /* Initialize data for BB. */
5118 rgn_bb_table
[pos
] = bb
->index
;
5119 BLOCK_TO_BB (bb
->index
) = bbi
;
5120 CONTAINING_RGN (bb
->index
) = rgn
;
5122 RGN_NR_BLOCKS (rgn
)++;
5124 for (i
= rgn
+ 1; i
<= nr_regions
; i
++)
5128 /* Remove BB from the current region and update the region data. */
5130 remove_bb_from_region (basic_block bb
)
5132 int i
, pos
, bbi
= -2, rgn
;
5134 rgn
= CONTAINING_RGN (BB_TO_BLOCK (0));
5135 bbi
= BLOCK_TO_BB (bb
->index
);
5136 pos
= RGN_BLOCKS (rgn
) + bbi
;
5138 gcc_assert (RGN_HAS_REAL_EBB (rgn
) == 0
5139 && ebb_head
[bbi
] == pos
);
5141 for (i
= RGN_BLOCKS (rgn
+ 1) - 1; i
>= pos
; i
--)
5142 BLOCK_TO_BB (rgn_bb_table
[i
])--;
5144 memmove (rgn_bb_table
+ pos
,
5145 rgn_bb_table
+ pos
+ 1,
5146 (RGN_BLOCKS (nr_regions
) - pos
) * sizeof (*rgn_bb_table
));
5148 RGN_NR_BLOCKS (rgn
)--;
5149 for (i
= rgn
+ 1; i
<= nr_regions
; i
++)
5153 /* Add BB to the current region and update all data. If BB is NULL, add all
5154 blocks from last_added_blocks vector. */
5156 sel_add_bb (basic_block bb
)
5158 /* Extend luids so that new notes will receive zero luids. */
5159 sched_extend_luids ();
5161 sel_init_bbs (last_added_blocks
);
5163 /* When bb is passed explicitly, the vector should contain
5164 the only element that equals to bb; otherwise, the vector
5165 should not be NULL. */
5166 gcc_assert (last_added_blocks
.exists ());
5170 gcc_assert (last_added_blocks
.length () == 1
5171 && last_added_blocks
[0] == bb
);
5172 add_block_to_current_region (bb
);
5174 /* We associate creating/deleting data sets with the first insn
5175 appearing / disappearing in the bb. */
5176 if (!sel_bb_empty_p (bb
) && BB_LV_SET (bb
) == NULL
)
5177 create_initial_data_sets (bb
);
5179 last_added_blocks
.release ();
5182 /* BB is NULL - process LAST_ADDED_BLOCKS instead. */
5185 basic_block temp_bb
= NULL
;
5188 last_added_blocks
.iterate (i
, &bb
); i
++)
5190 add_block_to_current_region (bb
);
5194 /* We need to fetch at least one bb so we know the region
5196 gcc_assert (temp_bb
!= NULL
);
5199 last_added_blocks
.release ();
5202 rgn_setup_region (CONTAINING_RGN (bb
->index
));
5205 /* Remove BB from the current region and update all data.
5206 If REMOVE_FROM_CFG_PBB is true, also remove the block cfom cfg. */
5208 sel_remove_bb (basic_block bb
, bool remove_from_cfg_p
)
5210 unsigned idx
= bb
->index
;
5212 gcc_assert (bb
!= NULL
&& BB_NOTE_LIST (bb
) == NULL_RTX
);
5214 remove_bb_from_region (bb
);
5215 return_bb_to_pool (bb
);
5216 bitmap_clear_bit (blocks_to_reschedule
, idx
);
5218 if (remove_from_cfg_p
)
5220 basic_block succ
= single_succ (bb
);
5221 delete_and_free_basic_block (bb
);
5222 set_immediate_dominator (CDI_DOMINATORS
, succ
,
5223 recompute_dominator (CDI_DOMINATORS
, succ
));
5226 rgn_setup_region (CONTAINING_RGN (idx
));
5229 /* Concatenate info of EMPTY_BB to info of MERGE_BB. */
5231 move_bb_info (basic_block merge_bb
, basic_block empty_bb
)
5233 if (in_current_region_p (merge_bb
))
5234 concat_note_lists (BB_NOTE_LIST (empty_bb
),
5235 &BB_NOTE_LIST (merge_bb
));
5236 BB_NOTE_LIST (empty_bb
) = NULL
;
5240 /* Remove EMPTY_BB. If REMOVE_FROM_CFG_P is false, remove EMPTY_BB from
5241 region, but keep it in CFG. */
5243 remove_empty_bb (basic_block empty_bb
, bool remove_from_cfg_p
)
5245 /* The block should contain just a note or a label.
5246 We try to check whether it is unused below. */
5247 gcc_assert (BB_HEAD (empty_bb
) == BB_END (empty_bb
)
5248 || LABEL_P (BB_HEAD (empty_bb
)));
5250 /* If basic block has predecessors or successors, redirect them. */
5251 if (remove_from_cfg_p
5252 && (EDGE_COUNT (empty_bb
->preds
) > 0
5253 || EDGE_COUNT (empty_bb
->succs
) > 0))
5258 /* We need to init PRED and SUCC before redirecting edges. */
5259 if (EDGE_COUNT (empty_bb
->preds
) > 0)
5263 gcc_assert (EDGE_COUNT (empty_bb
->preds
) == 1);
5265 e
= EDGE_PRED (empty_bb
, 0);
5266 gcc_assert (e
->src
== empty_bb
->prev_bb
5267 && (e
->flags
& EDGE_FALLTHRU
));
5269 pred
= empty_bb
->prev_bb
;
5274 if (EDGE_COUNT (empty_bb
->succs
) > 0)
5276 /* We do not check fallthruness here as above, because
5277 after removing a jump the edge may actually be not fallthru. */
5278 gcc_assert (EDGE_COUNT (empty_bb
->succs
) == 1);
5279 succ
= EDGE_SUCC (empty_bb
, 0)->dest
;
5284 if (EDGE_COUNT (empty_bb
->preds
) > 0 && succ
!= NULL
)
5286 edge e
= EDGE_PRED (empty_bb
, 0);
5288 if (e
->flags
& EDGE_FALLTHRU
)
5289 redirect_edge_succ_nodup (e
, succ
);
5291 sel_redirect_edge_and_branch (EDGE_PRED (empty_bb
, 0), succ
);
5294 if (EDGE_COUNT (empty_bb
->succs
) > 0 && pred
!= NULL
)
5296 edge e
= EDGE_SUCC (empty_bb
, 0);
5298 if (find_edge (pred
, e
->dest
) == NULL
)
5299 redirect_edge_pred (e
, pred
);
5303 /* Finish removing. */
5304 sel_remove_bb (empty_bb
, remove_from_cfg_p
);
5307 /* An implementation of create_basic_block hook, which additionally updates
5308 per-bb data structures. */
5310 sel_create_basic_block (void *headp
, void *endp
, basic_block after
)
5313 rtx_note
*new_bb_note
;
5315 gcc_assert (flag_sel_sched_pipelining_outer_loops
5316 || !last_added_blocks
.exists ());
5318 new_bb_note
= get_bb_note_from_pool ();
5320 if (new_bb_note
== NULL_RTX
)
5321 new_bb
= orig_cfg_hooks
.create_basic_block (headp
, endp
, after
);
5324 new_bb
= create_basic_block_structure ((rtx_insn
*) headp
,
5326 new_bb_note
, after
);
5330 last_added_blocks
.safe_push (new_bb
);
5335 /* Implement sched_init_only_bb (). */
5337 sel_init_only_bb (basic_block bb
, basic_block after
)
5339 gcc_assert (after
== NULL
);
5342 rgn_make_new_region_out_of_new_block (bb
);
5345 /* Update the latch when we've splitted or merged it from FROM block to TO.
5346 This should be checked for all outer loops, too. */
5348 change_loops_latches (basic_block from
, basic_block to
)
5350 gcc_assert (from
!= to
);
5352 if (current_loop_nest
)
5356 for (loop
= current_loop_nest
; loop
; loop
= loop_outer (loop
))
5357 if (considered_for_pipelining_p (loop
) && loop
->latch
== from
)
5359 gcc_assert (loop
== current_loop_nest
);
5361 gcc_assert (loop_latch_edge (loop
));
5366 /* Splits BB on two basic blocks, adding it to the region and extending
5367 per-bb data structures. Returns the newly created bb. */
5369 sel_split_block (basic_block bb
, rtx after
)
5374 new_bb
= sched_split_block_1 (bb
, after
);
5375 sel_add_bb (new_bb
);
5377 /* This should be called after sel_add_bb, because this uses
5378 CONTAINING_RGN for the new block, which is not yet initialized.
5379 FIXME: this function may be a no-op now. */
5380 change_loops_latches (bb
, new_bb
);
5382 /* Update ORIG_BB_INDEX for insns moved into the new block. */
5383 FOR_BB_INSNS (new_bb
, insn
)
5385 EXPR_ORIG_BB_INDEX (INSN_EXPR (insn
)) = new_bb
->index
;
5387 if (sel_bb_empty_p (bb
))
5389 gcc_assert (!sel_bb_empty_p (new_bb
));
5391 /* NEW_BB has data sets that need to be updated and BB holds
5392 data sets that should be removed. Exchange these data sets
5393 so that we won't lose BB's valid data sets. */
5394 exchange_data_sets (new_bb
, bb
);
5395 free_data_sets (bb
);
5398 if (!sel_bb_empty_p (new_bb
)
5399 && bitmap_bit_p (blocks_to_reschedule
, bb
->index
))
5400 bitmap_set_bit (blocks_to_reschedule
, new_bb
->index
);
5405 /* If BB ends with a jump insn whose ID is bigger then PREV_MAX_UID, return it.
5406 Otherwise returns NULL. */
5408 check_for_new_jump (basic_block bb
, int prev_max_uid
)
5412 end
= sel_bb_end (bb
);
5413 if (end
&& INSN_UID (end
) >= prev_max_uid
)
5418 /* Look for a new jump either in FROM_BB block or in newly created JUMP_BB block.
5419 New means having UID at least equal to PREV_MAX_UID. */
5421 find_new_jump (basic_block from
, basic_block jump_bb
, int prev_max_uid
)
5425 /* Return immediately if no new insns were emitted. */
5426 if (get_max_uid () == prev_max_uid
)
5429 /* Now check both blocks for new jumps. It will ever be only one. */
5430 if ((jump
= check_for_new_jump (from
, prev_max_uid
)))
5434 && (jump
= check_for_new_jump (jump_bb
, prev_max_uid
)))
5439 /* Splits E and adds the newly created basic block to the current region.
5440 Returns this basic block. */
5442 sel_split_edge (edge e
)
5444 basic_block new_bb
, src
, other_bb
= NULL
;
5449 prev_max_uid
= get_max_uid ();
5450 new_bb
= split_edge (e
);
5452 if (flag_sel_sched_pipelining_outer_loops
5453 && current_loop_nest
)
5458 /* Some of the basic blocks might not have been added to the loop.
5459 Add them here, until this is fixed in force_fallthru. */
5461 last_added_blocks
.iterate (i
, &bb
); i
++)
5462 if (!bb
->loop_father
)
5464 add_bb_to_loop (bb
, e
->dest
->loop_father
);
5466 gcc_assert (!other_bb
&& (new_bb
->index
!= bb
->index
));
5471 /* Add all last_added_blocks to the region. */
5474 jump
= find_new_jump (src
, new_bb
, prev_max_uid
);
5476 sel_init_new_insn (jump
, INSN_INIT_TODO_LUID
| INSN_INIT_TODO_SIMPLEJUMP
);
5478 /* Put the correct lv set on this block. */
5479 if (other_bb
&& !sel_bb_empty_p (other_bb
))
5480 compute_live (sel_bb_head (other_bb
));
5485 /* Implement sched_create_empty_bb (). */
5487 sel_create_empty_bb (basic_block after
)
5491 new_bb
= sched_create_empty_bb_1 (after
);
5493 /* We'll explicitly initialize NEW_BB via sel_init_only_bb () a bit
5495 gcc_assert (last_added_blocks
.length () == 1
5496 && last_added_blocks
[0] == new_bb
);
5498 last_added_blocks
.release ();
5502 /* Implement sched_create_recovery_block. ORIG_INSN is where block
5503 will be splitted to insert a check. */
5505 sel_create_recovery_block (insn_t orig_insn
)
5507 basic_block first_bb
, second_bb
, recovery_block
;
5508 basic_block before_recovery
= NULL
;
5511 first_bb
= BLOCK_FOR_INSN (orig_insn
);
5512 if (sel_bb_end_p (orig_insn
))
5514 /* Avoid introducing an empty block while splitting. */
5515 gcc_assert (single_succ_p (first_bb
));
5516 second_bb
= single_succ (first_bb
);
5519 second_bb
= sched_split_block (first_bb
, orig_insn
);
5521 recovery_block
= sched_create_recovery_block (&before_recovery
);
5522 if (before_recovery
)
5523 copy_lv_set_from (before_recovery
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
5525 gcc_assert (sel_bb_empty_p (recovery_block
));
5526 sched_create_recovery_edges (first_bb
, recovery_block
, second_bb
);
5527 if (current_loops
!= NULL
)
5528 add_bb_to_loop (recovery_block
, first_bb
->loop_father
);
5530 sel_add_bb (recovery_block
);
5532 jump
= BB_END (recovery_block
);
5533 gcc_assert (sel_bb_head (recovery_block
) == jump
);
5534 sel_init_new_insn (jump
, INSN_INIT_TODO_LUID
| INSN_INIT_TODO_SIMPLEJUMP
);
5536 return recovery_block
;
5539 /* Merge basic block B into basic block A. */
5541 sel_merge_blocks (basic_block a
, basic_block b
)
5543 gcc_assert (sel_bb_empty_p (b
)
5544 && EDGE_COUNT (b
->preds
) == 1
5545 && EDGE_PRED (b
, 0)->src
== b
->prev_bb
);
5547 move_bb_info (b
->prev_bb
, b
);
5548 remove_empty_bb (b
, false);
5549 merge_blocks (a
, b
);
5550 change_loops_latches (b
, a
);
5553 /* A wrapper for redirect_edge_and_branch_force, which also initializes
5554 data structures for possibly created bb and insns. */
5556 sel_redirect_edge_and_branch_force (edge e
, basic_block to
)
5558 basic_block jump_bb
, src
, orig_dest
= e
->dest
;
5563 /* This function is now used only for bookkeeping code creation, where
5564 we'll never get the single pred of orig_dest block and thus will not
5565 hit unreachable blocks when updating dominator info. */
5566 gcc_assert (!sel_bb_empty_p (e
->src
)
5567 && !single_pred_p (orig_dest
));
5569 prev_max_uid
= get_max_uid ();
5570 /* Compute and pass old_seqno down to sel_init_new_insn only for the case
5571 when the conditional jump being redirected may become unconditional. */
5572 if (any_condjump_p (BB_END (src
))
5573 && INSN_SEQNO (BB_END (src
)) >= 0)
5574 old_seqno
= INSN_SEQNO (BB_END (src
));
5576 jump_bb
= redirect_edge_and_branch_force (e
, to
);
5577 if (jump_bb
!= NULL
)
5578 sel_add_bb (jump_bb
);
5580 /* This function could not be used to spoil the loop structure by now,
5581 thus we don't care to update anything. But check it to be sure. */
5582 if (current_loop_nest
5584 gcc_assert (loop_latch_edge (current_loop_nest
));
5586 jump
= find_new_jump (src
, jump_bb
, prev_max_uid
);
5588 sel_init_new_insn (jump
, INSN_INIT_TODO_LUID
| INSN_INIT_TODO_SIMPLEJUMP
,
5590 set_immediate_dominator (CDI_DOMINATORS
, to
,
5591 recompute_dominator (CDI_DOMINATORS
, to
));
5592 set_immediate_dominator (CDI_DOMINATORS
, orig_dest
,
5593 recompute_dominator (CDI_DOMINATORS
, orig_dest
));
5596 /* A wrapper for redirect_edge_and_branch. Return TRUE if blocks connected by
5597 redirected edge are in reverse topological order. */
5599 sel_redirect_edge_and_branch (edge e
, basic_block to
)
5602 basic_block src
, orig_dest
= e
->dest
;
5606 bool recompute_toporder_p
= false;
5607 bool maybe_unreachable
= single_pred_p (orig_dest
);
5610 latch_edge_p
= (pipelining_p
5611 && current_loop_nest
5612 && e
== loop_latch_edge (current_loop_nest
));
5615 prev_max_uid
= get_max_uid ();
5617 /* Compute and pass old_seqno down to sel_init_new_insn only for the case
5618 when the conditional jump being redirected may become unconditional. */
5619 if (any_condjump_p (BB_END (src
))
5620 && INSN_SEQNO (BB_END (src
)) >= 0)
5621 old_seqno
= INSN_SEQNO (BB_END (src
));
5623 redirected
= redirect_edge_and_branch (e
, to
);
5625 gcc_assert (redirected
&& !last_added_blocks
.exists ());
5627 /* When we've redirected a latch edge, update the header. */
5630 current_loop_nest
->header
= to
;
5631 gcc_assert (loop_latch_edge (current_loop_nest
));
5634 /* In rare situations, the topological relation between the blocks connected
5635 by the redirected edge can change (see PR42245 for an example). Update
5636 block_to_bb/bb_to_block. */
5637 if (CONTAINING_RGN (e
->src
->index
) == CONTAINING_RGN (to
->index
)
5638 && BLOCK_TO_BB (e
->src
->index
) > BLOCK_TO_BB (to
->index
))
5639 recompute_toporder_p
= true;
5641 jump
= find_new_jump (src
, NULL
, prev_max_uid
);
5643 sel_init_new_insn (jump
, INSN_INIT_TODO_LUID
| INSN_INIT_TODO_SIMPLEJUMP
, old_seqno
);
5645 /* Only update dominator info when we don't have unreachable blocks.
5646 Otherwise we'll update in maybe_tidy_empty_bb. */
5647 if (!maybe_unreachable
)
5649 set_immediate_dominator (CDI_DOMINATORS
, to
,
5650 recompute_dominator (CDI_DOMINATORS
, to
));
5651 set_immediate_dominator (CDI_DOMINATORS
, orig_dest
,
5652 recompute_dominator (CDI_DOMINATORS
, orig_dest
));
5654 return recompute_toporder_p
;
5657 /* This variable holds the cfg hooks used by the selective scheduler. */
5658 static struct cfg_hooks sel_cfg_hooks
;
5660 /* Register sel-sched cfg hooks. */
5662 sel_register_cfg_hooks (void)
5664 sched_split_block
= sel_split_block
;
5666 orig_cfg_hooks
= get_cfg_hooks ();
5667 sel_cfg_hooks
= orig_cfg_hooks
;
5669 sel_cfg_hooks
.create_basic_block
= sel_create_basic_block
;
5671 set_cfg_hooks (sel_cfg_hooks
);
5673 sched_init_only_bb
= sel_init_only_bb
;
5674 sched_split_block
= sel_split_block
;
5675 sched_create_empty_bb
= sel_create_empty_bb
;
5678 /* Unregister sel-sched cfg hooks. */
5680 sel_unregister_cfg_hooks (void)
5682 sched_create_empty_bb
= NULL
;
5683 sched_split_block
= NULL
;
5684 sched_init_only_bb
= NULL
;
5686 set_cfg_hooks (orig_cfg_hooks
);
5690 /* Emit an insn rtx based on PATTERN. If a jump insn is wanted,
5691 LABEL is where this jump should be directed. */
5693 create_insn_rtx_from_pattern (rtx pattern
, rtx label
)
5697 gcc_assert (!INSN_P (pattern
));
5701 if (label
== NULL_RTX
)
5702 insn_rtx
= emit_insn (pattern
);
5703 else if (DEBUG_INSN_P (label
))
5704 insn_rtx
= emit_debug_insn (pattern
);
5707 insn_rtx
= emit_jump_insn (pattern
);
5708 JUMP_LABEL (insn_rtx
) = label
;
5709 ++LABEL_NUSES (label
);
5714 sched_extend_luids ();
5715 sched_extend_target ();
5716 sched_deps_init (false);
5718 /* Initialize INSN_CODE now. */
5719 recog_memoized (insn_rtx
);
5723 /* Create a new vinsn for INSN_RTX. FORCE_UNIQUE_P is true when the vinsn
5724 must not be clonable. */
5726 create_vinsn_from_insn_rtx (rtx_insn
*insn_rtx
, bool force_unique_p
)
5728 gcc_assert (INSN_P (insn_rtx
) && !INSN_IN_STREAM_P (insn_rtx
));
5730 /* If VINSN_TYPE is not USE, retain its uniqueness. */
5731 return vinsn_create (insn_rtx
, force_unique_p
);
5734 /* Create a copy of INSN_RTX. */
5736 create_copy_of_insn_rtx (rtx insn_rtx
)
5741 if (DEBUG_INSN_P (insn_rtx
))
5742 return create_insn_rtx_from_pattern (copy_rtx (PATTERN (insn_rtx
)),
5745 gcc_assert (NONJUMP_INSN_P (insn_rtx
));
5747 res
= create_insn_rtx_from_pattern (copy_rtx (PATTERN (insn_rtx
)),
5750 /* Copy all REG_NOTES except REG_EQUAL/REG_EQUIV and REG_LABEL_OPERAND
5751 since mark_jump_label will make them. REG_LABEL_TARGETs are created
5752 there too, but are supposed to be sticky, so we copy them. */
5753 for (link
= REG_NOTES (insn_rtx
); link
; link
= XEXP (link
, 1))
5754 if (REG_NOTE_KIND (link
) != REG_LABEL_OPERAND
5755 && REG_NOTE_KIND (link
) != REG_EQUAL
5756 && REG_NOTE_KIND (link
) != REG_EQUIV
)
5758 if (GET_CODE (link
) == EXPR_LIST
)
5759 add_reg_note (res
, REG_NOTE_KIND (link
),
5760 copy_insn_1 (XEXP (link
, 0)));
5762 add_reg_note (res
, REG_NOTE_KIND (link
), XEXP (link
, 0));
5768 /* Change vinsn field of EXPR to hold NEW_VINSN. */
5770 change_vinsn_in_expr (expr_t expr
, vinsn_t new_vinsn
)
5772 vinsn_detach (EXPR_VINSN (expr
));
5774 EXPR_VINSN (expr
) = new_vinsn
;
5775 vinsn_attach (new_vinsn
);
5778 /* Helpers for global init. */
5779 /* This structure is used to be able to call existing bundling mechanism
5780 and calculate insn priorities. */
5781 static struct haifa_sched_info sched_sel_haifa_sched_info
=
5783 NULL
, /* init_ready_list */
5784 NULL
, /* can_schedule_ready_p */
5785 NULL
, /* schedule_more_p */
5786 NULL
, /* new_ready */
5787 NULL
, /* rgn_rank */
5788 sel_print_insn
, /* rgn_print_insn */
5789 contributes_to_priority
,
5790 NULL
, /* insn_finishes_block_p */
5796 NULL
, /* add_remove_insn */
5797 NULL
, /* begin_schedule_ready */
5798 NULL
, /* begin_move_insn */
5799 NULL
, /* advance_target_bb */
5807 /* Setup special insns used in the scheduler. */
5809 setup_nop_and_exit_insns (void)
5811 gcc_assert (nop_pattern
== NULL_RTX
5812 && exit_insn
== NULL_RTX
);
5814 nop_pattern
= constm1_rtx
;
5817 emit_insn (nop_pattern
);
5818 exit_insn
= get_insns ();
5820 set_block_for_insn (exit_insn
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
5823 /* Free special insns used in the scheduler. */
5825 free_nop_and_exit_insns (void)
5828 nop_pattern
= NULL_RTX
;
5831 /* Setup a special vinsn used in new insns initialization. */
5833 setup_nop_vinsn (void)
5835 nop_vinsn
= vinsn_create (exit_insn
, false);
5836 vinsn_attach (nop_vinsn
);
5839 /* Free a special vinsn used in new insns initialization. */
5841 free_nop_vinsn (void)
5843 gcc_assert (VINSN_COUNT (nop_vinsn
) == 1);
5844 vinsn_detach (nop_vinsn
);
5848 /* Call a set_sched_flags hook. */
5850 sel_set_sched_flags (void)
5852 /* ??? This means that set_sched_flags were called, and we decided to
5853 support speculation. However, set_sched_flags also modifies flags
5854 on current_sched_info, doing this only at global init. And we
5855 sometimes change c_s_i later. So put the correct flags again. */
5856 if (spec_info
&& targetm
.sched
.set_sched_flags
)
5857 targetm
.sched
.set_sched_flags (spec_info
);
5860 /* Setup pointers to global sched info structures. */
5862 sel_setup_sched_infos (void)
5864 rgn_setup_common_sched_info ();
5866 memcpy (&sel_common_sched_info
, common_sched_info
,
5867 sizeof (sel_common_sched_info
));
5869 sel_common_sched_info
.fix_recovery_cfg
= NULL
;
5870 sel_common_sched_info
.add_block
= NULL
;
5871 sel_common_sched_info
.estimate_number_of_insns
5872 = sel_estimate_number_of_insns
;
5873 sel_common_sched_info
.luid_for_non_insn
= sel_luid_for_non_insn
;
5874 sel_common_sched_info
.sched_pass_id
= SCHED_SEL_PASS
;
5876 common_sched_info
= &sel_common_sched_info
;
5878 current_sched_info
= &sched_sel_haifa_sched_info
;
5879 current_sched_info
->sched_max_insns_priority
=
5880 get_rgn_sched_max_insns_priority ();
5882 sel_set_sched_flags ();
5886 /* Adds basic block BB to region RGN at the position *BB_ORD_INDEX,
5887 *BB_ORD_INDEX after that is increased. */
5889 sel_add_block_to_region (basic_block bb
, int *bb_ord_index
, int rgn
)
5891 RGN_NR_BLOCKS (rgn
) += 1;
5892 RGN_DONT_CALC_DEPS (rgn
) = 0;
5893 RGN_HAS_REAL_EBB (rgn
) = 0;
5894 CONTAINING_RGN (bb
->index
) = rgn
;
5895 BLOCK_TO_BB (bb
->index
) = *bb_ord_index
;
5896 rgn_bb_table
[RGN_BLOCKS (rgn
) + *bb_ord_index
] = bb
->index
;
5899 /* FIXME: it is true only when not scheduling ebbs. */
5900 RGN_BLOCKS (rgn
+ 1) = RGN_BLOCKS (rgn
) + RGN_NR_BLOCKS (rgn
);
5903 /* Functions to support pipelining of outer loops. */
5905 /* Creates a new empty region and returns it's number. */
5907 sel_create_new_region (void)
5909 int new_rgn_number
= nr_regions
;
5911 RGN_NR_BLOCKS (new_rgn_number
) = 0;
5913 /* FIXME: This will work only when EBBs are not created. */
5914 if (new_rgn_number
!= 0)
5915 RGN_BLOCKS (new_rgn_number
) = RGN_BLOCKS (new_rgn_number
- 1) +
5916 RGN_NR_BLOCKS (new_rgn_number
- 1);
5918 RGN_BLOCKS (new_rgn_number
) = 0;
5920 /* Set the blocks of the next region so the other functions may
5921 calculate the number of blocks in the region. */
5922 RGN_BLOCKS (new_rgn_number
+ 1) = RGN_BLOCKS (new_rgn_number
) +
5923 RGN_NR_BLOCKS (new_rgn_number
);
5927 return new_rgn_number
;
5930 /* If X has a smaller topological sort number than Y, returns -1;
5931 if greater, returns 1. */
5933 bb_top_order_comparator (const void *x
, const void *y
)
5935 basic_block bb1
= *(const basic_block
*) x
;
5936 basic_block bb2
= *(const basic_block
*) y
;
5938 gcc_assert (bb1
== bb2
5939 || rev_top_order_index
[bb1
->index
]
5940 != rev_top_order_index
[bb2
->index
]);
5942 /* It's a reverse topological order in REV_TOP_ORDER_INDEX, so
5943 bbs with greater number should go earlier. */
5944 if (rev_top_order_index
[bb1
->index
] > rev_top_order_index
[bb2
->index
])
5950 /* Create a region for LOOP and return its number. If we don't want
5951 to pipeline LOOP, return -1. */
5953 make_region_from_loop (struct loop
*loop
)
5956 int new_rgn_number
= -1;
5959 /* Basic block index, to be assigned to BLOCK_TO_BB. */
5960 int bb_ord_index
= 0;
5961 basic_block
*loop_blocks
;
5962 basic_block preheader_block
;
5965 > (unsigned) PARAM_VALUE (PARAM_MAX_PIPELINE_REGION_BLOCKS
))
5968 /* Don't pipeline loops whose latch belongs to some of its inner loops. */
5969 for (inner
= loop
->inner
; inner
; inner
= inner
->inner
)
5970 if (flow_bb_inside_loop_p (inner
, loop
->latch
))
5973 loop
->ninsns
= num_loop_insns (loop
);
5974 if ((int) loop
->ninsns
> PARAM_VALUE (PARAM_MAX_PIPELINE_REGION_INSNS
))
5977 loop_blocks
= get_loop_body_in_custom_order (loop
, bb_top_order_comparator
);
5979 for (i
= 0; i
< loop
->num_nodes
; i
++)
5980 if (loop_blocks
[i
]->flags
& BB_IRREDUCIBLE_LOOP
)
5986 preheader_block
= loop_preheader_edge (loop
)->src
;
5987 gcc_assert (preheader_block
);
5988 gcc_assert (loop_blocks
[0] == loop
->header
);
5990 new_rgn_number
= sel_create_new_region ();
5992 sel_add_block_to_region (preheader_block
, &bb_ord_index
, new_rgn_number
);
5993 bitmap_set_bit (bbs_in_loop_rgns
, preheader_block
->index
);
5995 for (i
= 0; i
< loop
->num_nodes
; i
++)
5997 /* Add only those blocks that haven't been scheduled in the inner loop.
5998 The exception is the basic blocks with bookkeeping code - they should
5999 be added to the region (and they actually don't belong to the loop
6000 body, but to the region containing that loop body). */
6002 gcc_assert (new_rgn_number
>= 0);
6004 if (! bitmap_bit_p (bbs_in_loop_rgns
, loop_blocks
[i
]->index
))
6006 sel_add_block_to_region (loop_blocks
[i
], &bb_ord_index
,
6008 bitmap_set_bit (bbs_in_loop_rgns
, loop_blocks
[i
]->index
);
6013 MARK_LOOP_FOR_PIPELINING (loop
);
6015 return new_rgn_number
;
6018 /* Create a new region from preheader blocks LOOP_BLOCKS. */
6020 make_region_from_loop_preheader (vec
<basic_block
> *&loop_blocks
)
6023 int new_rgn_number
= -1;
6026 /* Basic block index, to be assigned to BLOCK_TO_BB. */
6027 int bb_ord_index
= 0;
6029 new_rgn_number
= sel_create_new_region ();
6031 FOR_EACH_VEC_ELT (*loop_blocks
, i
, bb
)
6033 gcc_assert (new_rgn_number
>= 0);
6035 sel_add_block_to_region (bb
, &bb_ord_index
, new_rgn_number
);
6038 vec_free (loop_blocks
);
6042 /* Create region(s) from loop nest LOOP, such that inner loops will be
6043 pipelined before outer loops. Returns true when a region for LOOP
6046 make_regions_from_loop_nest (struct loop
*loop
)
6048 struct loop
*cur_loop
;
6051 /* Traverse all inner nodes of the loop. */
6052 for (cur_loop
= loop
->inner
; cur_loop
; cur_loop
= cur_loop
->next
)
6053 if (! bitmap_bit_p (bbs_in_loop_rgns
, cur_loop
->header
->index
))
6056 /* At this moment all regular inner loops should have been pipelined.
6057 Try to create a region from this loop. */
6058 rgn_number
= make_region_from_loop (loop
);
6063 loop_nests
.safe_push (loop
);
6067 /* Initalize data structures needed. */
6069 sel_init_pipelining (void)
6071 /* Collect loop information to be used in outer loops pipelining. */
6072 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
6073 | LOOPS_HAVE_FALLTHRU_PREHEADERS
6074 | LOOPS_HAVE_RECORDED_EXITS
6075 | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
);
6076 current_loop_nest
= NULL
;
6078 bbs_in_loop_rgns
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
6079 bitmap_clear (bbs_in_loop_rgns
);
6081 recompute_rev_top_order ();
6084 /* Returns a struct loop for region RGN. */
6086 get_loop_nest_for_rgn (unsigned int rgn
)
6088 /* Regions created with extend_rgns don't have corresponding loop nests,
6089 because they don't represent loops. */
6090 if (rgn
< loop_nests
.length ())
6091 return loop_nests
[rgn
];
6096 /* True when LOOP was included into pipelining regions. */
6098 considered_for_pipelining_p (struct loop
*loop
)
6100 if (loop_depth (loop
) == 0)
6103 /* Now, the loop could be too large or irreducible. Check whether its
6104 region is in LOOP_NESTS.
6105 We determine the region number of LOOP as the region number of its
6106 latch. We can't use header here, because this header could be
6107 just removed preheader and it will give us the wrong region number.
6108 Latch can't be used because it could be in the inner loop too. */
6109 if (LOOP_MARKED_FOR_PIPELINING_P (loop
))
6111 int rgn
= CONTAINING_RGN (loop
->latch
->index
);
6113 gcc_assert ((unsigned) rgn
< loop_nests
.length ());
6120 /* Makes regions from the rest of the blocks, after loops are chosen
6123 make_regions_from_the_rest (void)
6134 /* Index in rgn_bb_table where to start allocating new regions. */
6135 cur_rgn_blocks
= nr_regions
? RGN_BLOCKS (nr_regions
) : 0;
6137 /* Make regions from all the rest basic blocks - those that don't belong to
6138 any loop or belong to irreducible loops. Prepare the data structures
6141 /* LOOP_HDR[I] == -1 if I-th bb doesn't belong to any loop,
6142 LOOP_HDR[I] == LOOP_HDR[J] iff basic blocks I and J reside within the same
6144 loop_hdr
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
6145 degree
= XCNEWVEC (int, last_basic_block_for_fn (cfun
));
6148 /* For each basic block that belongs to some loop assign the number
6149 of innermost loop it belongs to. */
6150 for (i
= 0; i
< last_basic_block_for_fn (cfun
); i
++)
6153 FOR_EACH_BB_FN (bb
, cfun
)
6155 if (bb
->loop_father
&& bb
->loop_father
->num
!= 0
6156 && !(bb
->flags
& BB_IRREDUCIBLE_LOOP
))
6157 loop_hdr
[bb
->index
] = bb
->loop_father
->num
;
6160 /* For each basic block degree is calculated as the number of incoming
6161 edges, that are going out of bbs that are not yet scheduled.
6162 The basic blocks that are scheduled have degree value of zero. */
6163 FOR_EACH_BB_FN (bb
, cfun
)
6165 degree
[bb
->index
] = 0;
6167 if (!bitmap_bit_p (bbs_in_loop_rgns
, bb
->index
))
6169 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
6170 if (!bitmap_bit_p (bbs_in_loop_rgns
, e
->src
->index
))
6171 degree
[bb
->index
]++;
6174 degree
[bb
->index
] = -1;
6177 extend_rgns (degree
, &cur_rgn_blocks
, bbs_in_loop_rgns
, loop_hdr
);
6179 /* Any block that did not end up in a region is placed into a region
6181 FOR_EACH_BB_FN (bb
, cfun
)
6182 if (degree
[bb
->index
] >= 0)
6184 rgn_bb_table
[cur_rgn_blocks
] = bb
->index
;
6185 RGN_NR_BLOCKS (nr_regions
) = 1;
6186 RGN_BLOCKS (nr_regions
) = cur_rgn_blocks
++;
6187 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
6188 RGN_HAS_REAL_EBB (nr_regions
) = 0;
6189 CONTAINING_RGN (bb
->index
) = nr_regions
++;
6190 BLOCK_TO_BB (bb
->index
) = 0;
6197 /* Free data structures used in pipelining of loops. */
6198 void sel_finish_pipelining (void)
6202 /* Release aux fields so we don't free them later by mistake. */
6203 FOR_EACH_LOOP (loop
, 0)
6206 loop_optimizer_finalize ();
6208 loop_nests
.release ();
6210 free (rev_top_order_index
);
6211 rev_top_order_index
= NULL
;
6214 /* This function replaces the find_rgns when
6215 FLAG_SEL_SCHED_PIPELINING_OUTER_LOOPS is set. */
6217 sel_find_rgns (void)
6219 sel_init_pipelining ();
6226 FOR_EACH_LOOP (loop
, (flag_sel_sched_pipelining_outer_loops
6228 : LI_ONLY_INNERMOST
))
6229 make_regions_from_loop_nest (loop
);
6232 /* Make regions from all the rest basic blocks and schedule them.
6233 These blocks include blocks that don't belong to any loop or belong
6234 to irreducible loops. */
6235 make_regions_from_the_rest ();
6237 /* We don't need bbs_in_loop_rgns anymore. */
6238 sbitmap_free (bbs_in_loop_rgns
);
6239 bbs_in_loop_rgns
= NULL
;
6242 /* Add the preheader blocks from previous loop to current region taking
6243 it from LOOP_PREHEADER_BLOCKS (current_loop_nest) and record them in *BBS.
6244 This function is only used with -fsel-sched-pipelining-outer-loops. */
6246 sel_add_loop_preheaders (bb_vec_t
*bbs
)
6250 vec
<basic_block
> *preheader_blocks
6251 = LOOP_PREHEADER_BLOCKS (current_loop_nest
);
6253 if (!preheader_blocks
)
6256 for (i
= 0; preheader_blocks
->iterate (i
, &bb
); i
++)
6258 bbs
->safe_push (bb
);
6259 last_added_blocks
.safe_push (bb
);
6263 vec_free (preheader_blocks
);
6266 /* While pipelining outer loops, returns TRUE if BB is a loop preheader.
6267 Please note that the function should also work when pipelining_p is
6268 false, because it is used when deciding whether we should or should
6269 not reschedule pipelined code. */
6271 sel_is_loop_preheader_p (basic_block bb
)
6273 if (current_loop_nest
)
6277 if (preheader_removed
)
6280 /* Preheader is the first block in the region. */
6281 if (BLOCK_TO_BB (bb
->index
) == 0)
6284 /* We used to find a preheader with the topological information.
6285 Check that the above code is equivalent to what we did before. */
6287 if (in_current_region_p (current_loop_nest
->header
))
6288 gcc_assert (!(BLOCK_TO_BB (bb
->index
)
6289 < BLOCK_TO_BB (current_loop_nest
->header
->index
)));
6291 /* Support the situation when the latch block of outer loop
6292 could be from here. */
6293 for (outer
= loop_outer (current_loop_nest
);
6295 outer
= loop_outer (outer
))
6296 if (considered_for_pipelining_p (outer
) && outer
->latch
== bb
)
6303 /* Check whether JUMP_BB ends with a jump insn that leads only to DEST_BB and
6304 can be removed, making the corresponding edge fallthrough (assuming that
6305 all basic blocks between JUMP_BB and DEST_BB are empty). */
6307 bb_has_removable_jump_to_p (basic_block jump_bb
, basic_block dest_bb
)
6309 if (!onlyjump_p (BB_END (jump_bb
))
6310 || tablejump_p (BB_END (jump_bb
), NULL
, NULL
))
6313 /* Several outgoing edges, abnormal edge or destination of jump is
6315 if (EDGE_COUNT (jump_bb
->succs
) != 1
6316 || EDGE_SUCC (jump_bb
, 0)->flags
& (EDGE_ABNORMAL
| EDGE_CROSSING
)
6317 || EDGE_SUCC (jump_bb
, 0)->dest
!= dest_bb
)
6320 /* If not anything of the upper. */
6324 /* Removes the loop preheader from the current region and saves it in
6325 PREHEADER_BLOCKS of the father loop, so they will be added later to
6326 region that represents an outer loop. */
6328 sel_remove_loop_preheader (void)
6331 int cur_rgn
= CONTAINING_RGN (BB_TO_BLOCK (0));
6333 bool all_empty_p
= true;
6334 vec
<basic_block
> *preheader_blocks
6335 = LOOP_PREHEADER_BLOCKS (loop_outer (current_loop_nest
));
6337 vec_check_alloc (preheader_blocks
, 0);
6339 gcc_assert (current_loop_nest
);
6340 old_len
= preheader_blocks
->length ();
6342 /* Add blocks that aren't within the current loop to PREHEADER_BLOCKS. */
6343 for (i
= 0; i
< RGN_NR_BLOCKS (cur_rgn
); i
++)
6345 bb
= BASIC_BLOCK_FOR_FN (cfun
, BB_TO_BLOCK (i
));
6347 /* If the basic block belongs to region, but doesn't belong to
6348 corresponding loop, then it should be a preheader. */
6349 if (sel_is_loop_preheader_p (bb
))
6351 preheader_blocks
->safe_push (bb
);
6352 if (BB_END (bb
) != bb_note (bb
))
6353 all_empty_p
= false;
6357 /* Remove these blocks only after iterating over the whole region. */
6358 for (i
= preheader_blocks
->length () - 1; i
>= old_len
; i
--)
6360 bb
= (*preheader_blocks
)[i
];
6361 sel_remove_bb (bb
, false);
6364 if (!considered_for_pipelining_p (loop_outer (current_loop_nest
)))
6367 /* Immediately create new region from preheader. */
6368 make_region_from_loop_preheader (preheader_blocks
);
6371 /* If all preheader blocks are empty - dont create new empty region.
6372 Instead, remove them completely. */
6373 FOR_EACH_VEC_ELT (*preheader_blocks
, i
, bb
)
6377 basic_block prev_bb
= bb
->prev_bb
, next_bb
= bb
->next_bb
;
6379 /* Redirect all incoming edges to next basic block. */
6380 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
6382 if (! (e
->flags
& EDGE_FALLTHRU
))
6383 redirect_edge_and_branch (e
, bb
->next_bb
);
6385 redirect_edge_succ (e
, bb
->next_bb
);
6387 gcc_assert (BB_NOTE_LIST (bb
) == NULL
);
6388 delete_and_free_basic_block (bb
);
6390 /* Check if after deleting preheader there is a nonconditional
6391 jump in PREV_BB that leads to the next basic block NEXT_BB.
6392 If it is so - delete this jump and clear data sets of its
6393 basic block if it becomes empty. */
6394 if (next_bb
->prev_bb
== prev_bb
6395 && prev_bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
6396 && bb_has_removable_jump_to_p (prev_bb
, next_bb
))
6398 redirect_edge_and_branch (EDGE_SUCC (prev_bb
, 0), next_bb
);
6399 if (BB_END (prev_bb
) == bb_note (prev_bb
))
6400 free_data_sets (prev_bb
);
6403 set_immediate_dominator (CDI_DOMINATORS
, next_bb
,
6404 recompute_dominator (CDI_DOMINATORS
,
6408 vec_free (preheader_blocks
);
6411 /* Store preheader within the father's loop structure. */
6412 SET_LOOP_PREHEADER_BLOCKS (loop_outer (current_loop_nest
),