1 /* Instruction scheduling pass. Selective scheduler and pipeliner.
2 Copyright (C) 2006-2019 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
33 #include "insn-config.h"
34 #include "insn-attr.h"
38 #include "sched-int.h"
39 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
41 #ifdef INSN_SCHEDULING
44 #include "sel-sched-ir.h"
45 /* We don't have to use it except for sel_print_insn. */
46 #include "sel-sched-dump.h"
48 /* A vector holding bb info for whole scheduling pass. */
49 vec<sel_global_bb_info_def> sel_global_bb_info;
51 /* A vector holding bb info. */
52 vec<sel_region_bb_info_def> sel_region_bb_info;
54 /* A pool for allocating all lists. */
55 object_allocator<_list_node> sched_lists_pool ("sel-sched-lists");
57 /* This contains information about successors for compute_av_set. */
58 struct succs_info current_succs;
60 /* Data structure to describe interaction with the generic scheduler utils. */
61 static struct common_sched_info_def sel_common_sched_info;
63 /* The loop nest being pipelined. */
64 class loop *current_loop_nest;
66 /* LOOP_NESTS is a vector containing the corresponding loop nest for
68 static vec<loop_p> loop_nests;
70 /* Saves blocks already in loop regions, indexed by bb->index. */
71 static sbitmap bbs_in_loop_rgns = NULL;
73 /* CFG hooks that are saved before changing create_basic_block hook. */
74 static struct cfg_hooks orig_cfg_hooks;
77 /* Array containing reverse topological index of function basic blocks,
78 indexed by BB->INDEX. */
79 static int *rev_top_order_index = NULL;
81 /* Length of the above array. */
82 static int rev_top_order_index_len = -1;
84 /* A regset pool structure. */
87 /* The stack to which regsets are returned. */
96 /* In VV we save all generated regsets so that, when destructing the
97 pool, we can compare it with V and check that every regset was returned
101 /* The pointer of VV stack. */
107 /* The difference between allocated and returned regsets. */
109 } regset_pool = { NULL, 0, 0, NULL, 0, 0, 0 };
111 /* This represents the nop pool. */
114 /* The vector which holds previously emitted nops. */
122 } nop_pool = { NULL, 0, 0 };
124 /* The pool for basic block notes. */
125 static vec<rtx_note *> bb_note_pool;
127 /* A NOP pattern used to emit placeholder insns. */
128 rtx nop_pattern = NULL_RTX;
129 /* A special instruction that resides in EXIT_BLOCK.
130 EXIT_INSN is successor of the insns that lead to EXIT_BLOCK. */
131 rtx_insn *exit_insn = NULL;
133 /* TRUE if while scheduling current region, which is loop, its preheader
135 bool preheader_removed = false;
138 /* Forward static declarations. */
139 static void fence_clear (fence_t);
141 static void deps_init_id (idata_t, insn_t, bool);
142 static void init_id_from_df (idata_t, insn_t, bool);
143 static expr_t set_insn_init (expr_t, vinsn_t, int);
145 static void cfg_preds (basic_block, insn_t **, int *);
146 static void prepare_insn_expr (insn_t, int);
147 static void free_history_vect (vec<expr_history_def> &);
149 static void move_bb_info (basic_block, basic_block);
150 static void remove_empty_bb (basic_block, bool);
151 static void sel_merge_blocks (basic_block, basic_block);
152 static void sel_remove_loop_preheader (void);
153 static bool bb_has_removable_jump_to_p (basic_block, basic_block);
155 static bool insn_is_the_only_one_in_bb_p (insn_t);
156 static void create_initial_data_sets (basic_block);
158 static void free_av_set (basic_block);
159 static void invalidate_av_set (basic_block);
160 static void extend_insn_data (void);
161 static void sel_init_new_insn (insn_t, int, int = -1);
162 static void finish_insns (void);
164 /* Various list functions. */
166 /* Copy an instruction list L. */
168 ilist_copy (ilist_t l)
170 ilist_t head = NULL, *tailp = &head;
174 ilist_add (tailp, ILIST_INSN (l));
175 tailp = &ILIST_NEXT (*tailp);
182 /* Invert an instruction list L. */
184 ilist_invert (ilist_t l)
190 ilist_add (&res, ILIST_INSN (l));
197 /* Add a new boundary to the LP list with parameters TO, PTR, and DC. */
199 blist_add (blist_t *lp, insn_t to, ilist_t ptr, deps_t dc)
204 bnd = BLIST_BND (*lp);
209 BND_AV1 (bnd) = NULL;
213 /* Remove the list note pointed to by LP. */
215 blist_remove (blist_t *lp)
217 bnd_t b = BLIST_BND (*lp);
219 av_set_clear (&BND_AV (b));
220 av_set_clear (&BND_AV1 (b));
221 ilist_clear (&BND_PTR (b));
226 /* Init a fence tail L. */
228 flist_tail_init (flist_tail_t l)
230 FLIST_TAIL_HEAD (l) = NULL;
231 FLIST_TAIL_TAILP (l) = &FLIST_TAIL_HEAD (l);
234 /* Try to find fence corresponding to INSN in L. */
236 flist_lookup (flist_t l, insn_t insn)
240 if (FENCE_INSN (FLIST_FENCE (l)) == insn)
241 return FLIST_FENCE (l);
249 /* Init the fields of F before running fill_insns. */
251 init_fence_for_scheduling (fence_t f)
253 FENCE_BNDS (f) = NULL;
254 FENCE_PROCESSED_P (f) = false;
255 FENCE_SCHEDULED_P (f) = false;
258 /* Add new fence consisting of INSN and STATE to the list pointed to by LP. */
260 flist_add (flist_t *lp, insn_t insn, state_t state, deps_t dc, void *tc,
261 insn_t last_scheduled_insn, vec<rtx_insn *, va_gc> *executing_insns,
262 int *ready_ticks, int ready_ticks_size, insn_t sched_next,
263 int cycle, int cycle_issued_insns, int issue_more,
264 bool starts_cycle_p, bool after_stall_p)
269 f = FLIST_FENCE (*lp);
271 FENCE_INSN (f) = insn;
273 gcc_assert (state != NULL);
274 FENCE_STATE (f) = state;
276 FENCE_CYCLE (f) = cycle;
277 FENCE_ISSUED_INSNS (f) = cycle_issued_insns;
278 FENCE_STARTS_CYCLE_P (f) = starts_cycle_p;
279 FENCE_AFTER_STALL_P (f) = after_stall_p;
281 gcc_assert (dc != NULL);
284 gcc_assert (tc != NULL || targetm.sched.alloc_sched_context == NULL);
287 FENCE_LAST_SCHEDULED_INSN (f) = last_scheduled_insn;
288 FENCE_ISSUE_MORE (f) = issue_more;
289 FENCE_EXECUTING_INSNS (f) = executing_insns;
290 FENCE_READY_TICKS (f) = ready_ticks;
291 FENCE_READY_TICKS_SIZE (f) = ready_ticks_size;
292 FENCE_SCHED_NEXT (f) = sched_next;
294 init_fence_for_scheduling (f);
297 /* Remove the head node of the list pointed to by LP. */
299 flist_remove (flist_t *lp)
301 if (FENCE_INSN (FLIST_FENCE (*lp)))
302 fence_clear (FLIST_FENCE (*lp));
306 /* Clear the fence list pointed to by LP. */
308 flist_clear (flist_t *lp)
314 /* Add ORIGINAL_INSN the def list DL honoring CROSSES_CALL. */
316 def_list_add (def_list_t *dl, insn_t original_insn, bool crosses_call)
321 d = DEF_LIST_DEF (*dl);
323 d->orig_insn = original_insn;
324 d->crosses_call = crosses_call;
328 /* Functions to work with target contexts. */
330 /* Bulk target context. It is convenient for debugging purposes to ensure
331 that there are no uninitialized (null) target contexts. */
332 static tc_t bulk_tc = (tc_t) 1;
334 /* Target hooks wrappers. In the future we can provide some default
335 implementations for them. */
337 /* Allocate a store for the target context. */
339 alloc_target_context (void)
341 return (targetm.sched.alloc_sched_context
342 ? targetm.sched.alloc_sched_context () : bulk_tc);
345 /* Init target context TC.
346 If CLEAN_P is true, then make TC as it is beginning of the scheduler.
347 Overwise, copy current backend context to TC. */
349 init_target_context (tc_t tc, bool clean_p)
351 if (targetm.sched.init_sched_context)
352 targetm.sched.init_sched_context (tc, clean_p);
355 /* Allocate and initialize a target context. Meaning of CLEAN_P is the same as
356 int init_target_context (). */
358 create_target_context (bool clean_p)
360 tc_t tc = alloc_target_context ();
362 init_target_context (tc, clean_p);
366 /* Copy TC to the current backend context. */
368 set_target_context (tc_t tc)
370 if (targetm.sched.set_sched_context)
371 targetm.sched.set_sched_context (tc);
374 /* TC is about to be destroyed. Free any internal data. */
376 clear_target_context (tc_t tc)
378 if (targetm.sched.clear_sched_context)
379 targetm.sched.clear_sched_context (tc);
382 /* Clear and free it. */
384 delete_target_context (tc_t tc)
386 clear_target_context (tc);
388 if (targetm.sched.free_sched_context)
389 targetm.sched.free_sched_context (tc);
392 /* Make a copy of FROM in TO.
393 NB: May be this should be a hook. */
395 copy_target_context (tc_t to, tc_t from)
397 tc_t tmp = create_target_context (false);
399 set_target_context (from);
400 init_target_context (to, false);
402 set_target_context (tmp);
403 delete_target_context (tmp);
406 /* Create a copy of TC. */
408 create_copy_of_target_context (tc_t tc)
410 tc_t copy = alloc_target_context ();
412 copy_target_context (copy, tc);
417 /* Clear TC and initialize it according to CLEAN_P. The meaning of CLEAN_P
418 is the same as in init_target_context (). */
420 reset_target_context (tc_t tc, bool clean_p)
422 clear_target_context (tc);
423 init_target_context (tc, clean_p);
426 /* Functions to work with dependence contexts.
427 Dc (aka deps context, aka deps_t, aka class deps_desc *) is short for dependence
428 context. It accumulates information about processed insns to decide if
429 current insn is dependent on the processed ones. */
431 /* Make a copy of FROM in TO. */
433 copy_deps_context (deps_t to, deps_t from)
435 init_deps (to, false);
436 deps_join (to, from);
439 /* Allocate store for dep context. */
441 alloc_deps_context (void)
443 return XNEW (class deps_desc);
446 /* Allocate and initialize dep context. */
448 create_deps_context (void)
450 deps_t dc = alloc_deps_context ();
452 init_deps (dc, false);
456 /* Create a copy of FROM. */
458 create_copy_of_deps_context (deps_t from)
460 deps_t to = alloc_deps_context ();
462 copy_deps_context (to, from);
466 /* Clean up internal data of DC. */
468 clear_deps_context (deps_t dc)
473 /* Clear and free DC. */
475 delete_deps_context (deps_t dc)
477 clear_deps_context (dc);
481 /* Clear and init DC. */
483 reset_deps_context (deps_t dc)
485 clear_deps_context (dc);
486 init_deps (dc, false);
489 /* This structure describes the dependence analysis hooks for advancing
490 dependence context. */
491 static struct sched_deps_info_def advance_deps_context_sched_deps_info =
495 NULL, /* start_insn */
496 NULL, /* finish_insn */
497 NULL, /* start_lhs */
498 NULL, /* finish_lhs */
499 NULL, /* start_rhs */
500 NULL, /* finish_rhs */
502 haifa_note_reg_clobber,
504 NULL, /* note_mem_dep */
510 /* Process INSN and add its impact on DC. */
512 advance_deps_context (deps_t dc, insn_t insn)
514 sched_deps_info = &advance_deps_context_sched_deps_info;
515 deps_analyze_insn (dc, insn);
519 /* Functions to work with DFA states. */
521 /* Allocate store for a DFA state. */
525 return xmalloc (dfa_state_size);
528 /* Allocate and initialize DFA state. */
532 state_t state = state_alloc ();
535 advance_state (state);
539 /* Free DFA state. */
541 state_free (state_t state)
546 /* Make a copy of FROM in TO. */
548 state_copy (state_t to, state_t from)
550 memcpy (to, from, dfa_state_size);
553 /* Create a copy of FROM. */
555 state_create_copy (state_t from)
557 state_t to = state_alloc ();
559 state_copy (to, from);
564 /* Functions to work with fences. */
566 /* Clear the fence. */
568 fence_clear (fence_t f)
570 state_t s = FENCE_STATE (f);
571 deps_t dc = FENCE_DC (f);
572 void *tc = FENCE_TC (f);
574 ilist_clear (&FENCE_BNDS (f));
576 gcc_assert ((s != NULL && dc != NULL && tc != NULL)
577 || (s == NULL && dc == NULL && tc == NULL));
582 delete_deps_context (dc);
585 delete_target_context (tc);
586 vec_free (FENCE_EXECUTING_INSNS (f));
587 free (FENCE_READY_TICKS (f));
588 FENCE_READY_TICKS (f) = NULL;
591 /* Init a list of fences with successors of OLD_FENCE. */
593 init_fences (insn_t old_fence)
598 int ready_ticks_size = get_max_uid () + 1;
600 FOR_EACH_SUCC_1 (succ, si, old_fence,
601 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
607 gcc_assert (flag_sel_sched_pipelining_outer_loops);
609 flist_add (&fences, succ,
611 create_deps_context () /* dc */,
612 create_target_context (true) /* tc */,
613 NULL /* last_scheduled_insn */,
614 NULL, /* executing_insns */
615 XCNEWVEC (int, ready_ticks_size), /* ready_ticks */
617 NULL /* sched_next */,
618 1 /* cycle */, 0 /* cycle_issued_insns */,
619 issue_rate, /* issue_more */
620 1 /* starts_cycle_p */, 0 /* after_stall_p */);
624 /* Merges two fences (filling fields of fence F with resulting values) by
625 following rules: 1) state, target context and last scheduled insn are
626 propagated from fallthrough edge if it is available;
627 2) deps context and cycle is propagated from more probable edge;
628 3) all other fields are set to corresponding constant values.
630 INSN, STATE, DC, TC, LAST_SCHEDULED_INSN, EXECUTING_INSNS,
631 READY_TICKS, READY_TICKS_SIZE, SCHED_NEXT, CYCLE, ISSUE_MORE
632 and AFTER_STALL_P are the corresponding fields of the second fence. */
634 merge_fences (fence_t f, insn_t insn,
635 state_t state, deps_t dc, void *tc,
636 rtx_insn *last_scheduled_insn,
637 vec<rtx_insn *, va_gc> *executing_insns,
638 int *ready_ticks, int ready_ticks_size,
639 rtx sched_next, int cycle, int issue_more, bool after_stall_p)
641 insn_t last_scheduled_insn_old = FENCE_LAST_SCHEDULED_INSN (f);
643 gcc_assert (sel_bb_head_p (FENCE_INSN (f))
644 && !sched_next && !FENCE_SCHED_NEXT (f));
646 /* Check if we can decide which path fences came.
647 If we can't (or don't want to) - reset all. */
648 if (last_scheduled_insn == NULL
649 || last_scheduled_insn_old == NULL
650 /* This is a case when INSN is reachable on several paths from
651 one insn (this can happen when pipelining of outer loops is on and
652 there are two edges: one going around of inner loop and the other -
653 right through it; in such case just reset everything). */
654 || last_scheduled_insn == last_scheduled_insn_old)
656 state_reset (FENCE_STATE (f));
659 reset_deps_context (FENCE_DC (f));
660 delete_deps_context (dc);
662 reset_target_context (FENCE_TC (f), true);
663 delete_target_context (tc);
665 if (cycle > FENCE_CYCLE (f))
666 FENCE_CYCLE (f) = cycle;
668 FENCE_LAST_SCHEDULED_INSN (f) = NULL;
669 FENCE_ISSUE_MORE (f) = issue_rate;
670 vec_free (executing_insns);
672 if (FENCE_EXECUTING_INSNS (f))
673 FENCE_EXECUTING_INSNS (f)->block_remove (0,
674 FENCE_EXECUTING_INSNS (f)->length ());
675 if (FENCE_READY_TICKS (f))
676 memset (FENCE_READY_TICKS (f), 0, FENCE_READY_TICKS_SIZE (f));
680 edge edge_old = NULL, edge_new = NULL;
685 /* Find fallthrough edge. */
686 gcc_assert (BLOCK_FOR_INSN (insn)->prev_bb);
687 candidate = find_fallthru_edge_from (BLOCK_FOR_INSN (insn)->prev_bb);
690 || (candidate->src != BLOCK_FOR_INSN (last_scheduled_insn)
691 && candidate->src != BLOCK_FOR_INSN (last_scheduled_insn_old)))
693 /* No fallthrough edge leading to basic block of INSN. */
694 state_reset (FENCE_STATE (f));
697 reset_target_context (FENCE_TC (f), true);
698 delete_target_context (tc);
700 FENCE_LAST_SCHEDULED_INSN (f) = NULL;
701 FENCE_ISSUE_MORE (f) = issue_rate;
704 if (candidate->src == BLOCK_FOR_INSN (last_scheduled_insn))
706 state_free (FENCE_STATE (f));
707 FENCE_STATE (f) = state;
709 delete_target_context (FENCE_TC (f));
712 FENCE_LAST_SCHEDULED_INSN (f) = last_scheduled_insn;
713 FENCE_ISSUE_MORE (f) = issue_more;
717 /* Leave STATE, TC and LAST_SCHEDULED_INSN fields untouched. */
719 delete_target_context (tc);
721 gcc_assert (BLOCK_FOR_INSN (insn)->prev_bb
722 != BLOCK_FOR_INSN (last_scheduled_insn));
725 /* Find edge of first predecessor (last_scheduled_insn_old->insn). */
726 FOR_EACH_SUCC_1 (succ, si, last_scheduled_insn_old,
727 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
731 /* No same successor allowed from several edges. */
732 gcc_assert (!edge_old);
736 /* Find edge of second predecessor (last_scheduled_insn->insn). */
737 FOR_EACH_SUCC_1 (succ, si, last_scheduled_insn,
738 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
742 /* No same successor allowed from several edges. */
743 gcc_assert (!edge_new);
748 /* Check if we can choose most probable predecessor. */
749 if (edge_old == NULL || edge_new == NULL)
751 reset_deps_context (FENCE_DC (f));
752 delete_deps_context (dc);
753 vec_free (executing_insns);
756 FENCE_CYCLE (f) = MAX (FENCE_CYCLE (f), cycle);
757 if (FENCE_EXECUTING_INSNS (f))
758 FENCE_EXECUTING_INSNS (f)->block_remove (0,
759 FENCE_EXECUTING_INSNS (f)->length ());
760 if (FENCE_READY_TICKS (f))
761 memset (FENCE_READY_TICKS (f), 0, FENCE_READY_TICKS_SIZE (f));
764 if (edge_new->probability > edge_old->probability)
766 delete_deps_context (FENCE_DC (f));
768 vec_free (FENCE_EXECUTING_INSNS (f));
769 FENCE_EXECUTING_INSNS (f) = executing_insns;
770 free (FENCE_READY_TICKS (f));
771 FENCE_READY_TICKS (f) = ready_ticks;
772 FENCE_READY_TICKS_SIZE (f) = ready_ticks_size;
773 FENCE_CYCLE (f) = cycle;
777 /* Leave DC and CYCLE untouched. */
778 delete_deps_context (dc);
779 vec_free (executing_insns);
784 /* Fill remaining invariant fields. */
786 FENCE_AFTER_STALL_P (f) = 1;
788 FENCE_ISSUED_INSNS (f) = 0;
789 FENCE_STARTS_CYCLE_P (f) = 1;
790 FENCE_SCHED_NEXT (f) = NULL;
793 /* Add a new fence to NEW_FENCES list, initializing it from all
796 add_to_fences (flist_tail_t new_fences, insn_t insn,
797 state_t state, deps_t dc, void *tc,
798 rtx_insn *last_scheduled_insn,
799 vec<rtx_insn *, va_gc> *executing_insns, int *ready_ticks,
800 int ready_ticks_size, rtx_insn *sched_next, int cycle,
801 int cycle_issued_insns, int issue_rate,
802 bool starts_cycle_p, bool after_stall_p)
804 fence_t f = flist_lookup (FLIST_TAIL_HEAD (new_fences), insn);
808 flist_add (FLIST_TAIL_TAILP (new_fences), insn, state, dc, tc,
809 last_scheduled_insn, executing_insns, ready_ticks,
810 ready_ticks_size, sched_next, cycle, cycle_issued_insns,
811 issue_rate, starts_cycle_p, after_stall_p);
813 FLIST_TAIL_TAILP (new_fences)
814 = &FLIST_NEXT (*FLIST_TAIL_TAILP (new_fences));
818 merge_fences (f, insn, state, dc, tc, last_scheduled_insn,
819 executing_insns, ready_ticks, ready_ticks_size,
820 sched_next, cycle, issue_rate, after_stall_p);
824 /* Move the first fence in the OLD_FENCES list to NEW_FENCES. */
826 move_fence_to_fences (flist_t old_fences, flist_tail_t new_fences)
829 flist_t *tailp = FLIST_TAIL_TAILP (new_fences);
831 old = FLIST_FENCE (old_fences);
832 f = flist_lookup (FLIST_TAIL_HEAD (new_fences),
833 FENCE_INSN (FLIST_FENCE (old_fences)));
836 merge_fences (f, old->insn, old->state, old->dc, old->tc,
837 old->last_scheduled_insn, old->executing_insns,
838 old->ready_ticks, old->ready_ticks_size,
839 old->sched_next, old->cycle, old->issue_more,
845 FLIST_TAIL_TAILP (new_fences) = &FLIST_NEXT (*tailp);
846 *FLIST_FENCE (*tailp) = *old;
847 init_fence_for_scheduling (FLIST_FENCE (*tailp));
849 FENCE_INSN (old) = NULL;
852 /* Add a new fence to NEW_FENCES list and initialize most of its data
855 add_clean_fence_to_fences (flist_tail_t new_fences, insn_t succ, fence_t fence)
857 int ready_ticks_size = get_max_uid () + 1;
859 add_to_fences (new_fences,
860 succ, state_create (), create_deps_context (),
861 create_target_context (true),
863 XCNEWVEC (int, ready_ticks_size), ready_ticks_size,
864 NULL, FENCE_CYCLE (fence) + 1,
865 0, issue_rate, 1, FENCE_AFTER_STALL_P (fence));
868 /* Add a new fence to NEW_FENCES list and initialize all of its data
869 from FENCE and SUCC. */
871 add_dirty_fence_to_fences (flist_tail_t new_fences, insn_t succ, fence_t fence)
873 int * new_ready_ticks
874 = XNEWVEC (int, FENCE_READY_TICKS_SIZE (fence));
876 memcpy (new_ready_ticks, FENCE_READY_TICKS (fence),
877 FENCE_READY_TICKS_SIZE (fence) * sizeof (int));
878 add_to_fences (new_fences,
879 succ, state_create_copy (FENCE_STATE (fence)),
880 create_copy_of_deps_context (FENCE_DC (fence)),
881 create_copy_of_target_context (FENCE_TC (fence)),
882 FENCE_LAST_SCHEDULED_INSN (fence),
883 vec_safe_copy (FENCE_EXECUTING_INSNS (fence)),
885 FENCE_READY_TICKS_SIZE (fence),
886 FENCE_SCHED_NEXT (fence),
888 FENCE_ISSUED_INSNS (fence),
889 FENCE_ISSUE_MORE (fence),
890 FENCE_STARTS_CYCLE_P (fence),
891 FENCE_AFTER_STALL_P (fence));
895 /* Functions to work with regset and nop pools. */
897 /* Returns the new regset from pool. It might have some of the bits set
898 from the previous usage. */
900 get_regset_from_pool (void)
904 if (regset_pool.n != 0)
905 rs = regset_pool.v[--regset_pool.n];
907 /* We need to create the regset. */
909 rs = ALLOC_REG_SET (®_obstack);
911 if (regset_pool.nn == regset_pool.ss)
912 regset_pool.vv = XRESIZEVEC (regset, regset_pool.vv,
913 (regset_pool.ss = 2 * regset_pool.ss + 1));
914 regset_pool.vv[regset_pool.nn++] = rs;
922 /* Same as above, but returns the empty regset. */
924 get_clear_regset_from_pool (void)
926 regset rs = get_regset_from_pool ();
932 /* Return regset RS to the pool for future use. */
934 return_regset_to_pool (regset rs)
939 if (regset_pool.n == regset_pool.s)
940 regset_pool.v = XRESIZEVEC (regset, regset_pool.v,
941 (regset_pool.s = 2 * regset_pool.s + 1));
942 regset_pool.v[regset_pool.n++] = rs;
945 /* This is used as a qsort callback for sorting regset pool stacks.
946 X and XX are addresses of two regsets. They are never equal. */
948 cmp_v_in_regset_pool (const void *x, const void *xx)
950 uintptr_t r1 = (uintptr_t) *((const regset *) x);
951 uintptr_t r2 = (uintptr_t) *((const regset *) xx);
959 /* Free the regset pool possibly checking for memory leaks. */
961 free_regset_pool (void)
965 regset *v = regset_pool.v;
967 int n = regset_pool.n;
969 regset *vv = regset_pool.vv;
971 int nn = regset_pool.nn;
975 gcc_assert (n <= nn);
977 /* Sort both vectors so it will be possible to compare them. */
978 qsort (v, n, sizeof (*v), cmp_v_in_regset_pool);
979 qsort (vv, nn, sizeof (*vv), cmp_v_in_regset_pool);
986 /* VV[II] was lost. */
992 gcc_assert (diff == regset_pool.diff);
995 /* If not true - we have a memory leak. */
996 gcc_assert (regset_pool.diff == 0);
998 while (regset_pool.n)
1001 FREE_REG_SET (regset_pool.v[regset_pool.n]);
1004 free (regset_pool.v);
1005 regset_pool.v = NULL;
1008 free (regset_pool.vv);
1009 regset_pool.vv = NULL;
1013 regset_pool.diff = 0;
1017 /* Functions to work with nop pools. NOP insns are used as temporary
1018 placeholders of the insns being scheduled to allow correct update of
1019 the data sets. When update is finished, NOPs are deleted. */
1021 /* A vinsn that is used to represent a nop. This vinsn is shared among all
1022 nops sel-sched generates. */
1023 static vinsn_t nop_vinsn = NULL;
1025 /* Emit a nop before INSN, taking it from pool. */
1027 get_nop_from_pool (insn_t insn)
1031 bool old_p = nop_pool.n != 0;
1035 nop_pat = nop_pool.v[--nop_pool.n];
1037 nop_pat = nop_pattern;
1039 nop = emit_insn_before (nop_pat, insn);
1042 flags = INSN_INIT_TODO_SSID;
1044 flags = INSN_INIT_TODO_LUID | INSN_INIT_TODO_SSID;
1046 set_insn_init (INSN_EXPR (insn), nop_vinsn, INSN_SEQNO (insn));
1047 sel_init_new_insn (nop, flags);
1052 /* Remove NOP from the instruction stream and return it to the pool. */
1054 return_nop_to_pool (insn_t nop, bool full_tidying)
1056 gcc_assert (INSN_IN_STREAM_P (nop));
1057 sel_remove_insn (nop, false, full_tidying);
1059 /* We'll recycle this nop. */
1060 nop->set_undeleted ();
1062 if (nop_pool.n == nop_pool.s)
1063 nop_pool.v = XRESIZEVEC (rtx_insn *, nop_pool.v,
1064 (nop_pool.s = 2 * nop_pool.s + 1));
1065 nop_pool.v[nop_pool.n++] = nop;
1068 /* Free the nop pool. */
1070 free_nop_pool (void)
1079 /* Skip unspec to support ia64 speculation. Called from rtx_equal_p_cb.
1080 The callback is given two rtxes XX and YY and writes the new rtxes
1081 to NX and NY in case some needs to be skipped. */
1083 skip_unspecs_callback (const_rtx *xx, const_rtx *yy, rtx *nx, rtx* ny)
1088 if (GET_CODE (x) == UNSPEC
1089 && (targetm.sched.skip_rtx_p == NULL
1090 || targetm.sched.skip_rtx_p (x)))
1092 *nx = XVECEXP (x, 0, 0);
1093 *ny = CONST_CAST_RTX (y);
1097 if (GET_CODE (y) == UNSPEC
1098 && (targetm.sched.skip_rtx_p == NULL
1099 || targetm.sched.skip_rtx_p (y)))
1101 *nx = CONST_CAST_RTX (x);
1102 *ny = XVECEXP (y, 0, 0);
1109 /* Callback, called from hash_rtx_cb. Helps to hash UNSPEC rtx X in a correct way
1110 to support ia64 speculation. When changes are needed, new rtx X and new mode
1111 NMODE are written, and the callback returns true. */
1113 hash_with_unspec_callback (const_rtx x, machine_mode mode ATTRIBUTE_UNUSED,
1114 rtx *nx, machine_mode* nmode)
1116 if (GET_CODE (x) == UNSPEC
1117 && targetm.sched.skip_rtx_p
1118 && targetm.sched.skip_rtx_p (x))
1120 *nx = XVECEXP (x, 0 ,0);
1128 /* Returns LHS and RHS are ok to be scheduled separately. */
1130 lhs_and_rhs_separable_p (rtx lhs, rtx rhs)
1132 if (lhs == NULL || rhs == NULL)
1135 /* Do not schedule constants as rhs: no point to use reg, if const
1136 can be used. Moreover, scheduling const as rhs may lead to mode
1137 mismatch cause consts don't have modes but they could be merged
1138 from branches where the same const used in different modes. */
1139 if (CONSTANT_P (rhs))
1142 /* ??? Do not rename predicate registers to avoid ICEs in bundling. */
1143 if (COMPARISON_P (rhs))
1146 /* Do not allow single REG to be an rhs. */
1150 /* See comment at find_used_regs_1 (*1) for explanation of this
1152 /* FIXME: remove this later. */
1156 /* This will filter all tricky things like ZERO_EXTRACT etc.
1157 For now we don't handle it. */
1158 if (!REG_P (lhs) && !MEM_P (lhs))
1164 /* Initialize vinsn VI for INSN. Only for use from vinsn_create (). When
1165 FORCE_UNIQUE_P is true, the resulting vinsn will not be clonable. This is
1166 used e.g. for insns from recovery blocks. */
1168 vinsn_init (vinsn_t vi, insn_t insn, bool force_unique_p)
1170 hash_rtx_callback_function hrcf;
1173 VINSN_INSN_RTX (vi) = insn;
1174 VINSN_COUNT (vi) = 0;
1177 if (INSN_NOP_P (insn))
1180 if (DF_INSN_UID_SAFE_GET (INSN_UID (insn)) != NULL)
1181 init_id_from_df (VINSN_ID (vi), insn, force_unique_p);
1183 deps_init_id (VINSN_ID (vi), insn, force_unique_p);
1185 /* Hash vinsn depending on whether it is separable or not. */
1186 hrcf = targetm.sched.skip_rtx_p ? hash_with_unspec_callback : NULL;
1187 if (VINSN_SEPARABLE_P (vi))
1189 rtx rhs = VINSN_RHS (vi);
1191 VINSN_HASH (vi) = hash_rtx_cb (rhs, GET_MODE (rhs),
1192 NULL, NULL, false, hrcf);
1193 VINSN_HASH_RTX (vi) = hash_rtx_cb (VINSN_PATTERN (vi),
1194 VOIDmode, NULL, NULL,
1199 VINSN_HASH (vi) = hash_rtx_cb (VINSN_PATTERN (vi), VOIDmode,
1200 NULL, NULL, false, hrcf);
1201 VINSN_HASH_RTX (vi) = VINSN_HASH (vi);
1204 insn_class = haifa_classify_insn (insn);
1206 && (!targetm.sched.get_insn_spec_ds
1207 || ((targetm.sched.get_insn_spec_ds (insn) & BEGIN_CONTROL)
1209 VINSN_MAY_TRAP_P (vi) = true;
1211 VINSN_MAY_TRAP_P (vi) = false;
1214 /* Indicate that VI has become the part of an rtx object. */
1216 vinsn_attach (vinsn_t vi)
1218 /* Assert that VI is not pending for deletion. */
1219 gcc_assert (VINSN_INSN_RTX (vi));
1224 /* Create and init VI from the INSN. Use UNIQUE_P for determining the correct
1227 vinsn_create (insn_t insn, bool force_unique_p)
1229 vinsn_t vi = XCNEW (struct vinsn_def);
1231 vinsn_init (vi, insn, force_unique_p);
1235 /* Return a copy of VI. When REATTACH_P is true, detach VI and attach
1238 vinsn_copy (vinsn_t vi, bool reattach_p)
1241 bool unique = VINSN_UNIQUE_P (vi);
1244 copy = create_copy_of_insn_rtx (VINSN_INSN_RTX (vi));
1245 new_vi = create_vinsn_from_insn_rtx (copy, unique);
1249 vinsn_attach (new_vi);
1255 /* Delete the VI vinsn and free its data. */
1257 vinsn_delete (vinsn_t vi)
1259 gcc_assert (VINSN_COUNT (vi) == 0);
1261 if (!INSN_NOP_P (VINSN_INSN_RTX (vi)))
1263 return_regset_to_pool (VINSN_REG_SETS (vi));
1264 return_regset_to_pool (VINSN_REG_USES (vi));
1265 return_regset_to_pool (VINSN_REG_CLOBBERS (vi));
1271 /* Indicate that VI is no longer a part of some rtx object.
1272 Remove VI if it is no longer needed. */
1274 vinsn_detach (vinsn_t vi)
1276 gcc_assert (VINSN_COUNT (vi) > 0);
1278 if (--VINSN_COUNT (vi) == 0)
1282 /* Returns TRUE if VI is a branch. */
1284 vinsn_cond_branch_p (vinsn_t vi)
1288 if (!VINSN_UNIQUE_P (vi))
1291 insn = VINSN_INSN_RTX (vi);
1292 if (BB_END (BLOCK_FOR_INSN (insn)) != insn)
1295 return control_flow_insn_p (insn);
1298 /* Return latency of INSN. */
1300 sel_insn_rtx_cost (rtx_insn *insn)
1304 /* A USE insn, or something else we don't need to
1305 understand. We can't pass these directly to
1306 result_ready_cost or insn_default_latency because it will
1307 trigger a fatal error for unrecognizable insns. */
1308 if (recog_memoized (insn) < 0)
1312 cost = insn_default_latency (insn);
1321 /* Return the cost of the VI.
1322 !!! FIXME: Unify with haifa-sched.c: insn_sched_cost (). */
1324 sel_vinsn_cost (vinsn_t vi)
1326 int cost = vi->cost;
1330 cost = sel_insn_rtx_cost (VINSN_INSN_RTX (vi));
1338 /* Functions for insn emitting. */
1340 /* Emit new insn after AFTER based on PATTERN and initialize its data from
1343 sel_gen_insn_from_rtx_after (rtx pattern, expr_t expr, int seqno, insn_t after)
1347 gcc_assert (EXPR_TARGET_AVAILABLE (expr) == true);
1349 new_insn = emit_insn_after (pattern, after);
1350 set_insn_init (expr, NULL, seqno);
1351 sel_init_new_insn (new_insn, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SSID);
1356 /* Force newly generated vinsns to be unique. */
1357 static bool init_insn_force_unique_p = false;
1359 /* Emit new speculation recovery insn after AFTER based on PATTERN and
1360 initialize its data from EXPR and SEQNO. */
1362 sel_gen_recovery_insn_from_rtx_after (rtx pattern, expr_t expr, int seqno,
1367 gcc_assert (!init_insn_force_unique_p);
1369 init_insn_force_unique_p = true;
1370 insn = sel_gen_insn_from_rtx_after (pattern, expr, seqno, after);
1371 CANT_MOVE (insn) = 1;
1372 init_insn_force_unique_p = false;
1377 /* Emit new insn after AFTER based on EXPR and SEQNO. If VINSN is not NULL,
1378 take it as a new vinsn instead of EXPR's vinsn.
1379 We simplify insns later, after scheduling region in
1380 simplify_changed_insns. */
1382 sel_gen_insn_from_expr_after (expr_t expr, vinsn_t vinsn, int seqno,
1389 emit_expr = set_insn_init (expr, vinsn ? vinsn : EXPR_VINSN (expr),
1391 insn = EXPR_INSN_RTX (emit_expr);
1393 /* The insn may come from the transformation cache, which may hold already
1394 deleted insns, so mark it as not deleted. */
1395 insn->set_undeleted ();
1397 add_insn_after (insn, after, BLOCK_FOR_INSN (insn));
1399 flags = INSN_INIT_TODO_SSID;
1400 if (INSN_LUID (insn) == 0)
1401 flags |= INSN_INIT_TODO_LUID;
1402 sel_init_new_insn (insn, flags);
1407 /* Move insn from EXPR after AFTER. */
1409 sel_move_insn (expr_t expr, int seqno, insn_t after)
1411 insn_t insn = EXPR_INSN_RTX (expr);
1412 basic_block bb = BLOCK_FOR_INSN (after);
1413 insn_t next = NEXT_INSN (after);
1415 /* Assert that in move_op we disconnected this insn properly. */
1416 gcc_assert (EXPR_VINSN (INSN_EXPR (insn)) != NULL);
1417 SET_PREV_INSN (insn) = after;
1418 SET_NEXT_INSN (insn) = next;
1420 SET_NEXT_INSN (after) = insn;
1421 SET_PREV_INSN (next) = insn;
1423 /* Update links from insn to bb and vice versa. */
1424 df_insn_change_bb (insn, bb);
1425 if (BB_END (bb) == after)
1428 prepare_insn_expr (insn, seqno);
1433 /* Functions to work with right-hand sides. */
1435 /* Search for a hash value determined by UID/NEW_VINSN in a sorted vector
1436 VECT and return true when found. Use NEW_VINSN for comparison only when
1437 COMPARE_VINSNS is true. Write to INDP the index on which
1438 the search has stopped, such that inserting the new element at INDP will
1439 retain VECT's sort order. */
1441 find_in_history_vect_1 (vec<expr_history_def> vect,
1442 unsigned uid, vinsn_t new_vinsn,
1443 bool compare_vinsns, int *indp)
1445 expr_history_def *arr;
1446 int i, j, len = vect.length ();
1454 arr = vect.address ();
1459 unsigned auid = arr[i].uid;
1460 vinsn_t avinsn = arr[i].new_expr_vinsn;
1463 /* When undoing transformation on a bookkeeping copy, the new vinsn
1464 may not be exactly equal to the one that is saved in the vector.
1465 This is because the insn whose copy we're checking was possibly
1466 substituted itself. */
1467 && (! compare_vinsns
1468 || vinsn_equal_p (avinsn, new_vinsn)))
1473 else if (auid > uid)
1482 /* Search for a uid of INSN and NEW_VINSN in a sorted vector VECT. Return
1483 the position found or -1, if no such value is in vector.
1484 Search also for UIDs of insn's originators, if ORIGINATORS_P is true. */
1486 find_in_history_vect (vec<expr_history_def> vect, rtx insn,
1487 vinsn_t new_vinsn, bool originators_p)
1491 if (find_in_history_vect_1 (vect, INSN_UID (insn), new_vinsn,
1495 if (INSN_ORIGINATORS (insn) && originators_p)
1500 EXECUTE_IF_SET_IN_BITMAP (INSN_ORIGINATORS (insn), 0, uid, bi)
1501 if (find_in_history_vect_1 (vect, uid, new_vinsn, false, &ind))
1508 /* Insert new element in a sorted history vector pointed to by PVECT,
1509 if it is not there already. The element is searched using
1510 UID/NEW_EXPR_VINSN pair. TYPE, OLD_EXPR_VINSN and SPEC_DS save
1511 the history of a transformation. */
1513 insert_in_history_vect (vec<expr_history_def> *pvect,
1514 unsigned uid, enum local_trans_type type,
1515 vinsn_t old_expr_vinsn, vinsn_t new_expr_vinsn,
1518 vec<expr_history_def> vect = *pvect;
1519 expr_history_def temp;
1523 res = find_in_history_vect_1 (vect, uid, new_expr_vinsn, true, &ind);
1527 expr_history_def *phist = &vect[ind];
1529 /* It is possible that speculation types of expressions that were
1530 propagated through different paths will be different here. In this
1531 case, merge the status to get the correct check later. */
1532 if (phist->spec_ds != spec_ds)
1533 phist->spec_ds = ds_max_merge (phist->spec_ds, spec_ds);
1538 temp.old_expr_vinsn = old_expr_vinsn;
1539 temp.new_expr_vinsn = new_expr_vinsn;
1540 temp.spec_ds = spec_ds;
1543 vinsn_attach (old_expr_vinsn);
1544 vinsn_attach (new_expr_vinsn);
1545 vect.safe_insert (ind, temp);
1549 /* Free history vector PVECT. */
1551 free_history_vect (vec<expr_history_def> &pvect)
1554 expr_history_def *phist;
1556 if (! pvect.exists ())
1559 for (i = 0; pvect.iterate (i, &phist); i++)
1561 vinsn_detach (phist->old_expr_vinsn);
1562 vinsn_detach (phist->new_expr_vinsn);
1568 /* Merge vector FROM to PVECT. */
1570 merge_history_vect (vec<expr_history_def> *pvect,
1571 vec<expr_history_def> from)
1573 expr_history_def *phist;
1576 /* We keep this vector sorted. */
1577 for (i = 0; from.iterate (i, &phist); i++)
1578 insert_in_history_vect (pvect, phist->uid, phist->type,
1579 phist->old_expr_vinsn, phist->new_expr_vinsn,
1583 /* Compare two vinsns as rhses if possible and as vinsns otherwise. */
1585 vinsn_equal_p (vinsn_t x, vinsn_t y)
1587 rtx_equal_p_callback_function repcf;
1592 if (VINSN_TYPE (x) != VINSN_TYPE (y))
1595 if (VINSN_HASH (x) != VINSN_HASH (y))
1598 repcf = targetm.sched.skip_rtx_p ? skip_unspecs_callback : NULL;
1599 if (VINSN_SEPARABLE_P (x))
1601 /* Compare RHSes of VINSNs. */
1602 gcc_assert (VINSN_RHS (x));
1603 gcc_assert (VINSN_RHS (y));
1605 return rtx_equal_p_cb (VINSN_RHS (x), VINSN_RHS (y), repcf);
1608 return rtx_equal_p_cb (VINSN_PATTERN (x), VINSN_PATTERN (y), repcf);
1612 /* Functions for working with expressions. */
1614 /* Initialize EXPR. */
1616 init_expr (expr_t expr, vinsn_t vi, int spec, int use, int priority,
1617 int sched_times, int orig_bb_index, ds_t spec_done_ds,
1618 ds_t spec_to_check_ds, int orig_sched_cycle,
1619 vec<expr_history_def> history,
1620 signed char target_available,
1621 bool was_substituted, bool was_renamed, bool needs_spec_check_p,
1626 EXPR_VINSN (expr) = vi;
1627 EXPR_SPEC (expr) = spec;
1628 EXPR_USEFULNESS (expr) = use;
1629 EXPR_PRIORITY (expr) = priority;
1630 EXPR_PRIORITY_ADJ (expr) = 0;
1631 EXPR_SCHED_TIMES (expr) = sched_times;
1632 EXPR_ORIG_BB_INDEX (expr) = orig_bb_index;
1633 EXPR_ORIG_SCHED_CYCLE (expr) = orig_sched_cycle;
1634 EXPR_SPEC_DONE_DS (expr) = spec_done_ds;
1635 EXPR_SPEC_TO_CHECK_DS (expr) = spec_to_check_ds;
1637 if (history.exists ())
1638 EXPR_HISTORY_OF_CHANGES (expr) = history;
1640 EXPR_HISTORY_OF_CHANGES (expr).create (0);
1642 EXPR_TARGET_AVAILABLE (expr) = target_available;
1643 EXPR_WAS_SUBSTITUTED (expr) = was_substituted;
1644 EXPR_WAS_RENAMED (expr) = was_renamed;
1645 EXPR_NEEDS_SPEC_CHECK_P (expr) = needs_spec_check_p;
1646 EXPR_CANT_MOVE (expr) = cant_move;
1649 /* Make a copy of the expr FROM into the expr TO. */
1651 copy_expr (expr_t to, expr_t from)
1653 vec<expr_history_def> temp = vNULL;
1655 if (EXPR_HISTORY_OF_CHANGES (from).exists ())
1658 expr_history_def *phist;
1660 temp = EXPR_HISTORY_OF_CHANGES (from).copy ();
1662 temp.iterate (i, &phist);
1665 vinsn_attach (phist->old_expr_vinsn);
1666 vinsn_attach (phist->new_expr_vinsn);
1670 init_expr (to, EXPR_VINSN (from), EXPR_SPEC (from),
1671 EXPR_USEFULNESS (from), EXPR_PRIORITY (from),
1672 EXPR_SCHED_TIMES (from), EXPR_ORIG_BB_INDEX (from),
1673 EXPR_SPEC_DONE_DS (from), EXPR_SPEC_TO_CHECK_DS (from),
1674 EXPR_ORIG_SCHED_CYCLE (from), temp,
1675 EXPR_TARGET_AVAILABLE (from), EXPR_WAS_SUBSTITUTED (from),
1676 EXPR_WAS_RENAMED (from), EXPR_NEEDS_SPEC_CHECK_P (from),
1677 EXPR_CANT_MOVE (from));
1680 /* Same, but the final expr will not ever be in av sets, so don't copy
1681 "uninteresting" data such as bitmap cache. */
1683 copy_expr_onside (expr_t to, expr_t from)
1685 init_expr (to, EXPR_VINSN (from), EXPR_SPEC (from), EXPR_USEFULNESS (from),
1686 EXPR_PRIORITY (from), EXPR_SCHED_TIMES (from), 0,
1687 EXPR_SPEC_DONE_DS (from), EXPR_SPEC_TO_CHECK_DS (from), 0,
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 /* Prepare the expr of INSN for scheduling. Used when moving insn and when
1695 initializing new insns. */
1697 prepare_insn_expr (insn_t insn, int seqno)
1699 expr_t expr = INSN_EXPR (insn);
1702 INSN_SEQNO (insn) = seqno;
1703 EXPR_ORIG_BB_INDEX (expr) = BLOCK_NUM (insn);
1704 EXPR_SPEC (expr) = 0;
1705 EXPR_ORIG_SCHED_CYCLE (expr) = 0;
1706 EXPR_WAS_SUBSTITUTED (expr) = 0;
1707 EXPR_WAS_RENAMED (expr) = 0;
1708 EXPR_TARGET_AVAILABLE (expr) = 1;
1709 INSN_LIVE_VALID_P (insn) = false;
1711 /* ??? If this expression is speculative, make its dependence
1712 as weak as possible. We can filter this expression later
1713 in process_spec_exprs, because we do not distinguish
1714 between the status we got during compute_av_set and the
1715 existing status. To be fixed. */
1716 ds = EXPR_SPEC_DONE_DS (expr);
1718 EXPR_SPEC_DONE_DS (expr) = ds_get_max_dep_weak (ds);
1720 free_history_vect (EXPR_HISTORY_OF_CHANGES (expr));
1723 /* Update target_available bits when merging exprs TO and FROM. SPLIT_POINT
1724 is non-null when expressions are merged from different successors at
1727 update_target_availability (expr_t to, expr_t from, insn_t split_point)
1729 if (EXPR_TARGET_AVAILABLE (to) < 0
1730 || EXPR_TARGET_AVAILABLE (from) < 0)
1731 EXPR_TARGET_AVAILABLE (to) = -1;
1734 /* We try to detect the case when one of the expressions
1735 can only be reached through another one. In this case,
1736 we can do better. */
1737 if (split_point == NULL)
1741 toind = EXPR_ORIG_BB_INDEX (to);
1742 fromind = EXPR_ORIG_BB_INDEX (from);
1744 if (toind && toind == fromind)
1745 /* Do nothing -- everything is done in
1746 merge_with_other_exprs. */
1749 EXPR_TARGET_AVAILABLE (to) = -1;
1751 else if (EXPR_TARGET_AVAILABLE (from) == 0
1753 && REG_P (EXPR_LHS (from))
1754 && REGNO (EXPR_LHS (to)) != REGNO (EXPR_LHS (from)))
1755 EXPR_TARGET_AVAILABLE (to) = -1;
1757 EXPR_TARGET_AVAILABLE (to) &= EXPR_TARGET_AVAILABLE (from);
1761 /* Update speculation bits when merging exprs TO and FROM. SPLIT_POINT
1762 is non-null when expressions are merged from different successors at
1765 update_speculative_bits (expr_t to, expr_t from, insn_t split_point)
1767 ds_t old_to_ds, old_from_ds;
1769 old_to_ds = EXPR_SPEC_DONE_DS (to);
1770 old_from_ds = EXPR_SPEC_DONE_DS (from);
1772 EXPR_SPEC_DONE_DS (to) = ds_max_merge (old_to_ds, old_from_ds);
1773 EXPR_SPEC_TO_CHECK_DS (to) |= EXPR_SPEC_TO_CHECK_DS (from);
1774 EXPR_NEEDS_SPEC_CHECK_P (to) |= EXPR_NEEDS_SPEC_CHECK_P (from);
1776 /* When merging e.g. control & data speculative exprs, or a control
1777 speculative with a control&data speculative one, we really have
1778 to change vinsn too. Also, when speculative status is changed,
1779 we also need to record this as a transformation in expr's history. */
1780 if ((old_to_ds & SPECULATIVE) || (old_from_ds & SPECULATIVE))
1782 old_to_ds = ds_get_speculation_types (old_to_ds);
1783 old_from_ds = ds_get_speculation_types (old_from_ds);
1785 if (old_to_ds != old_from_ds)
1789 /* When both expressions are speculative, we need to change
1791 if ((old_to_ds & SPECULATIVE) && (old_from_ds & SPECULATIVE))
1795 res = speculate_expr (to, EXPR_SPEC_DONE_DS (to));
1796 gcc_assert (res >= 0);
1799 if (split_point != NULL)
1801 /* Record the change with proper status. */
1802 record_ds = EXPR_SPEC_DONE_DS (to) & SPECULATIVE;
1803 record_ds &= ~(old_to_ds & SPECULATIVE);
1804 record_ds &= ~(old_from_ds & SPECULATIVE);
1806 insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (to),
1807 INSN_UID (split_point), TRANS_SPECULATION,
1808 EXPR_VINSN (from), EXPR_VINSN (to),
1816 /* Merge bits of FROM expr to TO expr. When SPLIT_POINT is not NULL,
1817 this is done along different paths. */
1819 merge_expr_data (expr_t to, expr_t from, insn_t split_point)
1821 /* Choose the maximum of the specs of merged exprs. This is required
1822 for correctness of bookkeeping. */
1823 if (EXPR_SPEC (to) < EXPR_SPEC (from))
1824 EXPR_SPEC (to) = EXPR_SPEC (from);
1827 EXPR_USEFULNESS (to) += EXPR_USEFULNESS (from);
1829 EXPR_USEFULNESS (to) = MAX (EXPR_USEFULNESS (to),
1830 EXPR_USEFULNESS (from));
1832 if (EXPR_PRIORITY (to) < EXPR_PRIORITY (from))
1833 EXPR_PRIORITY (to) = EXPR_PRIORITY (from);
1835 /* We merge sched-times half-way to the larger value to avoid the endless
1836 pipelining of unneeded insns. The average seems to be good compromise
1837 between pipelining opportunities and avoiding extra work. */
1838 if (EXPR_SCHED_TIMES (to) != EXPR_SCHED_TIMES (from))
1839 EXPR_SCHED_TIMES (to) = ((EXPR_SCHED_TIMES (from) + EXPR_SCHED_TIMES (to)
1842 if (EXPR_ORIG_BB_INDEX (to) != EXPR_ORIG_BB_INDEX (from))
1843 EXPR_ORIG_BB_INDEX (to) = 0;
1845 EXPR_ORIG_SCHED_CYCLE (to) = MIN (EXPR_ORIG_SCHED_CYCLE (to),
1846 EXPR_ORIG_SCHED_CYCLE (from));
1848 EXPR_WAS_SUBSTITUTED (to) |= EXPR_WAS_SUBSTITUTED (from);
1849 EXPR_WAS_RENAMED (to) |= EXPR_WAS_RENAMED (from);
1850 EXPR_CANT_MOVE (to) |= EXPR_CANT_MOVE (from);
1852 merge_history_vect (&EXPR_HISTORY_OF_CHANGES (to),
1853 EXPR_HISTORY_OF_CHANGES (from));
1854 update_target_availability (to, from, split_point);
1855 update_speculative_bits (to, from, split_point);
1858 /* Merge bits of FROM expr to TO expr. Vinsns in the exprs should be equal
1859 in terms of vinsn_equal_p. SPLIT_POINT is non-null when expressions
1860 are merged from different successors at a split point. */
1862 merge_expr (expr_t to, expr_t from, insn_t split_point)
1864 vinsn_t to_vi = EXPR_VINSN (to);
1865 vinsn_t from_vi = EXPR_VINSN (from);
1867 gcc_assert (vinsn_equal_p (to_vi, from_vi));
1869 /* Make sure that speculative pattern is propagated into exprs that
1870 have non-speculative one. This will provide us with consistent
1871 speculative bits and speculative patterns inside expr. */
1872 if (EXPR_SPEC_DONE_DS (to) == 0
1873 && (EXPR_SPEC_DONE_DS (from) != 0
1874 /* Do likewise for volatile insns, so that we always retain
1875 the may_trap_p bit on the resulting expression. However,
1876 avoid propagating the trapping bit into the instructions
1877 already speculated. This would result in replacing the
1878 speculative pattern with the non-speculative one and breaking
1879 the speculation support. */
1880 || (!VINSN_MAY_TRAP_P (EXPR_VINSN (to))
1881 && VINSN_MAY_TRAP_P (EXPR_VINSN (from)))))
1882 change_vinsn_in_expr (to, EXPR_VINSN (from));
1884 merge_expr_data (to, from, split_point);
1885 gcc_assert (EXPR_USEFULNESS (to) <= REG_BR_PROB_BASE);
1888 /* Clear the information of this EXPR. */
1890 clear_expr (expr_t expr)
1893 vinsn_detach (EXPR_VINSN (expr));
1894 EXPR_VINSN (expr) = NULL;
1896 free_history_vect (EXPR_HISTORY_OF_CHANGES (expr));
1899 /* For a given LV_SET, mark EXPR having unavailable target register. */
1901 set_unavailable_target_for_expr (expr_t expr, regset lv_set)
1903 if (EXPR_SEPARABLE_P (expr))
1905 if (REG_P (EXPR_LHS (expr))
1906 && register_unavailable_p (lv_set, EXPR_LHS (expr)))
1908 /* If it's an insn like r1 = use (r1, ...), and it exists in
1909 different forms in each of the av_sets being merged, we can't say
1910 whether original destination register is available or not.
1911 However, this still works if destination register is not used
1912 in the original expression: if the branch at which LV_SET we're
1913 looking here is not actually 'other branch' in sense that same
1914 expression is available through it (but it can't be determined
1915 at computation stage because of transformations on one of the
1916 branches), it still won't affect the availability.
1917 Liveness of a register somewhere on a code motion path means
1918 it's either read somewhere on a codemotion path, live on
1919 'other' branch, live at the point immediately following
1920 the original operation, or is read by the original operation.
1921 The latter case is filtered out in the condition below.
1922 It still doesn't cover the case when register is defined and used
1923 somewhere within the code motion path, and in this case we could
1924 miss a unifying code motion along both branches using a renamed
1925 register, but it won't affect a code correctness since upon
1926 an actual code motion a bookkeeping code would be generated. */
1927 if (register_unavailable_p (VINSN_REG_USES (EXPR_VINSN (expr)),
1929 EXPR_TARGET_AVAILABLE (expr) = -1;
1931 EXPR_TARGET_AVAILABLE (expr) = false;
1937 reg_set_iterator rsi;
1939 EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_SETS (EXPR_VINSN (expr)),
1941 if (bitmap_bit_p (lv_set, regno))
1943 EXPR_TARGET_AVAILABLE (expr) = false;
1947 EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_CLOBBERS (EXPR_VINSN (expr)),
1949 if (bitmap_bit_p (lv_set, regno))
1951 EXPR_TARGET_AVAILABLE (expr) = false;
1957 /* Try to make EXPR speculative. Return 1 when EXPR's pattern
1958 or dependence status have changed, 2 when also the target register
1959 became unavailable, 0 if nothing had to be changed. */
1961 speculate_expr (expr_t expr, ds_t ds)
1964 rtx_insn *orig_insn_rtx;
1966 ds_t target_ds, current_ds;
1968 /* Obtain the status we need to put on EXPR. */
1969 target_ds = (ds & SPECULATIVE);
1970 current_ds = EXPR_SPEC_DONE_DS (expr);
1971 ds = ds_full_merge (current_ds, target_ds, NULL_RTX, NULL_RTX);
1973 orig_insn_rtx = EXPR_INSN_RTX (expr);
1975 res = sched_speculate_insn (orig_insn_rtx, ds, &spec_pat);
1980 EXPR_SPEC_DONE_DS (expr) = ds;
1981 return current_ds != ds ? 1 : 0;
1985 rtx_insn *spec_insn_rtx =
1986 create_insn_rtx_from_pattern (spec_pat, NULL_RTX);
1987 vinsn_t spec_vinsn = create_vinsn_from_insn_rtx (spec_insn_rtx, false);
1989 change_vinsn_in_expr (expr, spec_vinsn);
1990 EXPR_SPEC_DONE_DS (expr) = ds;
1991 EXPR_NEEDS_SPEC_CHECK_P (expr) = true;
1993 /* Do not allow clobbering the address register of speculative
1995 if (register_unavailable_p (VINSN_REG_USES (EXPR_VINSN (expr)),
1996 expr_dest_reg (expr)))
1998 EXPR_TARGET_AVAILABLE (expr) = false;
2014 /* Return a destination register, if any, of EXPR. */
2016 expr_dest_reg (expr_t expr)
2018 rtx dest = VINSN_LHS (EXPR_VINSN (expr));
2020 if (dest != NULL_RTX && REG_P (dest))
2026 /* Returns the REGNO of the R's destination. */
2028 expr_dest_regno (expr_t expr)
2030 rtx dest = expr_dest_reg (expr);
2032 gcc_assert (dest != NULL_RTX);
2033 return REGNO (dest);
2036 /* For a given LV_SET, mark all expressions in JOIN_SET, but not present in
2037 AV_SET having unavailable target register. */
2039 mark_unavailable_targets (av_set_t join_set, av_set_t av_set, regset lv_set)
2042 av_set_iterator avi;
2044 FOR_EACH_EXPR (expr, avi, join_set)
2045 if (av_set_lookup (av_set, EXPR_VINSN (expr)) == NULL)
2046 set_unavailable_target_for_expr (expr, lv_set);
2050 /* Returns true if REG (at least partially) is present in REGS. */
2052 register_unavailable_p (regset regs, rtx reg)
2054 unsigned regno, end_regno;
2056 regno = REGNO (reg);
2057 if (bitmap_bit_p (regs, regno))
2060 end_regno = END_REGNO (reg);
2062 while (++regno < end_regno)
2063 if (bitmap_bit_p (regs, regno))
2069 /* Av set functions. */
2071 /* Add a new element to av set SETP.
2072 Return the element added. */
2074 av_set_add_element (av_set_t *setp)
2076 /* Insert at the beginning of the list. */
2081 /* Add EXPR to SETP. */
2083 av_set_add (av_set_t *setp, expr_t expr)
2087 gcc_assert (!INSN_NOP_P (EXPR_INSN_RTX (expr)));
2088 elem = av_set_add_element (setp);
2089 copy_expr (_AV_SET_EXPR (elem), expr);
2092 /* Same, but do not copy EXPR. */
2094 av_set_add_nocopy (av_set_t *setp, expr_t expr)
2098 elem = av_set_add_element (setp);
2099 *_AV_SET_EXPR (elem) = *expr;
2102 /* Remove expr pointed to by IP from the av_set. */
2104 av_set_iter_remove (av_set_iterator *ip)
2106 clear_expr (_AV_SET_EXPR (*ip->lp));
2107 _list_iter_remove (ip);
2110 /* Search for an expr in SET, such that it's equivalent to SOUGHT_VINSN in the
2111 sense of vinsn_equal_p function. Return NULL if no such expr is
2112 in SET was found. */
2114 av_set_lookup (av_set_t set, vinsn_t sought_vinsn)
2119 FOR_EACH_EXPR (expr, i, set)
2120 if (vinsn_equal_p (EXPR_VINSN (expr), sought_vinsn))
2125 /* Same, but also remove the EXPR found. */
2127 av_set_lookup_and_remove (av_set_t *setp, vinsn_t sought_vinsn)
2132 FOR_EACH_EXPR_1 (expr, i, setp)
2133 if (vinsn_equal_p (EXPR_VINSN (expr), sought_vinsn))
2135 _list_iter_remove_nofree (&i);
2141 /* Search for an expr in SET, such that it's equivalent to EXPR in the
2142 sense of vinsn_equal_p function of their vinsns, but not EXPR itself.
2143 Returns NULL if no such expr is in SET was found. */
2145 av_set_lookup_other_equiv_expr (av_set_t set, expr_t expr)
2150 FOR_EACH_EXPR (cur_expr, i, set)
2152 if (cur_expr == expr)
2154 if (vinsn_equal_p (EXPR_VINSN (cur_expr), EXPR_VINSN (expr)))
2161 /* If other expression is already in AVP, remove one of them. */
2163 merge_with_other_exprs (av_set_t *avp, av_set_iterator *ip, expr_t expr)
2167 expr2 = av_set_lookup_other_equiv_expr (*avp, expr);
2170 /* Reset target availability on merge, since taking it only from one
2171 of the exprs would be controversial for different code. */
2172 EXPR_TARGET_AVAILABLE (expr2) = -1;
2173 EXPR_USEFULNESS (expr2) = 0;
2175 merge_expr (expr2, expr, NULL);
2177 /* Fix usefulness as it should be now REG_BR_PROB_BASE. */
2178 EXPR_USEFULNESS (expr2) = REG_BR_PROB_BASE;
2180 av_set_iter_remove (ip);
2187 /* Return true if there is an expr that correlates to VI in SET. */
2189 av_set_is_in_p (av_set_t set, vinsn_t vi)
2191 return av_set_lookup (set, vi) != NULL;
2194 /* Return a copy of SET. */
2196 av_set_copy (av_set_t set)
2200 av_set_t res = NULL;
2202 FOR_EACH_EXPR (expr, i, set)
2203 av_set_add (&res, expr);
2208 /* Join two av sets that do not have common elements by attaching second set
2209 (pointed to by FROMP) to the end of first set (TO_TAILP must point to
2210 _AV_SET_NEXT of first set's last element). */
2212 join_distinct_sets (av_set_t *to_tailp, av_set_t *fromp)
2214 gcc_assert (*to_tailp == NULL);
2219 /* Makes set pointed to by TO to be the union of TO and FROM. Clear av_set
2220 pointed to by FROMP afterwards. */
2222 av_set_union_and_clear (av_set_t *top, av_set_t *fromp, insn_t insn)
2227 /* Delete from TOP all exprs, that present in FROMP. */
2228 FOR_EACH_EXPR_1 (expr1, i, top)
2230 expr_t expr2 = av_set_lookup (*fromp, EXPR_VINSN (expr1));
2234 merge_expr (expr2, expr1, insn);
2235 av_set_iter_remove (&i);
2239 join_distinct_sets (i.lp, fromp);
2242 /* Same as above, but also update availability of target register in
2243 TOP judging by TO_LV_SET and FROM_LV_SET. */
2245 av_set_union_and_live (av_set_t *top, av_set_t *fromp, regset to_lv_set,
2246 regset from_lv_set, insn_t insn)
2250 av_set_t *to_tailp, in_both_set = NULL;
2252 /* Delete from TOP all expres, that present in FROMP. */
2253 FOR_EACH_EXPR_1 (expr1, i, top)
2255 expr_t expr2 = av_set_lookup_and_remove (fromp, EXPR_VINSN (expr1));
2259 /* It may be that the expressions have different destination
2260 registers, in which case we need to check liveness here. */
2261 if (EXPR_SEPARABLE_P (expr1))
2263 int regno1 = (REG_P (EXPR_LHS (expr1))
2264 ? (int) expr_dest_regno (expr1) : -1);
2265 int regno2 = (REG_P (EXPR_LHS (expr2))
2266 ? (int) expr_dest_regno (expr2) : -1);
2268 /* ??? We don't have a way to check restrictions for
2269 *other* register on the current path, we did it only
2270 for the current target register. Give up. */
2271 if (regno1 != regno2)
2272 EXPR_TARGET_AVAILABLE (expr2) = -1;
2274 else if (EXPR_INSN_RTX (expr1) != EXPR_INSN_RTX (expr2))
2275 EXPR_TARGET_AVAILABLE (expr2) = -1;
2277 merge_expr (expr2, expr1, insn);
2278 av_set_add_nocopy (&in_both_set, expr2);
2279 av_set_iter_remove (&i);
2282 /* EXPR1 is present in TOP, but not in FROMP. Check it on
2284 set_unavailable_target_for_expr (expr1, from_lv_set);
2288 /* These expressions are not present in TOP. Check liveness
2289 restrictions on TO_LV_SET. */
2290 FOR_EACH_EXPR (expr1, i, *fromp)
2291 set_unavailable_target_for_expr (expr1, to_lv_set);
2293 join_distinct_sets (i.lp, &in_both_set);
2294 join_distinct_sets (to_tailp, fromp);
2297 /* Clear av_set pointed to by SETP. */
2299 av_set_clear (av_set_t *setp)
2304 FOR_EACH_EXPR_1 (expr, i, setp)
2305 av_set_iter_remove (&i);
2307 gcc_assert (*setp == NULL);
2310 /* Leave only one non-speculative element in the SETP. */
2312 av_set_leave_one_nonspec (av_set_t *setp)
2316 bool has_one_nonspec = false;
2318 /* Keep all speculative exprs, and leave one non-speculative
2320 FOR_EACH_EXPR_1 (expr, i, setp)
2322 if (!EXPR_SPEC_DONE_DS (expr))
2324 if (has_one_nonspec)
2325 av_set_iter_remove (&i);
2327 has_one_nonspec = true;
2332 /* Return the N'th element of the SET. */
2334 av_set_element (av_set_t set, int n)
2339 FOR_EACH_EXPR (expr, i, set)
2347 /* Deletes all expressions from AVP that are conditional branches (IFs). */
2349 av_set_substract_cond_branches (av_set_t *avp)
2354 FOR_EACH_EXPR_1 (expr, i, avp)
2355 if (vinsn_cond_branch_p (EXPR_VINSN (expr)))
2356 av_set_iter_remove (&i);
2359 /* Multiplies usefulness attribute of each member of av-set *AVP by
2360 value PROB / ALL_PROB. */
2362 av_set_split_usefulness (av_set_t av, int prob, int all_prob)
2367 FOR_EACH_EXPR (expr, i, av)
2368 EXPR_USEFULNESS (expr) = (all_prob
2369 ? (EXPR_USEFULNESS (expr) * prob) / all_prob
2373 /* Leave in AVP only those expressions, which are present in AV,
2374 and return it, merging history expressions. */
2376 av_set_code_motion_filter (av_set_t *avp, av_set_t av)
2381 FOR_EACH_EXPR_1 (expr, i, avp)
2382 if ((expr2 = av_set_lookup (av, EXPR_VINSN (expr))) == NULL)
2383 av_set_iter_remove (&i);
2385 /* When updating av sets in bookkeeping blocks, we can add more insns
2386 there which will be transformed but the upper av sets will not
2387 reflect those transformations. We then fail to undo those
2388 when searching for such insns. So merge the history saved
2389 in the av set of the block we are processing. */
2390 merge_history_vect (&EXPR_HISTORY_OF_CHANGES (expr),
2391 EXPR_HISTORY_OF_CHANGES (expr2));
2396 /* Dependence hooks to initialize insn data. */
2398 /* This is used in hooks callable from dependence analysis when initializing
2399 instruction's data. */
2402 /* Where the dependence was found (lhs/rhs). */
2405 /* The actual data object to initialize. */
2408 /* True when the insn should not be made clonable. */
2409 bool force_unique_p;
2411 /* True when insn should be treated as of type USE, i.e. never renamed. */
2413 } deps_init_id_data;
2416 /* Setup ID for INSN. FORCE_UNIQUE_P is true when INSN should not be
2419 setup_id_for_insn (idata_t id, insn_t insn, bool force_unique_p)
2423 /* Determine whether INSN could be cloned and return appropriate vinsn type.
2424 That clonable insns which can be separated into lhs and rhs have type SET.
2425 Other clonable insns have type USE. */
2426 type = GET_CODE (insn);
2428 /* Only regular insns could be cloned. */
2429 if (type == INSN && !force_unique_p)
2431 else if (type == JUMP_INSN && simplejump_p (insn))
2433 else if (type == DEBUG_INSN)
2434 type = !force_unique_p ? USE : INSN;
2436 IDATA_TYPE (id) = type;
2437 IDATA_REG_SETS (id) = get_clear_regset_from_pool ();
2438 IDATA_REG_USES (id) = get_clear_regset_from_pool ();
2439 IDATA_REG_CLOBBERS (id) = get_clear_regset_from_pool ();
2442 /* Start initializing insn data. */
2444 deps_init_id_start_insn (insn_t insn)
2446 gcc_assert (deps_init_id_data.where == DEPS_IN_NOWHERE);
2448 setup_id_for_insn (deps_init_id_data.id, insn,
2449 deps_init_id_data.force_unique_p);
2450 deps_init_id_data.where = DEPS_IN_INSN;
2453 /* Start initializing lhs data. */
2455 deps_init_id_start_lhs (rtx lhs)
2457 gcc_assert (deps_init_id_data.where == DEPS_IN_INSN);
2458 gcc_assert (IDATA_LHS (deps_init_id_data.id) == NULL);
2460 if (IDATA_TYPE (deps_init_id_data.id) == SET)
2462 IDATA_LHS (deps_init_id_data.id) = lhs;
2463 deps_init_id_data.where = DEPS_IN_LHS;
2467 /* Finish initializing lhs data. */
2469 deps_init_id_finish_lhs (void)
2471 deps_init_id_data.where = DEPS_IN_INSN;
2474 /* Note a set of REGNO. */
2476 deps_init_id_note_reg_set (int regno)
2478 haifa_note_reg_set (regno);
2480 if (deps_init_id_data.where == DEPS_IN_RHS)
2481 deps_init_id_data.force_use_p = true;
2483 if (IDATA_TYPE (deps_init_id_data.id) != PC)
2484 SET_REGNO_REG_SET (IDATA_REG_SETS (deps_init_id_data.id), regno);
2487 /* Make instructions that set stack registers to be ineligible for
2488 renaming to avoid issues with find_used_regs. */
2489 if (IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG))
2490 deps_init_id_data.force_use_p = true;
2494 /* Note a clobber of REGNO. */
2496 deps_init_id_note_reg_clobber (int regno)
2498 haifa_note_reg_clobber (regno);
2500 if (deps_init_id_data.where == DEPS_IN_RHS)
2501 deps_init_id_data.force_use_p = true;
2503 if (IDATA_TYPE (deps_init_id_data.id) != PC)
2504 SET_REGNO_REG_SET (IDATA_REG_CLOBBERS (deps_init_id_data.id), regno);
2507 /* Note a use of REGNO. */
2509 deps_init_id_note_reg_use (int regno)
2511 haifa_note_reg_use (regno);
2513 if (IDATA_TYPE (deps_init_id_data.id) != PC)
2514 SET_REGNO_REG_SET (IDATA_REG_USES (deps_init_id_data.id), regno);
2517 /* Start initializing rhs data. */
2519 deps_init_id_start_rhs (rtx rhs)
2521 gcc_assert (deps_init_id_data.where == DEPS_IN_INSN);
2523 /* And there was no sel_deps_reset_to_insn (). */
2524 if (IDATA_LHS (deps_init_id_data.id) != NULL)
2526 IDATA_RHS (deps_init_id_data.id) = rhs;
2527 deps_init_id_data.where = DEPS_IN_RHS;
2531 /* Finish initializing rhs data. */
2533 deps_init_id_finish_rhs (void)
2535 gcc_assert (deps_init_id_data.where == DEPS_IN_RHS
2536 || deps_init_id_data.where == DEPS_IN_INSN);
2537 deps_init_id_data.where = DEPS_IN_INSN;
2540 /* Finish initializing insn data. */
2542 deps_init_id_finish_insn (void)
2544 gcc_assert (deps_init_id_data.where == DEPS_IN_INSN);
2546 if (IDATA_TYPE (deps_init_id_data.id) == SET)
2548 rtx lhs = IDATA_LHS (deps_init_id_data.id);
2549 rtx rhs = IDATA_RHS (deps_init_id_data.id);
2551 if (lhs == NULL || rhs == NULL || !lhs_and_rhs_separable_p (lhs, rhs)
2552 || deps_init_id_data.force_use_p)
2554 /* This should be a USE, as we don't want to schedule its RHS
2555 separately. However, we still want to have them recorded
2556 for the purposes of substitution. That's why we don't
2557 simply call downgrade_to_use () here. */
2558 gcc_assert (IDATA_TYPE (deps_init_id_data.id) == SET);
2559 gcc_assert (!lhs == !rhs);
2561 IDATA_TYPE (deps_init_id_data.id) = USE;
2565 deps_init_id_data.where = DEPS_IN_NOWHERE;
2568 /* This is dependence info used for initializing insn's data. */
2569 static struct sched_deps_info_def deps_init_id_sched_deps_info;
2571 /* This initializes most of the static part of the above structure. */
2572 static const struct sched_deps_info_def const_deps_init_id_sched_deps_info =
2576 deps_init_id_start_insn,
2577 deps_init_id_finish_insn,
2578 deps_init_id_start_lhs,
2579 deps_init_id_finish_lhs,
2580 deps_init_id_start_rhs,
2581 deps_init_id_finish_rhs,
2582 deps_init_id_note_reg_set,
2583 deps_init_id_note_reg_clobber,
2584 deps_init_id_note_reg_use,
2585 NULL, /* note_mem_dep */
2586 NULL, /* note_dep */
2589 0, /* use_deps_list */
2590 0 /* generate_spec_deps */
2593 /* Initialize INSN's lhs and rhs in ID. When FORCE_UNIQUE_P is true,
2594 we don't actually need information about lhs and rhs. */
2596 setup_id_lhs_rhs (idata_t id, insn_t insn, bool force_unique_p)
2598 rtx pat = PATTERN (insn);
2600 if (NONJUMP_INSN_P (insn)
2601 && GET_CODE (pat) == SET
2604 IDATA_RHS (id) = SET_SRC (pat);
2605 IDATA_LHS (id) = SET_DEST (pat);
2608 IDATA_LHS (id) = IDATA_RHS (id) = NULL;
2611 /* Possibly downgrade INSN to USE. */
2613 maybe_downgrade_id_to_use (idata_t id, insn_t insn)
2615 bool must_be_use = false;
2617 rtx lhs = IDATA_LHS (id);
2618 rtx rhs = IDATA_RHS (id);
2620 /* We downgrade only SETs. */
2621 if (IDATA_TYPE (id) != SET)
2624 if (!lhs || !lhs_and_rhs_separable_p (lhs, rhs))
2626 IDATA_TYPE (id) = USE;
2630 FOR_EACH_INSN_DEF (def, insn)
2632 if (DF_REF_INSN (def)
2633 && DF_REF_FLAGS_IS_SET (def, DF_REF_PRE_POST_MODIFY)
2634 && loc_mentioned_in_p (DF_REF_LOC (def), IDATA_RHS (id)))
2641 /* Make instructions that set stack registers to be ineligible for
2642 renaming to avoid issues with find_used_regs. */
2643 if (IN_RANGE (DF_REF_REGNO (def), FIRST_STACK_REG, LAST_STACK_REG))
2652 IDATA_TYPE (id) = USE;
2655 /* Setup implicit register clobbers calculated by sched-deps for INSN
2656 before reload and save them in ID. */
2658 setup_id_implicit_regs (idata_t id, insn_t insn)
2660 if (reload_completed)
2665 hard_reg_set_iterator hrsi;
2667 get_implicit_reg_pending_clobbers (&temp, insn);
2668 EXECUTE_IF_SET_IN_HARD_REG_SET (temp, 0, regno, hrsi)
2669 SET_REGNO_REG_SET (IDATA_REG_SETS (id), regno);
2672 /* Setup register sets describing INSN in ID. */
2674 setup_id_reg_sets (idata_t id, insn_t insn)
2676 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2678 regset tmp = get_clear_regset_from_pool ();
2680 FOR_EACH_INSN_INFO_DEF (def, insn_info)
2682 unsigned int regno = DF_REF_REGNO (def);
2684 /* Post modifies are treated like clobbers by sched-deps.c. */
2685 if (DF_REF_FLAGS_IS_SET (def, (DF_REF_MUST_CLOBBER
2686 | DF_REF_PRE_POST_MODIFY)))
2687 SET_REGNO_REG_SET (IDATA_REG_CLOBBERS (id), regno);
2688 else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
2690 SET_REGNO_REG_SET (IDATA_REG_SETS (id), regno);
2693 /* For stack registers, treat writes to them as writes
2694 to the first one to be consistent with sched-deps.c. */
2695 if (IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG))
2696 SET_REGNO_REG_SET (IDATA_REG_SETS (id), FIRST_STACK_REG);
2699 /* Mark special refs that generate read/write def pair. */
2700 if (DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL)
2701 || regno == STACK_POINTER_REGNUM)
2702 bitmap_set_bit (tmp, regno);
2705 FOR_EACH_INSN_INFO_USE (use, insn_info)
2707 unsigned int regno = DF_REF_REGNO (use);
2709 /* When these refs are met for the first time, skip them, as
2710 these uses are just counterparts of some defs. */
2711 if (bitmap_bit_p (tmp, regno))
2712 bitmap_clear_bit (tmp, regno);
2713 else if (! DF_REF_FLAGS_IS_SET (use, DF_REF_CALL_STACK_USAGE))
2715 SET_REGNO_REG_SET (IDATA_REG_USES (id), regno);
2718 /* For stack registers, treat reads from them as reads from
2719 the first one to be consistent with sched-deps.c. */
2720 if (IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG))
2721 SET_REGNO_REG_SET (IDATA_REG_USES (id), FIRST_STACK_REG);
2726 /* Also get implicit reg clobbers from sched-deps. */
2727 setup_id_implicit_regs (id, insn);
2729 return_regset_to_pool (tmp);
2732 /* Initialize instruction data for INSN in ID using DF's data. */
2734 init_id_from_df (idata_t id, insn_t insn, bool force_unique_p)
2736 gcc_assert (DF_INSN_UID_SAFE_GET (INSN_UID (insn)) != NULL);
2738 setup_id_for_insn (id, insn, force_unique_p);
2739 setup_id_lhs_rhs (id, insn, force_unique_p);
2741 if (INSN_NOP_P (insn))
2744 maybe_downgrade_id_to_use (id, insn);
2745 setup_id_reg_sets (id, insn);
2748 /* Initialize instruction data for INSN in ID. */
2750 deps_init_id (idata_t id, insn_t insn, bool force_unique_p)
2752 class deps_desc _dc, *dc = &_dc;
2754 deps_init_id_data.where = DEPS_IN_NOWHERE;
2755 deps_init_id_data.id = id;
2756 deps_init_id_data.force_unique_p = force_unique_p;
2757 deps_init_id_data.force_use_p = false;
2759 init_deps (dc, false);
2760 memcpy (&deps_init_id_sched_deps_info,
2761 &const_deps_init_id_sched_deps_info,
2762 sizeof (deps_init_id_sched_deps_info));
2763 if (spec_info != NULL)
2764 deps_init_id_sched_deps_info.generate_spec_deps = 1;
2765 sched_deps_info = &deps_init_id_sched_deps_info;
2767 deps_analyze_insn (dc, insn);
2768 /* Implicit reg clobbers received from sched-deps separately. */
2769 setup_id_implicit_regs (id, insn);
2772 deps_init_id_data.id = NULL;
2776 struct sched_scan_info_def
2778 /* This hook notifies scheduler frontend to extend its internal per basic
2779 block data structures. This hook should be called once before a series of
2780 calls to bb_init (). */
2781 void (*extend_bb) (void);
2783 /* This hook makes scheduler frontend to initialize its internal data
2784 structures for the passed basic block. */
2785 void (*init_bb) (basic_block);
2787 /* This hook notifies scheduler frontend to extend its internal per insn data
2788 structures. This hook should be called once before a series of calls to
2790 void (*extend_insn) (void);
2792 /* This hook makes scheduler frontend to initialize its internal data
2793 structures for the passed insn. */
2794 void (*init_insn) (insn_t);
2797 /* A driver function to add a set of basic blocks (BBS) to the
2798 scheduling region. */
2800 sched_scan (const struct sched_scan_info_def *ssi, bb_vec_t bbs)
2809 FOR_EACH_VEC_ELT (bbs, i, bb)
2812 if (ssi->extend_insn)
2813 ssi->extend_insn ();
2816 FOR_EACH_VEC_ELT (bbs, i, bb)
2820 FOR_BB_INSNS (bb, insn)
2821 ssi->init_insn (insn);
2825 /* Implement hooks for collecting fundamental insn properties like if insn is
2826 an ASM or is within a SCHED_GROUP. */
2828 /* True when a "one-time init" data for INSN was already inited. */
2830 first_time_insn_init (insn_t insn)
2832 return INSN_LIVE (insn) == NULL;
2835 /* Hash an entry in a transformed_insns hashtable. */
2837 hash_transformed_insns (const void *p)
2839 return VINSN_HASH_RTX (((const struct transformed_insns *) p)->vinsn_old);
2842 /* Compare the entries in a transformed_insns hashtable. */
2844 eq_transformed_insns (const void *p, const void *q)
2847 VINSN_INSN_RTX (((const struct transformed_insns *) p)->vinsn_old);
2849 VINSN_INSN_RTX (((const struct transformed_insns *) q)->vinsn_old);
2851 if (INSN_UID (i1) == INSN_UID (i2))
2853 return rtx_equal_p (PATTERN (i1), PATTERN (i2));
2856 /* Free an entry in a transformed_insns hashtable. */
2858 free_transformed_insns (void *p)
2860 struct transformed_insns *pti = (struct transformed_insns *) p;
2862 vinsn_detach (pti->vinsn_old);
2863 vinsn_detach (pti->vinsn_new);
2867 /* Init the s_i_d data for INSN which should be inited just once, when
2868 we first see the insn. */
2870 init_first_time_insn_data (insn_t insn)
2872 /* This should not be set if this is the first time we init data for
2874 gcc_assert (first_time_insn_init (insn));
2876 /* These are needed for nops too. */
2877 INSN_LIVE (insn) = get_regset_from_pool ();
2878 INSN_LIVE_VALID_P (insn) = false;
2880 if (!INSN_NOP_P (insn))
2882 INSN_ANALYZED_DEPS (insn) = BITMAP_ALLOC (NULL);
2883 INSN_FOUND_DEPS (insn) = BITMAP_ALLOC (NULL);
2884 INSN_TRANSFORMED_INSNS (insn)
2885 = htab_create (16, hash_transformed_insns,
2886 eq_transformed_insns, free_transformed_insns);
2887 init_deps (&INSN_DEPS_CONTEXT (insn), true);
2891 /* Free almost all above data for INSN that is scheduled already.
2892 Used for extra-large basic blocks. */
2894 free_data_for_scheduled_insn (insn_t insn)
2896 gcc_assert (! first_time_insn_init (insn));
2898 if (! INSN_ANALYZED_DEPS (insn))
2901 BITMAP_FREE (INSN_ANALYZED_DEPS (insn));
2902 BITMAP_FREE (INSN_FOUND_DEPS (insn));
2903 htab_delete (INSN_TRANSFORMED_INSNS (insn));
2905 /* This is allocated only for bookkeeping insns. */
2906 if (INSN_ORIGINATORS (insn))
2907 BITMAP_FREE (INSN_ORIGINATORS (insn));
2908 free_deps (&INSN_DEPS_CONTEXT (insn));
2910 INSN_ANALYZED_DEPS (insn) = NULL;
2912 /* Clear the readonly flag so we would ICE when trying to recalculate
2913 the deps context (as we believe that it should not happen). */
2914 (&INSN_DEPS_CONTEXT (insn))->readonly = 0;
2917 /* Free the same data as above for INSN. */
2919 free_first_time_insn_data (insn_t insn)
2921 gcc_assert (! first_time_insn_init (insn));
2923 free_data_for_scheduled_insn (insn);
2924 return_regset_to_pool (INSN_LIVE (insn));
2925 INSN_LIVE (insn) = NULL;
2926 INSN_LIVE_VALID_P (insn) = false;
2929 /* Initialize region-scope data structures for basic blocks. */
2931 init_global_and_expr_for_bb (basic_block bb)
2933 if (sel_bb_empty_p (bb))
2936 invalidate_av_set (bb);
2939 /* Data for global dependency analysis (to initialize CANT_MOVE and
2943 /* Previous insn. */
2947 /* Determine if INSN is in the sched_group, is an asm or should not be
2948 cloned. After that initialize its expr. */
2950 init_global_and_expr_for_insn (insn_t insn)
2955 if (NOTE_INSN_BASIC_BLOCK_P (insn))
2957 init_global_data.prev_insn = NULL;
2961 gcc_assert (INSN_P (insn));
2963 if (SCHED_GROUP_P (insn))
2964 /* Setup a sched_group. */
2966 insn_t prev_insn = init_global_data.prev_insn;
2969 INSN_SCHED_NEXT (prev_insn) = insn;
2971 init_global_data.prev_insn = insn;
2974 init_global_data.prev_insn = NULL;
2976 if (GET_CODE (PATTERN (insn)) == ASM_INPUT
2977 || asm_noperands (PATTERN (insn)) >= 0)
2978 /* Mark INSN as an asm. */
2979 INSN_ASM_P (insn) = true;
2982 bool force_unique_p;
2985 /* Certain instructions cannot be cloned, and frame related insns and
2986 the insn adjacent to NOTE_INSN_EPILOGUE_BEG cannot be moved out of
2988 if (prologue_epilogue_contains (insn))
2990 if (RTX_FRAME_RELATED_P (insn))
2991 CANT_MOVE (insn) = 1;
2995 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
2996 if (REG_NOTE_KIND (note) == REG_SAVE_NOTE
2997 && ((enum insn_note) INTVAL (XEXP (note, 0))
2998 == NOTE_INSN_EPILOGUE_BEG))
3000 CANT_MOVE (insn) = 1;
3004 force_unique_p = true;
3007 if (CANT_MOVE (insn)
3008 || INSN_ASM_P (insn)
3009 || SCHED_GROUP_P (insn)
3011 /* Exception handling insns are always unique. */
3012 || (cfun->can_throw_non_call_exceptions && can_throw_internal (insn))
3013 /* TRAP_IF though have an INSN code is control_flow_insn_p (). */
3014 || control_flow_insn_p (insn)
3015 || volatile_insn_p (PATTERN (insn))
3016 || (targetm.cannot_copy_insn_p
3017 && targetm.cannot_copy_insn_p (insn)))
3018 force_unique_p = true;
3020 force_unique_p = false;
3022 if (targetm.sched.get_insn_spec_ds)
3024 spec_done_ds = targetm.sched.get_insn_spec_ds (insn);
3025 spec_done_ds = ds_get_max_dep_weak (spec_done_ds);
3030 /* Initialize INSN's expr. */
3031 init_expr (INSN_EXPR (insn), vinsn_create (insn, force_unique_p), 0,
3032 REG_BR_PROB_BASE, INSN_PRIORITY (insn), 0, BLOCK_NUM (insn),
3033 spec_done_ds, 0, 0, vNULL, true,
3034 false, false, false, CANT_MOVE (insn));
3037 init_first_time_insn_data (insn);
3040 /* Scan the region and initialize instruction data for basic blocks BBS. */
3042 sel_init_global_and_expr (bb_vec_t bbs)
3044 /* ??? It would be nice to implement push / pop scheme for sched_infos. */
3045 const struct sched_scan_info_def ssi =
3047 NULL, /* extend_bb */
3048 init_global_and_expr_for_bb, /* init_bb */
3049 extend_insn_data, /* extend_insn */
3050 init_global_and_expr_for_insn /* init_insn */
3053 sched_scan (&ssi, bbs);
3056 /* Finalize region-scope data structures for basic blocks. */
3058 finish_global_and_expr_for_bb (basic_block bb)
3060 av_set_clear (&BB_AV_SET (bb));
3061 BB_AV_LEVEL (bb) = 0;
3064 /* Finalize INSN's data. */
3066 finish_global_and_expr_insn (insn_t insn)
3068 if (LABEL_P (insn) || NOTE_INSN_BASIC_BLOCK_P (insn))
3071 gcc_assert (INSN_P (insn));
3073 if (INSN_LUID (insn) > 0)
3075 free_first_time_insn_data (insn);
3076 INSN_WS_LEVEL (insn) = 0;
3077 CANT_MOVE (insn) = 0;
3079 /* We can no longer assert this, as vinsns of this insn could be
3080 easily live in other insn's caches. This should be changed to
3081 a counter-like approach among all vinsns. */
3082 gcc_assert (true || VINSN_COUNT (INSN_VINSN (insn)) == 1);
3083 clear_expr (INSN_EXPR (insn));
3087 /* Finalize per instruction data for the whole region. */
3089 sel_finish_global_and_expr (void)
3095 bbs.create (current_nr_blocks);
3097 for (i = 0; i < current_nr_blocks; i++)
3098 bbs.quick_push (BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (i)));
3100 /* Clear AV_SETs and INSN_EXPRs. */
3102 const struct sched_scan_info_def ssi =
3104 NULL, /* extend_bb */
3105 finish_global_and_expr_for_bb, /* init_bb */
3106 NULL, /* extend_insn */
3107 finish_global_and_expr_insn /* init_insn */
3110 sched_scan (&ssi, bbs);
3120 /* In the below hooks, we merely calculate whether or not a dependence
3121 exists, and in what part of insn. However, we will need more data
3122 when we'll start caching dependence requests. */
3124 /* Container to hold information for dependency analysis. */
3129 /* A variable to track which part of rtx we are scanning in
3130 sched-deps.c: sched_analyze_insn (). */
3133 /* Current producer. */
3136 /* Current consumer. */
3139 /* Is SEL_DEPS_HAS_DEP_P[DEPS_IN_X] is true, then X has a dependence.
3140 X is from { INSN, LHS, RHS }. */
3141 ds_t has_dep_p[DEPS_IN_NOWHERE];
3142 } has_dependence_data;
3144 /* Start analyzing dependencies of INSN. */
3146 has_dependence_start_insn (insn_t insn ATTRIBUTE_UNUSED)
3148 gcc_assert (has_dependence_data.where == DEPS_IN_NOWHERE);
3150 has_dependence_data.where = DEPS_IN_INSN;
3153 /* Finish analyzing dependencies of an insn. */
3155 has_dependence_finish_insn (void)
3157 gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
3159 has_dependence_data.where = DEPS_IN_NOWHERE;
3162 /* Start analyzing dependencies of LHS. */
3164 has_dependence_start_lhs (rtx lhs ATTRIBUTE_UNUSED)
3166 gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
3168 if (VINSN_LHS (has_dependence_data.con) != NULL)
3169 has_dependence_data.where = DEPS_IN_LHS;
3172 /* Finish analyzing dependencies of an lhs. */
3174 has_dependence_finish_lhs (void)
3176 has_dependence_data.where = DEPS_IN_INSN;
3179 /* Start analyzing dependencies of RHS. */
3181 has_dependence_start_rhs (rtx rhs ATTRIBUTE_UNUSED)
3183 gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
3185 if (VINSN_RHS (has_dependence_data.con) != NULL)
3186 has_dependence_data.where = DEPS_IN_RHS;
3189 /* Start analyzing dependencies of an rhs. */
3191 has_dependence_finish_rhs (void)
3193 gcc_assert (has_dependence_data.where == DEPS_IN_RHS
3194 || has_dependence_data.where == DEPS_IN_INSN);
3196 has_dependence_data.where = DEPS_IN_INSN;
3199 /* Note a set of REGNO. */
3201 has_dependence_note_reg_set (int regno)
3203 struct deps_reg *reg_last = &has_dependence_data.dc->reg_last[regno];
3205 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3207 (has_dependence_data.con)))
3209 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3211 if (reg_last->sets != NULL
3212 || reg_last->clobbers != NULL)
3213 *dsp = (*dsp & ~SPECULATIVE) | DEP_OUTPUT;
3215 if (reg_last->uses || reg_last->implicit_sets)
3216 *dsp = (*dsp & ~SPECULATIVE) | DEP_ANTI;
3220 /* Note a clobber of REGNO. */
3222 has_dependence_note_reg_clobber (int regno)
3224 struct deps_reg *reg_last = &has_dependence_data.dc->reg_last[regno];
3226 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3228 (has_dependence_data.con)))
3230 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3233 *dsp = (*dsp & ~SPECULATIVE) | DEP_OUTPUT;
3235 if (reg_last->uses || reg_last->implicit_sets)
3236 *dsp = (*dsp & ~SPECULATIVE) | DEP_ANTI;
3240 /* Note a use of REGNO. */
3242 has_dependence_note_reg_use (int regno)
3244 struct deps_reg *reg_last = &has_dependence_data.dc->reg_last[regno];
3246 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3248 (has_dependence_data.con)))
3250 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3253 *dsp = (*dsp & ~SPECULATIVE) | DEP_TRUE;
3255 if (reg_last->clobbers || reg_last->implicit_sets)
3256 *dsp = (*dsp & ~SPECULATIVE) | DEP_ANTI;
3258 /* Merge BE_IN_SPEC bits into *DSP when the dependency producer
3259 is actually a check insn. We need to do this for any register
3260 read-read dependency with the check unless we track properly
3261 all registers written by BE_IN_SPEC-speculated insns, as
3262 we don't have explicit dependence lists. See PR 53975. */
3265 ds_t pro_spec_checked_ds;
3267 pro_spec_checked_ds = INSN_SPEC_CHECKED_DS (has_dependence_data.pro);
3268 pro_spec_checked_ds = ds_get_max_dep_weak (pro_spec_checked_ds);
3270 if (pro_spec_checked_ds != 0)
3271 *dsp = ds_full_merge (*dsp, pro_spec_checked_ds,
3272 NULL_RTX, NULL_RTX);
3277 /* Note a memory dependence. */
3279 has_dependence_note_mem_dep (rtx mem ATTRIBUTE_UNUSED,
3280 rtx pending_mem ATTRIBUTE_UNUSED,
3281 insn_t pending_insn ATTRIBUTE_UNUSED,
3282 ds_t ds ATTRIBUTE_UNUSED)
3284 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3285 VINSN_INSN_RTX (has_dependence_data.con)))
3287 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3289 *dsp = ds_full_merge (ds, *dsp, pending_mem, mem);
3293 /* Note a dependence. */
3295 has_dependence_note_dep (insn_t pro, ds_t ds ATTRIBUTE_UNUSED)
3297 insn_t real_pro = has_dependence_data.pro;
3298 insn_t real_con = VINSN_INSN_RTX (has_dependence_data.con);
3300 /* We do not allow for debug insns to move through others unless they
3301 are at the start of bb. This movement may create bookkeeping copies
3302 that later would not be able to move up, violating the invariant
3303 that a bookkeeping copy should be movable as the original insn.
3304 Detect that here and allow that movement if we allowed it before
3305 in the first place. */
3306 if (DEBUG_INSN_P (real_con) && !DEBUG_INSN_P (real_pro)
3307 && INSN_UID (NEXT_INSN (pro)) == INSN_UID (real_con))
3310 if (!sched_insns_conditions_mutex_p (real_pro, real_con))
3312 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3314 *dsp = ds_full_merge (ds, *dsp, NULL_RTX, NULL_RTX);
3318 /* Mark the insn as having a hard dependence that prevents speculation. */
3320 sel_mark_hard_insn (rtx insn)
3324 /* Only work when we're in has_dependence_p mode.
3325 ??? This is a hack, this should actually be a hook. */
3326 if (!has_dependence_data.dc || !has_dependence_data.pro)
3329 gcc_assert (insn == VINSN_INSN_RTX (has_dependence_data.con));
3330 gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
3332 for (i = 0; i < DEPS_IN_NOWHERE; i++)
3333 has_dependence_data.has_dep_p[i] &= ~SPECULATIVE;
3336 /* This structure holds the hooks for the dependency analysis used when
3337 actually processing dependencies in the scheduler. */
3338 static struct sched_deps_info_def has_dependence_sched_deps_info;
3340 /* This initializes most of the fields of the above structure. */
3341 static const struct sched_deps_info_def const_has_dependence_sched_deps_info =
3345 has_dependence_start_insn,
3346 has_dependence_finish_insn,
3347 has_dependence_start_lhs,
3348 has_dependence_finish_lhs,
3349 has_dependence_start_rhs,
3350 has_dependence_finish_rhs,
3351 has_dependence_note_reg_set,
3352 has_dependence_note_reg_clobber,
3353 has_dependence_note_reg_use,
3354 has_dependence_note_mem_dep,
3355 has_dependence_note_dep,
3358 0, /* use_deps_list */
3359 0 /* generate_spec_deps */
3362 /* Initialize has_dependence_sched_deps_info with extra spec field. */
3364 setup_has_dependence_sched_deps_info (void)
3366 memcpy (&has_dependence_sched_deps_info,
3367 &const_has_dependence_sched_deps_info,
3368 sizeof (has_dependence_sched_deps_info));
3370 if (spec_info != NULL)
3371 has_dependence_sched_deps_info.generate_spec_deps = 1;
3373 sched_deps_info = &has_dependence_sched_deps_info;
3376 /* Remove all dependences found and recorded in has_dependence_data array. */
3378 sel_clear_has_dependence (void)
3382 for (i = 0; i < DEPS_IN_NOWHERE; i++)
3383 has_dependence_data.has_dep_p[i] = 0;
3386 /* Return nonzero if EXPR has is dependent upon PRED. Return the pointer
3387 to the dependence information array in HAS_DEP_PP. */
3389 has_dependence_p (expr_t expr, insn_t pred, ds_t **has_dep_pp)
3393 class deps_desc *dc;
3395 if (INSN_SIMPLEJUMP_P (pred))
3396 /* Unconditional jump is just a transfer of control flow.
3400 dc = &INSN_DEPS_CONTEXT (pred);
3402 /* We init this field lazily. */
3403 if (dc->reg_last == NULL)
3404 init_deps_reg_last (dc);
3408 has_dependence_data.pro = NULL;
3409 /* Initialize empty dep context with information about PRED. */
3410 advance_deps_context (dc, pred);
3414 has_dependence_data.where = DEPS_IN_NOWHERE;
3415 has_dependence_data.pro = pred;
3416 has_dependence_data.con = EXPR_VINSN (expr);
3417 has_dependence_data.dc = dc;
3419 sel_clear_has_dependence ();
3421 /* Now catch all dependencies that would be generated between PRED and
3423 setup_has_dependence_sched_deps_info ();
3424 deps_analyze_insn (dc, EXPR_INSN_RTX (expr));
3425 has_dependence_data.dc = NULL;
3427 /* When a barrier was found, set DEPS_IN_INSN bits. */
3428 if (dc->last_reg_pending_barrier == TRUE_BARRIER)
3429 has_dependence_data.has_dep_p[DEPS_IN_INSN] = DEP_TRUE;
3430 else if (dc->last_reg_pending_barrier == MOVE_BARRIER)
3431 has_dependence_data.has_dep_p[DEPS_IN_INSN] = DEP_ANTI;
3433 /* Do not allow stores to memory to move through checks. Currently
3434 we don't move this to sched-deps.c as the check doesn't have
3435 obvious places to which this dependence can be attached.
3436 FIMXE: this should go to a hook. */
3438 && MEM_P (EXPR_LHS (expr))
3439 && sel_insn_is_speculation_check (pred))
3440 has_dependence_data.has_dep_p[DEPS_IN_INSN] = DEP_ANTI;
3442 *has_dep_pp = has_dependence_data.has_dep_p;
3444 for (i = 0; i < DEPS_IN_NOWHERE; i++)
3445 ds = ds_full_merge (ds, has_dependence_data.has_dep_p[i],
3446 NULL_RTX, NULL_RTX);
3452 /* Dependence hooks implementation that checks dependence latency constraints
3453 on the insns being scheduled. The entry point for these routines is
3454 tick_check_p predicate. */
3458 /* An expr we are currently checking. */
3461 /* A minimal cycle for its scheduling. */
3464 /* Whether we have seen a true dependence while checking. */
3465 bool seen_true_dep_p;
3468 /* Update minimal scheduling cycle for tick_check_insn given that it depends
3469 on PRO with status DS and weight DW. */
3471 tick_check_dep_with_dw (insn_t pro_insn, ds_t ds, dw_t dw)
3473 expr_t con_expr = tick_check_data.expr;
3474 insn_t con_insn = EXPR_INSN_RTX (con_expr);
3476 if (con_insn != pro_insn)
3481 if (/* PROducer was removed from above due to pipelining. */
3482 !INSN_IN_STREAM_P (pro_insn)
3483 /* Or PROducer was originally on the next iteration regarding the
3485 || (INSN_SCHED_TIMES (pro_insn)
3486 - EXPR_SCHED_TIMES (con_expr)) > 1)
3487 /* Don't count this dependence. */
3491 if (dt == REG_DEP_TRUE)
3492 tick_check_data.seen_true_dep_p = true;
3494 gcc_assert (INSN_SCHED_CYCLE (pro_insn) > 0);
3497 dep_def _dep, *dep = &_dep;
3499 init_dep (dep, pro_insn, con_insn, dt);
3501 tick = INSN_SCHED_CYCLE (pro_insn) + dep_cost_1 (dep, dw);
3504 /* When there are several kinds of dependencies between pro and con,
3505 only REG_DEP_TRUE should be taken into account. */
3506 if (tick > tick_check_data.cycle
3507 && (dt == REG_DEP_TRUE || !tick_check_data.seen_true_dep_p))
3508 tick_check_data.cycle = tick;
3512 /* An implementation of note_dep hook. */
3514 tick_check_note_dep (insn_t pro, ds_t ds)
3516 tick_check_dep_with_dw (pro, ds, 0);
3519 /* An implementation of note_mem_dep hook. */
3521 tick_check_note_mem_dep (rtx mem1, rtx mem2, insn_t pro, ds_t ds)
3525 dw = (ds_to_dt (ds) == REG_DEP_TRUE
3526 ? estimate_dep_weak (mem1, mem2)
3529 tick_check_dep_with_dw (pro, ds, dw);
3532 /* This structure contains hooks for dependence analysis used when determining
3533 whether an insn is ready for scheduling. */
3534 static struct sched_deps_info_def tick_check_sched_deps_info =
3545 haifa_note_reg_clobber,
3547 tick_check_note_mem_dep,
3548 tick_check_note_dep,
3553 /* Estimate number of cycles from the current cycle of FENCE until EXPR can be
3554 scheduled. Return 0 if all data from producers in DC is ready. */
3556 tick_check_p (expr_t expr, deps_t dc, fence_t fence)
3559 /* Initialize variables. */
3560 tick_check_data.expr = expr;
3561 tick_check_data.cycle = 0;
3562 tick_check_data.seen_true_dep_p = false;
3563 sched_deps_info = &tick_check_sched_deps_info;
3565 gcc_assert (!dc->readonly);
3567 deps_analyze_insn (dc, EXPR_INSN_RTX (expr));
3570 cycles_left = tick_check_data.cycle - FENCE_CYCLE (fence);
3572 return cycles_left >= 0 ? cycles_left : 0;
3576 /* Functions to work with insns. */
3578 /* Returns true if LHS of INSN is the same as DEST of an insn
3581 lhs_of_insn_equals_to_dest_p (insn_t insn, rtx dest)
3583 rtx lhs = INSN_LHS (insn);
3585 if (lhs == NULL || dest == NULL)
3588 return rtx_equal_p (lhs, dest);
3591 /* Return s_i_d entry of INSN. Callable from debugger. */
3593 insn_sid (insn_t insn)
3598 /* True when INSN is a speculative check. We can tell this by looking
3599 at the data structures of the selective scheduler, not by examining
3602 sel_insn_is_speculation_check (rtx insn)
3604 return s_i_d.exists () && !! INSN_SPEC_CHECKED_DS (insn);
3607 /* Extracts machine mode MODE and destination location DST_LOC
3610 get_dest_and_mode (rtx insn, rtx *dst_loc, machine_mode *mode)
3612 rtx pat = PATTERN (insn);
3614 gcc_assert (dst_loc);
3615 gcc_assert (GET_CODE (pat) == SET);
3617 *dst_loc = SET_DEST (pat);
3619 gcc_assert (*dst_loc);
3620 gcc_assert (MEM_P (*dst_loc) || REG_P (*dst_loc));
3623 *mode = GET_MODE (*dst_loc);
3626 /* Returns true when moving through JUMP will result in bookkeeping
3629 bookkeeping_can_be_created_if_moved_through_p (insn_t jump)
3634 FOR_EACH_SUCC (succ, si, jump)
3635 if (sel_num_cfg_preds_gt_1 (succ))
3641 /* Return 'true' if INSN is the only one in its basic block. */
3643 insn_is_the_only_one_in_bb_p (insn_t insn)
3645 return sel_bb_head_p (insn) && sel_bb_end_p (insn);
3648 /* Check that the region we're scheduling still has at most one
3651 verify_backedges (void)
3659 for (i = 0; i < current_nr_blocks; i++)
3660 FOR_EACH_EDGE (e, ei, BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (i))->succs)
3661 if (in_current_region_p (e->dest)
3662 && BLOCK_TO_BB (e->dest->index) < i)
3665 gcc_assert (n <= 1);
3670 /* Functions to work with control flow. */
3672 /* Recompute BLOCK_TO_BB and BB_FOR_BLOCK for current region so that blocks
3673 are sorted in topological order (it might have been invalidated by
3674 redirecting an edge). */
3676 sel_recompute_toporder (void)
3679 int *postorder, n_blocks;
3681 postorder = XALLOCAVEC (int, n_basic_blocks_for_fn (cfun));
3682 n_blocks = post_order_compute (postorder, false, false);
3684 rgn = CONTAINING_RGN (BB_TO_BLOCK (0));
3685 for (n = 0, i = n_blocks - 1; i >= 0; i--)
3686 if (CONTAINING_RGN (postorder[i]) == rgn)
3688 BLOCK_TO_BB (postorder[i]) = n;
3689 BB_TO_BLOCK (n) = postorder[i];
3693 /* Assert that we updated info for all blocks. We may miss some blocks if
3694 this function is called when redirecting an edge made a block
3695 unreachable, but that block is not deleted yet. */
3696 gcc_assert (n == RGN_NR_BLOCKS (rgn));
3699 /* Tidy the possibly empty block BB. */
3701 maybe_tidy_empty_bb (basic_block bb)
3703 basic_block succ_bb, pred_bb, note_bb;
3704 vec<basic_block> dom_bbs;
3709 /* Keep empty bb only if this block immediately precedes EXIT and
3710 has incoming non-fallthrough edge, or it has no predecessors or
3711 successors. Otherwise remove it. */
3712 if (!sel_bb_empty_p (bb)
3713 || (single_succ_p (bb)
3714 && single_succ (bb) == EXIT_BLOCK_PTR_FOR_FN (cfun)
3715 && (!single_pred_p (bb)
3716 || !(single_pred_edge (bb)->flags & EDGE_FALLTHRU)))
3717 || EDGE_COUNT (bb->preds) == 0
3718 || EDGE_COUNT (bb->succs) == 0)
3721 /* Do not attempt to redirect complex edges. */
3722 FOR_EACH_EDGE (e, ei, bb->preds)
3723 if (e->flags & EDGE_COMPLEX)
3725 else if (e->flags & EDGE_FALLTHRU)
3728 /* If prev bb ends with asm goto, see if any of the
3729 ASM_OPERANDS_LABELs don't point to the fallthru
3730 label. Do not attempt to redirect it in that case. */
3731 if (JUMP_P (BB_END (e->src))
3732 && (note = extract_asm_operands (PATTERN (BB_END (e->src)))))
3734 int i, n = ASM_OPERANDS_LABEL_LENGTH (note);
3736 for (i = 0; i < n; ++i)
3737 if (XEXP (ASM_OPERANDS_LABEL (note, i), 0) == BB_HEAD (bb))
3742 free_data_sets (bb);
3744 /* Do not delete BB if it has more than one successor.
3745 That can occur when we moving a jump. */
3746 if (!single_succ_p (bb))
3748 gcc_assert (can_merge_blocks_p (bb->prev_bb, bb));
3749 sel_merge_blocks (bb->prev_bb, bb);
3753 succ_bb = single_succ (bb);
3758 /* Save a pred/succ from the current region to attach the notes to. */
3760 FOR_EACH_EDGE (e, ei, bb->preds)
3761 if (in_current_region_p (e->src))
3766 if (note_bb == NULL)
3769 /* Redirect all non-fallthru edges to the next bb. */
3774 FOR_EACH_EDGE (e, ei, bb->preds)
3778 if (!(e->flags & EDGE_FALLTHRU))
3780 /* We cannot invalidate computed topological order by moving
3781 the edge destination block (E->SUCC) along a fallthru edge.
3783 We will update dominators here only when we'll get
3784 an unreachable block when redirecting, otherwise
3785 sel_redirect_edge_and_branch will take care of it. */
3787 && single_pred_p (e->dest))
3788 dom_bbs.safe_push (e->dest);
3789 sel_redirect_edge_and_branch (e, succ_bb);
3793 /* If the edge is fallthru, but PRED_BB ends in a conditional jump
3794 to BB (so there is no non-fallthru edge from PRED_BB to BB), we
3795 still have to adjust it. */
3796 else if (single_succ_p (pred_bb) && any_condjump_p (BB_END (pred_bb)))
3798 /* If possible, try to remove the unneeded conditional jump. */
3799 if (INSN_SCHED_TIMES (BB_END (pred_bb)) == 0
3800 && !IN_CURRENT_FENCE_P (BB_END (pred_bb)))
3802 if (!sel_remove_insn (BB_END (pred_bb), false, false))
3803 tidy_fallthru_edge (e);
3806 sel_redirect_edge_and_branch (e, succ_bb);
3813 if (can_merge_blocks_p (bb->prev_bb, bb))
3814 sel_merge_blocks (bb->prev_bb, bb);
3817 /* This is a block without fallthru predecessor. Just delete it. */
3818 gcc_assert (note_bb);
3819 move_bb_info (note_bb, bb);
3820 remove_empty_bb (bb, true);
3823 if (!dom_bbs.is_empty ())
3825 dom_bbs.safe_push (succ_bb);
3826 iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, false);
3833 /* Tidy the control flow after we have removed original insn from
3834 XBB. Return true if we have removed some blocks. When FULL_TIDYING
3835 is true, also try to optimize control flow on non-empty blocks. */
3837 tidy_control_flow (basic_block xbb, bool full_tidying)
3839 bool changed = true;
3842 /* First check whether XBB is empty. */
3843 changed = maybe_tidy_empty_bb (xbb);
3844 if (changed || !full_tidying)
3847 /* Check if there is a unnecessary jump after insn left. */
3848 if (bb_has_removable_jump_to_p (xbb, xbb->next_bb)
3849 && INSN_SCHED_TIMES (BB_END (xbb)) == 0
3850 && !IN_CURRENT_FENCE_P (BB_END (xbb)))
3852 /* We used to call sel_remove_insn here that can trigger tidy_control_flow
3853 before we fix up the fallthru edge. Correct that ordering by
3854 explicitly doing the latter before the former. */
3855 clear_expr (INSN_EXPR (BB_END (xbb)));
3856 tidy_fallthru_edge (EDGE_SUCC (xbb, 0));
3857 if (tidy_control_flow (xbb, false))
3861 first = sel_bb_head (xbb);
3862 last = sel_bb_end (xbb);
3863 if (MAY_HAVE_DEBUG_INSNS)
3865 if (first != last && DEBUG_INSN_P (first))
3867 first = NEXT_INSN (first);
3868 while (first != last && (DEBUG_INSN_P (first) || NOTE_P (first)));
3870 if (first != last && DEBUG_INSN_P (last))
3872 last = PREV_INSN (last);
3873 while (first != last && (DEBUG_INSN_P (last) || NOTE_P (last)));
3875 /* Check if there is an unnecessary jump in previous basic block leading
3876 to next basic block left after removing INSN from stream.
3877 If it is so, remove that jump and redirect edge to current
3878 basic block (where there was INSN before deletion). This way
3879 when NOP will be deleted several instructions later with its
3880 basic block we will not get a jump to next instruction, which
3883 && !sel_bb_empty_p (xbb)
3884 && INSN_NOP_P (last)
3885 /* Flow goes fallthru from current block to the next. */
3886 && EDGE_COUNT (xbb->succs) == 1
3887 && (EDGE_SUCC (xbb, 0)->flags & EDGE_FALLTHRU)
3888 /* When successor is an EXIT block, it may not be the next block. */
3889 && single_succ (xbb) != EXIT_BLOCK_PTR_FOR_FN (cfun)
3890 /* And unconditional jump in previous basic block leads to
3891 next basic block of XBB and this jump can be safely removed. */
3892 && in_current_region_p (xbb->prev_bb)
3893 && bb_has_removable_jump_to_p (xbb->prev_bb, xbb->next_bb)
3894 && INSN_SCHED_TIMES (BB_END (xbb->prev_bb)) == 0
3895 /* Also this jump is not at the scheduling boundary. */
3896 && !IN_CURRENT_FENCE_P (BB_END (xbb->prev_bb)))
3898 bool recompute_toporder_p;
3899 /* Clear data structures of jump - jump itself will be removed
3900 by sel_redirect_edge_and_branch. */
3901 clear_expr (INSN_EXPR (BB_END (xbb->prev_bb)));
3902 recompute_toporder_p
3903 = sel_redirect_edge_and_branch (EDGE_SUCC (xbb->prev_bb, 0), xbb);
3905 gcc_assert (EDGE_SUCC (xbb->prev_bb, 0)->flags & EDGE_FALLTHRU);
3907 /* We could have skipped some debug insns which did not get removed with the block,
3908 and the seqnos could become incorrect. Fix them up here. */
3909 if (MAY_HAVE_DEBUG_INSNS && (sel_bb_head (xbb) != first || sel_bb_end (xbb) != last))
3911 if (!sel_bb_empty_p (xbb->prev_bb))
3913 int prev_seqno = INSN_SEQNO (sel_bb_end (xbb->prev_bb));
3914 if (prev_seqno > INSN_SEQNO (sel_bb_head (xbb)))
3915 for (insn_t insn = sel_bb_head (xbb); insn != first; insn = NEXT_INSN (insn))
3916 INSN_SEQNO (insn) = prev_seqno + 1;
3920 /* It can turn out that after removing unused jump, basic block
3921 that contained that jump, becomes empty too. In such case
3923 if (sel_bb_empty_p (xbb->prev_bb))
3924 changed = maybe_tidy_empty_bb (xbb->prev_bb);
3925 if (recompute_toporder_p)
3926 sel_recompute_toporder ();
3929 /* TODO: use separate flag for CFG checking. */
3932 verify_backedges ();
3933 verify_dominators (CDI_DOMINATORS);
3939 /* Purge meaningless empty blocks in the middle of a region. */
3941 purge_empty_blocks (void)
3945 /* Do not attempt to delete the first basic block in the region. */
3946 for (i = 1; i < current_nr_blocks; )
3948 basic_block b = BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (i));
3950 if (maybe_tidy_empty_bb (b))
3957 /* Rip-off INSN from the insn stream. When ONLY_DISCONNECT is true,
3958 do not delete insn's data, because it will be later re-emitted.
3959 Return true if we have removed some blocks afterwards. */
3961 sel_remove_insn (insn_t insn, bool only_disconnect, bool full_tidying)
3963 basic_block bb = BLOCK_FOR_INSN (insn);
3965 gcc_assert (INSN_IN_STREAM_P (insn));
3967 if (DEBUG_INSN_P (insn) && BB_AV_SET_VALID_P (bb))
3972 /* When we remove a debug insn that is head of a BB, it remains
3973 in the AV_SET of the block, but it shouldn't. */
3974 FOR_EACH_EXPR_1 (expr, i, &BB_AV_SET (bb))
3975 if (EXPR_INSN_RTX (expr) == insn)
3977 av_set_iter_remove (&i);
3982 if (only_disconnect)
3987 clear_expr (INSN_EXPR (insn));
3990 /* It is necessary to NULL these fields in case we are going to re-insert
3991 INSN into the insns stream, as will usually happen in the ONLY_DISCONNECT
3992 case, but also for NOPs that we will return to the nop pool. */
3993 SET_PREV_INSN (insn) = NULL_RTX;
3994 SET_NEXT_INSN (insn) = NULL_RTX;
3995 set_block_for_insn (insn, NULL);
3997 return tidy_control_flow (bb, full_tidying);
4000 /* Estimate number of the insns in BB. */
4002 sel_estimate_number_of_insns (basic_block bb)
4005 insn_t insn = NEXT_INSN (BB_HEAD (bb)), next_tail = NEXT_INSN (BB_END (bb));
4007 for (; insn != next_tail; insn = NEXT_INSN (insn))
4008 if (NONDEBUG_INSN_P (insn))
4014 /* We don't need separate luids for notes or labels. */
4016 sel_luid_for_non_insn (rtx x)
4018 gcc_assert (NOTE_P (x) || LABEL_P (x));
4023 /* Find the proper seqno for inserting at INSN by successors.
4024 Return -1 if no successors with positive seqno exist. */
4026 get_seqno_by_succs (rtx_insn *insn)
4028 basic_block bb = BLOCK_FOR_INSN (insn);
4029 rtx_insn *tmp = insn, *end = BB_END (bb);
4036 tmp = NEXT_INSN (tmp);
4038 return INSN_SEQNO (tmp);
4043 FOR_EACH_SUCC_1 (succ, si, end, SUCCS_NORMAL)
4044 if (INSN_SEQNO (succ) > 0)
4045 seqno = MIN (seqno, INSN_SEQNO (succ));
4047 if (seqno == INT_MAX)
4053 /* Compute seqno for INSN by its preds or succs. Use OLD_SEQNO to compute
4054 seqno in corner cases. */
4056 get_seqno_for_a_jump (insn_t insn, int old_seqno)
4060 gcc_assert (INSN_SIMPLEJUMP_P (insn));
4062 if (!sel_bb_head_p (insn))
4063 seqno = INSN_SEQNO (PREV_INSN (insn));
4066 basic_block bb = BLOCK_FOR_INSN (insn);
4068 if (single_pred_p (bb)
4069 && !in_current_region_p (single_pred (bb)))
4071 /* We can have preds outside a region when splitting edges
4072 for pipelining of an outer loop. Use succ instead.
4073 There should be only one of them. */
4078 gcc_assert (flag_sel_sched_pipelining_outer_loops
4079 && current_loop_nest);
4080 FOR_EACH_SUCC_1 (succ, si, insn,
4081 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
4087 gcc_assert (succ != NULL);
4088 seqno = INSN_SEQNO (succ);
4095 cfg_preds (BLOCK_FOR_INSN (insn), &preds, &n);
4098 /* For one predecessor, use simple method. */
4100 seqno = INSN_SEQNO (preds[0]);
4102 seqno = get_seqno_by_preds (insn);
4108 /* We were unable to find a good seqno among preds. */
4110 seqno = get_seqno_by_succs (insn);
4114 /* The only case where this could be here legally is that the only
4115 unscheduled insn was a conditional jump that got removed and turned
4116 into this unconditional one. Initialize from the old seqno
4117 of that jump passed down to here. */
4121 gcc_assert (seqno >= 0);
4125 /* Find the proper seqno for inserting at INSN. Returns -1 if no predecessors
4126 with positive seqno exist. */
4128 get_seqno_by_preds (rtx_insn *insn)
4130 basic_block bb = BLOCK_FOR_INSN (insn);
4131 rtx_insn *tmp = insn, *head = BB_HEAD (bb);
4135 /* Loop backwards from INSN to HEAD including both. */
4139 return INSN_SEQNO (tmp);
4142 tmp = PREV_INSN (tmp);
4145 cfg_preds (bb, &preds, &n);
4146 for (i = 0, seqno = -1; i < n; i++)
4147 seqno = MAX (seqno, INSN_SEQNO (preds[i]));
4154 /* Extend pass-scope data structures for basic blocks. */
4156 sel_extend_global_bb_info (void)
4158 sel_global_bb_info.safe_grow_cleared (last_basic_block_for_fn (cfun));
4161 /* Extend region-scope data structures for basic blocks. */
4163 extend_region_bb_info (void)
4165 sel_region_bb_info.safe_grow_cleared (last_basic_block_for_fn (cfun));
4168 /* Extend all data structures to fit for all basic blocks. */
4170 extend_bb_info (void)
4172 sel_extend_global_bb_info ();
4173 extend_region_bb_info ();
4176 /* Finalize pass-scope data structures for basic blocks. */
4178 sel_finish_global_bb_info (void)
4180 sel_global_bb_info.release ();
4183 /* Finalize region-scope data structures for basic blocks. */
4185 finish_region_bb_info (void)
4187 sel_region_bb_info.release ();
4191 /* Data for each insn in current region. */
4192 vec<sel_insn_data_def> s_i_d;
4194 /* Extend data structures for insns from current region. */
4196 extend_insn_data (void)
4200 sched_extend_target ();
4201 sched_deps_init (false);
4203 /* Extend data structures for insns from current region. */
4204 reserve = (sched_max_luid + 1 - s_i_d.length ());
4205 if (reserve > 0 && ! s_i_d.space (reserve))
4209 if (sched_max_luid / 2 > 1024)
4210 size = sched_max_luid + 1024;
4212 size = 3 * sched_max_luid / 2;
4215 s_i_d.safe_grow_cleared (size);
4219 /* Finalize data structures for insns from current region. */
4225 /* Clear here all dependence contexts that may have left from insns that were
4226 removed during the scheduling. */
4227 for (i = 0; i < s_i_d.length (); i++)
4229 sel_insn_data_def *sid_entry = &s_i_d[i];
4231 if (sid_entry->live)
4232 return_regset_to_pool (sid_entry->live);
4233 if (sid_entry->analyzed_deps)
4235 BITMAP_FREE (sid_entry->analyzed_deps);
4236 BITMAP_FREE (sid_entry->found_deps);
4237 htab_delete (sid_entry->transformed_insns);
4238 free_deps (&sid_entry->deps_context);
4240 if (EXPR_VINSN (&sid_entry->expr))
4242 clear_expr (&sid_entry->expr);
4244 /* Also, clear CANT_MOVE bit here, because we really don't want it
4245 to be passed to the next region. */
4246 CANT_MOVE_BY_LUID (i) = 0;
4253 /* A proxy to pass initialization data to init_insn (). */
4254 static sel_insn_data_def _insn_init_ssid;
4255 static sel_insn_data_t insn_init_ssid = &_insn_init_ssid;
4257 /* If true create a new vinsn. Otherwise use the one from EXPR. */
4258 static bool insn_init_create_new_vinsn_p;
4260 /* Set all necessary data for initialization of the new insn[s]. */
4262 set_insn_init (expr_t expr, vinsn_t vi, int seqno)
4264 expr_t x = &insn_init_ssid->expr;
4266 copy_expr_onside (x, expr);
4269 insn_init_create_new_vinsn_p = false;
4270 change_vinsn_in_expr (x, vi);
4273 insn_init_create_new_vinsn_p = true;
4275 insn_init_ssid->seqno = seqno;
4279 /* Init data for INSN. */
4281 init_insn_data (insn_t insn)
4284 sel_insn_data_t ssid = insn_init_ssid;
4286 /* The fields mentioned below are special and hence are not being
4287 propagated to the new insns. */
4288 gcc_assert (!ssid->asm_p && ssid->sched_next == NULL
4289 && !ssid->after_stall_p && ssid->sched_cycle == 0);
4290 gcc_assert (INSN_P (insn) && INSN_LUID (insn) > 0);
4292 expr = INSN_EXPR (insn);
4293 copy_expr (expr, &ssid->expr);
4294 prepare_insn_expr (insn, ssid->seqno);
4296 if (insn_init_create_new_vinsn_p)
4297 change_vinsn_in_expr (expr, vinsn_create (insn, init_insn_force_unique_p));
4299 if (first_time_insn_init (insn))
4300 init_first_time_insn_data (insn);
4303 /* This is used to initialize spurious jumps generated by
4304 sel_redirect_edge (). OLD_SEQNO is used for initializing seqnos
4305 in corner cases within get_seqno_for_a_jump. */
4307 init_simplejump_data (insn_t insn, int old_seqno)
4309 init_expr (INSN_EXPR (insn), vinsn_create (insn, false), 0,
4310 REG_BR_PROB_BASE, 0, 0, 0, 0, 0, 0,
4311 vNULL, true, false, false,
4313 INSN_SEQNO (insn) = get_seqno_for_a_jump (insn, old_seqno);
4314 init_first_time_insn_data (insn);
4317 /* Perform deferred initialization of insns. This is used to process
4318 a new jump that may be created by redirect_edge. OLD_SEQNO is used
4319 for initializing simplejumps in init_simplejump_data. */
4321 sel_init_new_insn (insn_t insn, int flags, int old_seqno)
4323 /* We create data structures for bb when the first insn is emitted in it. */
4325 && INSN_IN_STREAM_P (insn)
4326 && insn_is_the_only_one_in_bb_p (insn))
4329 create_initial_data_sets (BLOCK_FOR_INSN (insn));
4332 if (flags & INSN_INIT_TODO_LUID)
4334 sched_extend_luids ();
4335 sched_init_insn_luid (insn);
4338 if (flags & INSN_INIT_TODO_SSID)
4340 extend_insn_data ();
4341 init_insn_data (insn);
4342 clear_expr (&insn_init_ssid->expr);
4345 if (flags & INSN_INIT_TODO_SIMPLEJUMP)
4347 extend_insn_data ();
4348 init_simplejump_data (insn, old_seqno);
4351 gcc_assert (CONTAINING_RGN (BLOCK_NUM (insn))
4352 == CONTAINING_RGN (BB_TO_BLOCK (0)));
4356 /* Functions to init/finish work with lv sets. */
4358 /* Init BB_LV_SET of BB from DF_LR_IN set of BB. */
4360 init_lv_set (basic_block bb)
4362 gcc_assert (!BB_LV_SET_VALID_P (bb));
4364 BB_LV_SET (bb) = get_regset_from_pool ();
4365 COPY_REG_SET (BB_LV_SET (bb), DF_LR_IN (bb));
4366 BB_LV_SET_VALID_P (bb) = true;
4369 /* Copy liveness information to BB from FROM_BB. */
4371 copy_lv_set_from (basic_block bb, basic_block from_bb)
4373 gcc_assert (!BB_LV_SET_VALID_P (bb));
4375 COPY_REG_SET (BB_LV_SET (bb), BB_LV_SET (from_bb));
4376 BB_LV_SET_VALID_P (bb) = true;
4379 /* Initialize lv set of all bb headers. */
4385 /* Initialize of LV sets. */
4386 FOR_EACH_BB_FN (bb, cfun)
4389 /* Don't forget EXIT_BLOCK. */
4390 init_lv_set (EXIT_BLOCK_PTR_FOR_FN (cfun));
4393 /* Release lv set of HEAD. */
4395 free_lv_set (basic_block bb)
4397 gcc_assert (BB_LV_SET (bb) != NULL);
4399 return_regset_to_pool (BB_LV_SET (bb));
4400 BB_LV_SET (bb) = NULL;
4401 BB_LV_SET_VALID_P (bb) = false;
4404 /* Finalize lv sets of all bb headers. */
4410 /* Don't forget EXIT_BLOCK. */
4411 free_lv_set (EXIT_BLOCK_PTR_FOR_FN (cfun));
4414 FOR_EACH_BB_FN (bb, cfun)
4419 /* Mark AV_SET for BB as invalid, so this set will be updated the next time
4420 compute_av() processes BB. This function is called when creating new basic
4421 blocks, as well as for blocks (either new or existing) where new jumps are
4422 created when the control flow is being updated. */
4424 invalidate_av_set (basic_block bb)
4426 BB_AV_LEVEL (bb) = -1;
4429 /* Create initial data sets for BB (they will be invalid). */
4431 create_initial_data_sets (basic_block bb)
4434 BB_LV_SET_VALID_P (bb) = false;
4436 BB_LV_SET (bb) = get_regset_from_pool ();
4437 invalidate_av_set (bb);
4440 /* Free av set of BB. */
4442 free_av_set (basic_block bb)
4444 av_set_clear (&BB_AV_SET (bb));
4445 BB_AV_LEVEL (bb) = 0;
4448 /* Free data sets of BB. */
4450 free_data_sets (basic_block bb)
4456 /* Exchange data sets of TO and FROM. */
4458 exchange_data_sets (basic_block to, basic_block from)
4460 /* Exchange lv sets of TO and FROM. */
4461 std::swap (BB_LV_SET (from), BB_LV_SET (to));
4462 std::swap (BB_LV_SET_VALID_P (from), BB_LV_SET_VALID_P (to));
4464 /* Exchange av sets of TO and FROM. */
4465 std::swap (BB_AV_SET (from), BB_AV_SET (to));
4466 std::swap (BB_AV_LEVEL (from), BB_AV_LEVEL (to));
4469 /* Copy data sets of FROM to TO. */
4471 copy_data_sets (basic_block to, basic_block from)
4473 gcc_assert (!BB_LV_SET_VALID_P (to) && !BB_AV_SET_VALID_P (to));
4474 gcc_assert (BB_AV_SET (to) == NULL);
4476 BB_AV_LEVEL (to) = BB_AV_LEVEL (from);
4477 BB_LV_SET_VALID_P (to) = BB_LV_SET_VALID_P (from);
4479 if (BB_AV_SET_VALID_P (from))
4481 BB_AV_SET (to) = av_set_copy (BB_AV_SET (from));
4483 if (BB_LV_SET_VALID_P (from))
4485 gcc_assert (BB_LV_SET (to) != NULL);
4486 COPY_REG_SET (BB_LV_SET (to), BB_LV_SET (from));
4490 /* Return an av set for INSN, if any. */
4492 get_av_set (insn_t insn)
4496 gcc_assert (AV_SET_VALID_P (insn));
4498 if (sel_bb_head_p (insn))
4499 av_set = BB_AV_SET (BLOCK_FOR_INSN (insn));
4506 /* Implementation of AV_LEVEL () macro. Return AV_LEVEL () of INSN. */
4508 get_av_level (insn_t insn)
4512 gcc_assert (INSN_P (insn));
4514 if (sel_bb_head_p (insn))
4515 av_level = BB_AV_LEVEL (BLOCK_FOR_INSN (insn));
4517 av_level = INSN_WS_LEVEL (insn);
4524 /* Variables to work with control-flow graph. */
4526 /* The basic block that already has been processed by the sched_data_update (),
4527 but hasn't been in sel_add_bb () yet. */
4528 static vec<basic_block> last_added_blocks;
4530 /* A pool for allocating successor infos. */
4533 /* A stack for saving succs_info structures. */
4534 struct succs_info *stack;
4539 /* Top of the stack. */
4542 /* Maximal value of the top. */
4546 /* Functions to work with control-flow graph. */
4548 /* Return basic block note of BB. */
4550 sel_bb_head (basic_block bb)
4554 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
4556 gcc_assert (exit_insn != NULL_RTX);
4561 rtx_note *note = bb_note (bb);
4562 head = next_nonnote_insn (note);
4564 if (head && (BARRIER_P (head) || BLOCK_FOR_INSN (head) != bb))
4571 /* Return true if INSN is a basic block header. */
4573 sel_bb_head_p (insn_t insn)
4575 return sel_bb_head (BLOCK_FOR_INSN (insn)) == insn;
4578 /* Return last insn of BB. */
4580 sel_bb_end (basic_block bb)
4582 if (sel_bb_empty_p (bb))
4585 gcc_assert (bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
4590 /* Return true if INSN is the last insn in its basic block. */
4592 sel_bb_end_p (insn_t insn)
4594 return insn == sel_bb_end (BLOCK_FOR_INSN (insn));
4597 /* Return true if BB consist of single NOTE_INSN_BASIC_BLOCK. */
4599 sel_bb_empty_p (basic_block bb)
4601 return sel_bb_head (bb) == NULL;
4604 /* True when BB belongs to the current scheduling region. */
4606 in_current_region_p (basic_block bb)
4608 if (bb->index < NUM_FIXED_BLOCKS)
4611 return CONTAINING_RGN (bb->index) == CONTAINING_RGN (BB_TO_BLOCK (0));
4614 /* Return the block which is a fallthru bb of a conditional jump JUMP. */
4616 fallthru_bb_of_jump (const rtx_insn *jump)
4621 if (!any_condjump_p (jump))
4624 /* A basic block that ends with a conditional jump may still have one successor
4625 (and be followed by a barrier), we are not interested. */
4626 if (single_succ_p (BLOCK_FOR_INSN (jump)))
4629 return FALLTHRU_EDGE (BLOCK_FOR_INSN (jump))->dest;
4632 /* Remove all notes from BB. */
4634 init_bb (basic_block bb)
4636 remove_notes (bb_note (bb), BB_END (bb));
4637 BB_NOTE_LIST (bb) = note_list;
4641 sel_init_bbs (bb_vec_t bbs)
4643 const struct sched_scan_info_def ssi =
4645 extend_bb_info, /* extend_bb */
4646 init_bb, /* init_bb */
4647 NULL, /* extend_insn */
4648 NULL /* init_insn */
4651 sched_scan (&ssi, bbs);
4654 /* Restore notes for the whole region. */
4656 sel_restore_notes (void)
4661 for (bb = 0; bb < current_nr_blocks; bb++)
4663 basic_block first, last;
4665 first = EBB_FIRST_BB (bb);
4666 last = EBB_LAST_BB (bb)->next_bb;
4670 note_list = BB_NOTE_LIST (first);
4671 restore_other_notes (NULL, first);
4672 BB_NOTE_LIST (first) = NULL;
4674 FOR_BB_INSNS (first, insn)
4675 if (NONDEBUG_INSN_P (insn))
4676 reemit_notes (insn);
4678 first = first->next_bb;
4680 while (first != last);
4684 /* Free per-bb data structures. */
4686 sel_finish_bbs (void)
4688 sel_restore_notes ();
4690 /* Remove current loop preheader from this loop. */
4691 if (current_loop_nest)
4692 sel_remove_loop_preheader ();
4694 finish_region_bb_info ();
4697 /* Return true if INSN has a single successor of type FLAGS. */
4699 sel_insn_has_single_succ_p (insn_t insn, int flags)
4703 bool first_p = true;
4705 FOR_EACH_SUCC_1 (succ, si, insn, flags)
4716 /* Allocate successor's info. */
4717 static struct succs_info *
4718 alloc_succs_info (void)
4720 if (succs_info_pool.top == succs_info_pool.max_top)
4724 if (++succs_info_pool.max_top >= succs_info_pool.size)
4727 i = ++succs_info_pool.top;
4728 succs_info_pool.stack[i].succs_ok.create (10);
4729 succs_info_pool.stack[i].succs_other.create (10);
4730 succs_info_pool.stack[i].probs_ok.create (10);
4733 succs_info_pool.top++;
4735 return &succs_info_pool.stack[succs_info_pool.top];
4738 /* Free successor's info. */
4740 free_succs_info (struct succs_info * sinfo)
4742 gcc_assert (succs_info_pool.top >= 0
4743 && &succs_info_pool.stack[succs_info_pool.top] == sinfo);
4744 succs_info_pool.top--;
4746 /* Clear stale info. */
4747 sinfo->succs_ok.block_remove (0, sinfo->succs_ok.length ());
4748 sinfo->succs_other.block_remove (0, sinfo->succs_other.length ());
4749 sinfo->probs_ok.block_remove (0, sinfo->probs_ok.length ());
4750 sinfo->all_prob = 0;
4751 sinfo->succs_ok_n = 0;
4752 sinfo->all_succs_n = 0;
4755 /* Compute successor info for INSN. FLAGS are the flags passed
4756 to the FOR_EACH_SUCC_1 iterator. */
4758 compute_succs_info (insn_t insn, short flags)
4762 struct succs_info *sinfo = alloc_succs_info ();
4764 /* Traverse *all* successors and decide what to do with each. */
4765 FOR_EACH_SUCC_1 (succ, si, insn, SUCCS_ALL)
4767 /* FIXME: this doesn't work for skipping to loop exits, as we don't
4768 perform code motion through inner loops. */
4769 short current_flags = si.current_flags & ~SUCCS_SKIP_TO_LOOP_EXITS;
4771 if (current_flags & flags)
4773 sinfo->succs_ok.safe_push (succ);
4774 sinfo->probs_ok.safe_push (
4775 /* FIXME: Improve calculation when skipping
4776 inner loop to exits. */
4778 ? (si.e1->probability.initialized_p ()
4779 ? si.e1->probability.to_reg_br_prob_base ()
4781 : REG_BR_PROB_BASE);
4782 sinfo->succs_ok_n++;
4785 sinfo->succs_other.safe_push (succ);
4787 /* Compute all_prob. */
4789 sinfo->all_prob = REG_BR_PROB_BASE;
4790 else if (si.e1->probability.initialized_p ())
4791 sinfo->all_prob += si.e1->probability.to_reg_br_prob_base ();
4793 sinfo->all_succs_n++;
4799 /* Return the predecessors of BB in PREDS and their number in N.
4800 Empty blocks are skipped. SIZE is used to allocate PREDS. */
4802 cfg_preds_1 (basic_block bb, insn_t **preds, int *n, int *size)
4807 gcc_assert (BLOCK_TO_BB (bb->index) != 0);
4809 FOR_EACH_EDGE (e, ei, bb->preds)
4811 basic_block pred_bb = e->src;
4812 insn_t bb_end = BB_END (pred_bb);
4814 if (!in_current_region_p (pred_bb))
4816 gcc_assert (flag_sel_sched_pipelining_outer_loops
4817 && current_loop_nest);
4821 if (sel_bb_empty_p (pred_bb))
4822 cfg_preds_1 (pred_bb, preds, n, size);
4826 *preds = XRESIZEVEC (insn_t, *preds,
4827 (*size = 2 * *size + 1));
4828 (*preds)[(*n)++] = bb_end;
4833 || (flag_sel_sched_pipelining_outer_loops
4834 && current_loop_nest));
4837 /* Find all predecessors of BB and record them in PREDS and their number
4838 in N. Empty blocks are skipped, and only normal (forward in-region)
4839 edges are processed. */
4841 cfg_preds (basic_block bb, insn_t **preds, int *n)
4847 cfg_preds_1 (bb, preds, n, &size);
4850 /* Returns true if we are moving INSN through join point. */
4852 sel_num_cfg_preds_gt_1 (insn_t insn)
4856 if (!sel_bb_head_p (insn) || INSN_BB (insn) == 0)
4859 bb = BLOCK_FOR_INSN (insn);
4863 if (EDGE_COUNT (bb->preds) > 1)
4866 gcc_assert (EDGE_PRED (bb, 0)->dest == bb);
4867 bb = EDGE_PRED (bb, 0)->src;
4869 if (!sel_bb_empty_p (bb))
4876 /* Returns true when BB should be the end of an ebb. Adapted from the
4877 code in sched-ebb.c. */
4879 bb_ends_ebb_p (basic_block bb)
4881 basic_block next_bb = bb_next_bb (bb);
4884 if (next_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
4885 || bitmap_bit_p (forced_ebb_heads, next_bb->index)
4886 || (LABEL_P (BB_HEAD (next_bb))
4887 /* NB: LABEL_NUSES () is not maintained outside of jump.c.
4888 Work around that. */
4889 && !single_pred_p (next_bb)))
4892 if (!in_current_region_p (next_bb))
4895 e = find_fallthru_edge (bb->succs);
4898 gcc_assert (e->dest == next_bb);
4906 /* Returns true when INSN and SUCC are in the same EBB, given that SUCC is a
4907 successor of INSN. */
4909 in_same_ebb_p (insn_t insn, insn_t succ)
4911 basic_block ptr = BLOCK_FOR_INSN (insn);
4915 if (ptr == BLOCK_FOR_INSN (succ))
4918 if (bb_ends_ebb_p (ptr))
4921 ptr = bb_next_bb (ptr);
4928 /* Recomputes the reverse topological order for the function and
4929 saves it in REV_TOP_ORDER_INDEX. REV_TOP_ORDER_INDEX_LEN is also
4930 modified appropriately. */
4932 recompute_rev_top_order (void)
4937 if (!rev_top_order_index
4938 || rev_top_order_index_len < last_basic_block_for_fn (cfun))
4940 rev_top_order_index_len = last_basic_block_for_fn (cfun);
4941 rev_top_order_index = XRESIZEVEC (int, rev_top_order_index,
4942 rev_top_order_index_len);
4945 postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
4947 n_blocks = post_order_compute (postorder, true, false);
4948 gcc_assert (n_basic_blocks_for_fn (cfun) == n_blocks);
4950 /* Build reverse function: for each basic block with BB->INDEX == K
4951 rev_top_order_index[K] is it's reverse topological sort number. */
4952 for (i = 0; i < n_blocks; i++)
4954 gcc_assert (postorder[i] < rev_top_order_index_len);
4955 rev_top_order_index[postorder[i]] = i;
4961 /* Clear all flags from insns in BB that could spoil its rescheduling. */
4963 clear_outdated_rtx_info (basic_block bb)
4967 FOR_BB_INSNS (bb, insn)
4970 SCHED_GROUP_P (insn) = 0;
4971 INSN_AFTER_STALL_P (insn) = 0;
4972 INSN_SCHED_TIMES (insn) = 0;
4973 EXPR_PRIORITY_ADJ (INSN_EXPR (insn)) = 0;
4975 /* We cannot use the changed caches, as previously we could ignore
4976 the LHS dependence due to enabled renaming and transform
4977 the expression, and currently we'll be unable to do this. */
4978 htab_empty (INSN_TRANSFORMED_INSNS (insn));
4982 /* Add BB_NOTE to the pool of available basic block notes. */
4984 return_bb_to_pool (basic_block bb)
4986 rtx_note *note = bb_note (bb);
4988 gcc_assert (NOTE_BASIC_BLOCK (note) == bb
4989 && bb->aux == NULL);
4991 /* It turns out that current cfg infrastructure does not support
4992 reuse of basic blocks. Don't bother for now. */
4993 /*bb_note_pool.safe_push (note);*/
4996 /* Get a bb_note from pool or return NULL_RTX if pool is empty. */
4998 get_bb_note_from_pool (void)
5000 if (bb_note_pool.is_empty ())
5004 rtx_note *note = bb_note_pool.pop ();
5006 SET_PREV_INSN (note) = NULL_RTX;
5007 SET_NEXT_INSN (note) = NULL_RTX;
5013 /* Free bb_note_pool. */
5015 free_bb_note_pool (void)
5017 bb_note_pool.release ();
5020 /* Setup scheduler pool and successor structure. */
5022 alloc_sched_pools (void)
5026 succs_size = MAX_WS + 1;
5027 succs_info_pool.stack = XCNEWVEC (struct succs_info, succs_size);
5028 succs_info_pool.size = succs_size;
5029 succs_info_pool.top = -1;
5030 succs_info_pool.max_top = -1;
5033 /* Free the pools. */
5035 free_sched_pools (void)
5039 sched_lists_pool.release ();
5040 gcc_assert (succs_info_pool.top == -1);
5041 for (i = 0; i <= succs_info_pool.max_top; i++)
5043 succs_info_pool.stack[i].succs_ok.release ();
5044 succs_info_pool.stack[i].succs_other.release ();
5045 succs_info_pool.stack[i].probs_ok.release ();
5047 free (succs_info_pool.stack);
5051 /* Returns a position in RGN where BB can be inserted retaining
5052 topological order. */
5054 find_place_to_insert_bb (basic_block bb, int rgn)
5056 bool has_preds_outside_rgn = false;
5060 /* Find whether we have preds outside the region. */
5061 FOR_EACH_EDGE (e, ei, bb->preds)
5062 if (!in_current_region_p (e->src))
5064 has_preds_outside_rgn = true;
5068 /* Recompute the top order -- needed when we have > 1 pred
5069 and in case we don't have preds outside. */
5070 if (flag_sel_sched_pipelining_outer_loops
5071 && (has_preds_outside_rgn || EDGE_COUNT (bb->preds) > 1))
5073 int i, bbi = bb->index, cur_bbi;
5075 recompute_rev_top_order ();
5076 for (i = RGN_NR_BLOCKS (rgn) - 1; i >= 0; i--)
5078 cur_bbi = BB_TO_BLOCK (i);
5079 if (rev_top_order_index[bbi]
5080 < rev_top_order_index[cur_bbi])
5084 /* We skipped the right block, so we increase i. We accommodate
5085 it for increasing by step later, so we decrease i. */
5088 else if (has_preds_outside_rgn)
5090 /* This is the case when we generate an extra empty block
5091 to serve as region head during pipelining. */
5092 e = EDGE_SUCC (bb, 0);
5093 gcc_assert (EDGE_COUNT (bb->succs) == 1
5094 && in_current_region_p (EDGE_SUCC (bb, 0)->dest)
5095 && (BLOCK_TO_BB (e->dest->index) == 0));
5099 /* We don't have preds outside the region. We should have
5100 the only pred, because the multiple preds case comes from
5101 the pipelining of outer loops, and that is handled above.
5102 Just take the bbi of this single pred. */
5103 if (EDGE_COUNT (bb->succs) > 0)
5107 gcc_assert (EDGE_COUNT (bb->preds) == 1);
5109 pred_bbi = EDGE_PRED (bb, 0)->src->index;
5110 return BLOCK_TO_BB (pred_bbi);
5113 /* BB has no successors. It is safe to put it in the end. */
5114 return current_nr_blocks - 1;
5117 /* Deletes an empty basic block freeing its data. */
5119 delete_and_free_basic_block (basic_block bb)
5121 gcc_assert (sel_bb_empty_p (bb));
5126 bitmap_clear_bit (blocks_to_reschedule, bb->index);
5128 /* Can't assert av_set properties because we use sel_aremove_bb
5129 when removing loop preheader from the region. At the point of
5130 removing the preheader we already have deallocated sel_region_bb_info. */
5131 gcc_assert (BB_LV_SET (bb) == NULL
5132 && !BB_LV_SET_VALID_P (bb)
5133 && BB_AV_LEVEL (bb) == 0
5134 && BB_AV_SET (bb) == NULL);
5136 delete_basic_block (bb);
5139 /* Add BB to the current region and update the region data. */
5141 add_block_to_current_region (basic_block bb)
5143 int i, pos, bbi = -2, rgn;
5145 rgn = CONTAINING_RGN (BB_TO_BLOCK (0));
5146 bbi = find_place_to_insert_bb (bb, rgn);
5148 pos = RGN_BLOCKS (rgn) + bbi;
5150 gcc_assert (RGN_HAS_REAL_EBB (rgn) == 0
5151 && ebb_head[bbi] == pos);
5153 /* Make a place for the new block. */
5156 for (i = RGN_BLOCKS (rgn + 1) - 1; i >= pos; i--)
5157 BLOCK_TO_BB (rgn_bb_table[i])++;
5159 memmove (rgn_bb_table + pos + 1,
5161 (RGN_BLOCKS (nr_regions) - pos) * sizeof (*rgn_bb_table));
5163 /* Initialize data for BB. */
5164 rgn_bb_table[pos] = bb->index;
5165 BLOCK_TO_BB (bb->index) = bbi;
5166 CONTAINING_RGN (bb->index) = rgn;
5168 RGN_NR_BLOCKS (rgn)++;
5170 for (i = rgn + 1; i <= nr_regions; i++)
5174 /* Remove BB from the current region and update the region data. */
5176 remove_bb_from_region (basic_block bb)
5178 int i, pos, bbi = -2, rgn;
5180 rgn = CONTAINING_RGN (BB_TO_BLOCK (0));
5181 bbi = BLOCK_TO_BB (bb->index);
5182 pos = RGN_BLOCKS (rgn) + bbi;
5184 gcc_assert (RGN_HAS_REAL_EBB (rgn) == 0
5185 && ebb_head[bbi] == pos);
5187 for (i = RGN_BLOCKS (rgn + 1) - 1; i >= pos; i--)
5188 BLOCK_TO_BB (rgn_bb_table[i])--;
5190 memmove (rgn_bb_table + pos,
5191 rgn_bb_table + pos + 1,
5192 (RGN_BLOCKS (nr_regions) - pos) * sizeof (*rgn_bb_table));
5194 RGN_NR_BLOCKS (rgn)--;
5195 for (i = rgn + 1; i <= nr_regions; i++)
5199 /* Add BB to the current region and update all data. If BB is NULL, add all
5200 blocks from last_added_blocks vector. */
5202 sel_add_bb (basic_block bb)
5204 /* Extend luids so that new notes will receive zero luids. */
5205 sched_extend_luids ();
5207 sel_init_bbs (last_added_blocks);
5209 /* When bb is passed explicitly, the vector should contain
5210 the only element that equals to bb; otherwise, the vector
5211 should not be NULL. */
5212 gcc_assert (last_added_blocks.exists ());
5216 gcc_assert (last_added_blocks.length () == 1
5217 && last_added_blocks[0] == bb);
5218 add_block_to_current_region (bb);
5220 /* We associate creating/deleting data sets with the first insn
5221 appearing / disappearing in the bb. */
5222 if (!sel_bb_empty_p (bb) && BB_LV_SET (bb) == NULL)
5223 create_initial_data_sets (bb);
5225 last_added_blocks.release ();
5228 /* BB is NULL - process LAST_ADDED_BLOCKS instead. */
5231 basic_block temp_bb = NULL;
5234 last_added_blocks.iterate (i, &bb); i++)
5236 add_block_to_current_region (bb);
5240 /* We need to fetch at least one bb so we know the region
5242 gcc_assert (temp_bb != NULL);
5245 last_added_blocks.release ();
5248 rgn_setup_region (CONTAINING_RGN (bb->index));
5251 /* Remove BB from the current region and update all data.
5252 If REMOVE_FROM_CFG_PBB is true, also remove the block cfom cfg. */
5254 sel_remove_bb (basic_block bb, bool remove_from_cfg_p)
5256 unsigned idx = bb->index;
5258 gcc_assert (bb != NULL && BB_NOTE_LIST (bb) == NULL_RTX);
5260 remove_bb_from_region (bb);
5261 return_bb_to_pool (bb);
5262 bitmap_clear_bit (blocks_to_reschedule, idx);
5264 if (remove_from_cfg_p)
5266 basic_block succ = single_succ (bb);
5267 delete_and_free_basic_block (bb);
5268 set_immediate_dominator (CDI_DOMINATORS, succ,
5269 recompute_dominator (CDI_DOMINATORS, succ));
5272 rgn_setup_region (CONTAINING_RGN (idx));
5275 /* Concatenate info of EMPTY_BB to info of MERGE_BB. */
5277 move_bb_info (basic_block merge_bb, basic_block empty_bb)
5279 if (in_current_region_p (merge_bb))
5280 concat_note_lists (BB_NOTE_LIST (empty_bb),
5281 &BB_NOTE_LIST (merge_bb));
5282 BB_NOTE_LIST (empty_bb) = NULL;
5286 /* Remove EMPTY_BB. If REMOVE_FROM_CFG_P is false, remove EMPTY_BB from
5287 region, but keep it in CFG. */
5289 remove_empty_bb (basic_block empty_bb, bool remove_from_cfg_p)
5291 /* The block should contain just a note or a label.
5292 We try to check whether it is unused below. */
5293 gcc_assert (BB_HEAD (empty_bb) == BB_END (empty_bb)
5294 || LABEL_P (BB_HEAD (empty_bb)));
5296 /* If basic block has predecessors or successors, redirect them. */
5297 if (remove_from_cfg_p
5298 && (EDGE_COUNT (empty_bb->preds) > 0
5299 || EDGE_COUNT (empty_bb->succs) > 0))
5304 /* We need to init PRED and SUCC before redirecting edges. */
5305 if (EDGE_COUNT (empty_bb->preds) > 0)
5309 gcc_assert (EDGE_COUNT (empty_bb->preds) == 1);
5311 e = EDGE_PRED (empty_bb, 0);
5312 gcc_assert (e->src == empty_bb->prev_bb
5313 && (e->flags & EDGE_FALLTHRU));
5315 pred = empty_bb->prev_bb;
5320 if (EDGE_COUNT (empty_bb->succs) > 0)
5322 /* We do not check fallthruness here as above, because
5323 after removing a jump the edge may actually be not fallthru. */
5324 gcc_assert (EDGE_COUNT (empty_bb->succs) == 1);
5325 succ = EDGE_SUCC (empty_bb, 0)->dest;
5330 if (EDGE_COUNT (empty_bb->preds) > 0 && succ != NULL)
5332 edge e = EDGE_PRED (empty_bb, 0);
5334 if (e->flags & EDGE_FALLTHRU)
5335 redirect_edge_succ_nodup (e, succ);
5337 sel_redirect_edge_and_branch (EDGE_PRED (empty_bb, 0), succ);
5340 if (EDGE_COUNT (empty_bb->succs) > 0 && pred != NULL)
5342 edge e = EDGE_SUCC (empty_bb, 0);
5344 if (find_edge (pred, e->dest) == NULL)
5345 redirect_edge_pred (e, pred);
5349 /* Finish removing. */
5350 sel_remove_bb (empty_bb, remove_from_cfg_p);
5353 /* An implementation of create_basic_block hook, which additionally updates
5354 per-bb data structures. */
5356 sel_create_basic_block (void *headp, void *endp, basic_block after)
5359 rtx_note *new_bb_note;
5361 gcc_assert (flag_sel_sched_pipelining_outer_loops
5362 || !last_added_blocks.exists ());
5364 new_bb_note = get_bb_note_from_pool ();
5366 if (new_bb_note == NULL_RTX)
5367 new_bb = orig_cfg_hooks.create_basic_block (headp, endp, after);
5370 new_bb = create_basic_block_structure ((rtx_insn *) headp,
5372 new_bb_note, after);
5376 last_added_blocks.safe_push (new_bb);
5381 /* Implement sched_init_only_bb (). */
5383 sel_init_only_bb (basic_block bb, basic_block after)
5385 gcc_assert (after == NULL);
5388 rgn_make_new_region_out_of_new_block (bb);
5391 /* Update the latch when we've splitted or merged it from FROM block to TO.
5392 This should be checked for all outer loops, too. */
5394 change_loops_latches (basic_block from, basic_block to)
5396 gcc_assert (from != to);
5398 if (current_loop_nest)
5402 for (loop = current_loop_nest; loop; loop = loop_outer (loop))
5403 if (considered_for_pipelining_p (loop) && loop->latch == from)
5405 gcc_assert (loop == current_loop_nest);
5407 gcc_assert (loop_latch_edge (loop));
5412 /* Splits BB on two basic blocks, adding it to the region and extending
5413 per-bb data structures. Returns the newly created bb. */
5415 sel_split_block (basic_block bb, rtx after)
5420 new_bb = sched_split_block_1 (bb, after);
5421 sel_add_bb (new_bb);
5423 /* This should be called after sel_add_bb, because this uses
5424 CONTAINING_RGN for the new block, which is not yet initialized.
5425 FIXME: this function may be a no-op now. */
5426 change_loops_latches (bb, new_bb);
5428 /* Update ORIG_BB_INDEX for insns moved into the new block. */
5429 FOR_BB_INSNS (new_bb, insn)
5431 EXPR_ORIG_BB_INDEX (INSN_EXPR (insn)) = new_bb->index;
5433 if (sel_bb_empty_p (bb))
5435 gcc_assert (!sel_bb_empty_p (new_bb));
5437 /* NEW_BB has data sets that need to be updated and BB holds
5438 data sets that should be removed. Exchange these data sets
5439 so that we won't lose BB's valid data sets. */
5440 exchange_data_sets (new_bb, bb);
5441 free_data_sets (bb);
5444 if (!sel_bb_empty_p (new_bb)
5445 && bitmap_bit_p (blocks_to_reschedule, bb->index))
5446 bitmap_set_bit (blocks_to_reschedule, new_bb->index);
5451 /* If BB ends with a jump insn whose ID is bigger then PREV_MAX_UID, return it.
5452 Otherwise returns NULL. */
5454 check_for_new_jump (basic_block bb, int prev_max_uid)
5458 end = sel_bb_end (bb);
5459 if (end && INSN_UID (end) >= prev_max_uid)
5464 /* Look for a new jump either in FROM_BB block or in newly created JUMP_BB block.
5465 New means having UID at least equal to PREV_MAX_UID. */
5467 find_new_jump (basic_block from, basic_block jump_bb, int prev_max_uid)
5471 /* Return immediately if no new insns were emitted. */
5472 if (get_max_uid () == prev_max_uid)
5475 /* Now check both blocks for new jumps. It will ever be only one. */
5476 if ((jump = check_for_new_jump (from, prev_max_uid)))
5480 && (jump = check_for_new_jump (jump_bb, prev_max_uid)))
5485 /* Splits E and adds the newly created basic block to the current region.
5486 Returns this basic block. */
5488 sel_split_edge (edge e)
5490 basic_block new_bb, src, other_bb = NULL;
5495 prev_max_uid = get_max_uid ();
5496 new_bb = split_edge (e);
5498 if (flag_sel_sched_pipelining_outer_loops
5499 && current_loop_nest)
5504 /* Some of the basic blocks might not have been added to the loop.
5505 Add them here, until this is fixed in force_fallthru. */
5507 last_added_blocks.iterate (i, &bb); i++)
5508 if (!bb->loop_father)
5510 add_bb_to_loop (bb, e->dest->loop_father);
5512 gcc_assert (!other_bb && (new_bb->index != bb->index));
5517 /* Add all last_added_blocks to the region. */
5520 jump = find_new_jump (src, new_bb, prev_max_uid);
5522 sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP);
5524 /* Put the correct lv set on this block. */
5525 if (other_bb && !sel_bb_empty_p (other_bb))
5526 compute_live (sel_bb_head (other_bb));
5531 /* Implement sched_create_empty_bb (). */
5533 sel_create_empty_bb (basic_block after)
5537 new_bb = sched_create_empty_bb_1 (after);
5539 /* We'll explicitly initialize NEW_BB via sel_init_only_bb () a bit
5541 gcc_assert (last_added_blocks.length () == 1
5542 && last_added_blocks[0] == new_bb);
5544 last_added_blocks.release ();
5548 /* Implement sched_create_recovery_block. ORIG_INSN is where block
5549 will be splitted to insert a check. */
5551 sel_create_recovery_block (insn_t orig_insn)
5553 basic_block first_bb, second_bb, recovery_block;
5554 basic_block before_recovery = NULL;
5557 first_bb = BLOCK_FOR_INSN (orig_insn);
5558 if (sel_bb_end_p (orig_insn))
5560 /* Avoid introducing an empty block while splitting. */
5561 gcc_assert (single_succ_p (first_bb));
5562 second_bb = single_succ (first_bb);
5565 second_bb = sched_split_block (first_bb, orig_insn);
5567 recovery_block = sched_create_recovery_block (&before_recovery);
5568 if (before_recovery)
5569 copy_lv_set_from (before_recovery, EXIT_BLOCK_PTR_FOR_FN (cfun));
5571 gcc_assert (sel_bb_empty_p (recovery_block));
5572 sched_create_recovery_edges (first_bb, recovery_block, second_bb);
5573 if (current_loops != NULL)
5574 add_bb_to_loop (recovery_block, first_bb->loop_father);
5576 sel_add_bb (recovery_block);
5578 jump = BB_END (recovery_block);
5579 gcc_assert (sel_bb_head (recovery_block) == jump);
5580 sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP);
5582 return recovery_block;
5585 /* Merge basic block B into basic block A. */
5587 sel_merge_blocks (basic_block a, basic_block b)
5589 gcc_assert (sel_bb_empty_p (b)
5590 && EDGE_COUNT (b->preds) == 1
5591 && EDGE_PRED (b, 0)->src == b->prev_bb);
5593 move_bb_info (b->prev_bb, b);
5594 remove_empty_bb (b, false);
5595 merge_blocks (a, b);
5596 change_loops_latches (b, a);
5599 /* A wrapper for redirect_edge_and_branch_force, which also initializes
5600 data structures for possibly created bb and insns. */
5602 sel_redirect_edge_and_branch_force (edge e, basic_block to)
5604 basic_block jump_bb, src, orig_dest = e->dest;
5609 /* This function is now used only for bookkeeping code creation, where
5610 we'll never get the single pred of orig_dest block and thus will not
5611 hit unreachable blocks when updating dominator info. */
5612 gcc_assert (!sel_bb_empty_p (e->src)
5613 && !single_pred_p (orig_dest));
5615 prev_max_uid = get_max_uid ();
5616 /* Compute and pass old_seqno down to sel_init_new_insn only for the case
5617 when the conditional jump being redirected may become unconditional. */
5618 if (any_condjump_p (BB_END (src))
5619 && INSN_SEQNO (BB_END (src)) >= 0)
5620 old_seqno = INSN_SEQNO (BB_END (src));
5622 jump_bb = redirect_edge_and_branch_force (e, to);
5623 if (jump_bb != NULL)
5624 sel_add_bb (jump_bb);
5626 /* This function could not be used to spoil the loop structure by now,
5627 thus we don't care to update anything. But check it to be sure. */
5628 if (current_loop_nest
5630 gcc_assert (loop_latch_edge (current_loop_nest));
5632 jump = find_new_jump (src, jump_bb, prev_max_uid);
5634 sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP,
5636 set_immediate_dominator (CDI_DOMINATORS, to,
5637 recompute_dominator (CDI_DOMINATORS, to));
5638 set_immediate_dominator (CDI_DOMINATORS, orig_dest,
5639 recompute_dominator (CDI_DOMINATORS, orig_dest));
5640 if (jump && sel_bb_head_p (jump))
5641 compute_live (jump);
5644 /* A wrapper for redirect_edge_and_branch. Return TRUE if blocks connected by
5645 redirected edge are in reverse topological order. */
5647 sel_redirect_edge_and_branch (edge e, basic_block to)
5650 basic_block src, orig_dest = e->dest;
5654 bool recompute_toporder_p = false;
5655 bool maybe_unreachable = single_pred_p (orig_dest);
5658 latch_edge_p = (pipelining_p
5659 && current_loop_nest
5660 && e == loop_latch_edge (current_loop_nest));
5663 prev_max_uid = get_max_uid ();
5665 /* Compute and pass old_seqno down to sel_init_new_insn only for the case
5666 when the conditional jump being redirected may become unconditional. */
5667 if (any_condjump_p (BB_END (src))
5668 && INSN_SEQNO (BB_END (src)) >= 0)
5669 old_seqno = INSN_SEQNO (BB_END (src));
5671 redirected = redirect_edge_and_branch (e, to);
5673 gcc_assert (redirected && !last_added_blocks.exists ());
5675 /* When we've redirected a latch edge, update the header. */
5678 current_loop_nest->header = to;
5679 gcc_assert (loop_latch_edge (current_loop_nest));
5682 /* In rare situations, the topological relation between the blocks connected
5683 by the redirected edge can change (see PR42245 for an example). Update
5684 block_to_bb/bb_to_block. */
5685 if (CONTAINING_RGN (e->src->index) == CONTAINING_RGN (to->index)
5686 && BLOCK_TO_BB (e->src->index) > BLOCK_TO_BB (to->index))
5687 recompute_toporder_p = true;
5689 jump = find_new_jump (src, NULL, prev_max_uid);
5691 sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP, old_seqno);
5693 /* Only update dominator info when we don't have unreachable blocks.
5694 Otherwise we'll update in maybe_tidy_empty_bb. */
5695 if (!maybe_unreachable)
5697 set_immediate_dominator (CDI_DOMINATORS, to,
5698 recompute_dominator (CDI_DOMINATORS, to));
5699 set_immediate_dominator (CDI_DOMINATORS, orig_dest,
5700 recompute_dominator (CDI_DOMINATORS, orig_dest));
5702 if (jump && sel_bb_head_p (jump))
5703 compute_live (jump);
5704 return recompute_toporder_p;
5707 /* This variable holds the cfg hooks used by the selective scheduler. */
5708 static struct cfg_hooks sel_cfg_hooks;
5710 /* Register sel-sched cfg hooks. */
5712 sel_register_cfg_hooks (void)
5714 sched_split_block = sel_split_block;
5716 orig_cfg_hooks = get_cfg_hooks ();
5717 sel_cfg_hooks = orig_cfg_hooks;
5719 sel_cfg_hooks.create_basic_block = sel_create_basic_block;
5721 set_cfg_hooks (sel_cfg_hooks);
5723 sched_init_only_bb = sel_init_only_bb;
5724 sched_split_block = sel_split_block;
5725 sched_create_empty_bb = sel_create_empty_bb;
5728 /* Unregister sel-sched cfg hooks. */
5730 sel_unregister_cfg_hooks (void)
5732 sched_create_empty_bb = NULL;
5733 sched_split_block = NULL;
5734 sched_init_only_bb = NULL;
5736 set_cfg_hooks (orig_cfg_hooks);
5740 /* Emit an insn rtx based on PATTERN. If a jump insn is wanted,
5741 LABEL is where this jump should be directed. */
5743 create_insn_rtx_from_pattern (rtx pattern, rtx label)
5747 gcc_assert (!INSN_P (pattern));
5751 if (label == NULL_RTX)
5752 insn_rtx = emit_insn (pattern);
5753 else if (DEBUG_INSN_P (label))
5754 insn_rtx = emit_debug_insn (pattern);
5757 insn_rtx = emit_jump_insn (pattern);
5758 JUMP_LABEL (insn_rtx) = label;
5759 ++LABEL_NUSES (label);
5764 sched_extend_luids ();
5765 sched_extend_target ();
5766 sched_deps_init (false);
5768 /* Initialize INSN_CODE now. */
5769 recog_memoized (insn_rtx);
5773 /* Create a new vinsn for INSN_RTX. FORCE_UNIQUE_P is true when the vinsn
5774 must not be clonable. */
5776 create_vinsn_from_insn_rtx (rtx_insn *insn_rtx, bool force_unique_p)
5778 gcc_assert (INSN_P (insn_rtx) && !INSN_IN_STREAM_P (insn_rtx));
5780 /* If VINSN_TYPE is not USE, retain its uniqueness. */
5781 return vinsn_create (insn_rtx, force_unique_p);
5784 /* Create a copy of INSN_RTX. */
5786 create_copy_of_insn_rtx (rtx insn_rtx)
5791 if (DEBUG_INSN_P (insn_rtx))
5792 return create_insn_rtx_from_pattern (copy_rtx (PATTERN (insn_rtx)),
5795 gcc_assert (NONJUMP_INSN_P (insn_rtx));
5797 res = create_insn_rtx_from_pattern (copy_rtx (PATTERN (insn_rtx)),
5800 /* Locate the end of existing REG_NOTES in NEW_RTX. */
5801 rtx *ptail = ®_NOTES (res);
5802 while (*ptail != NULL_RTX)
5803 ptail = &XEXP (*ptail, 1);
5805 /* Copy all REG_NOTES except REG_EQUAL/REG_EQUIV and REG_LABEL_OPERAND
5806 since mark_jump_label will make them. REG_LABEL_TARGETs are created
5807 there too, but are supposed to be sticky, so we copy them. */
5808 for (link = REG_NOTES (insn_rtx); link; link = XEXP (link, 1))
5809 if (REG_NOTE_KIND (link) != REG_LABEL_OPERAND
5810 && REG_NOTE_KIND (link) != REG_EQUAL
5811 && REG_NOTE_KIND (link) != REG_EQUIV)
5813 *ptail = duplicate_reg_note (link);
5814 ptail = &XEXP (*ptail, 1);
5820 /* Change vinsn field of EXPR to hold NEW_VINSN. */
5822 change_vinsn_in_expr (expr_t expr, vinsn_t new_vinsn)
5824 vinsn_detach (EXPR_VINSN (expr));
5826 EXPR_VINSN (expr) = new_vinsn;
5827 vinsn_attach (new_vinsn);
5830 /* Helpers for global init. */
5831 /* This structure is used to be able to call existing bundling mechanism
5832 and calculate insn priorities. */
5833 static struct haifa_sched_info sched_sel_haifa_sched_info =
5835 NULL, /* init_ready_list */
5836 NULL, /* can_schedule_ready_p */
5837 NULL, /* schedule_more_p */
5838 NULL, /* new_ready */
5839 NULL, /* rgn_rank */
5840 sel_print_insn, /* rgn_print_insn */
5841 contributes_to_priority,
5842 NULL, /* insn_finishes_block_p */
5848 NULL, /* add_remove_insn */
5849 NULL, /* begin_schedule_ready */
5850 NULL, /* begin_move_insn */
5851 NULL, /* advance_target_bb */
5859 /* Setup special insns used in the scheduler. */
5861 setup_nop_and_exit_insns (void)
5863 gcc_assert (nop_pattern == NULL_RTX
5864 && exit_insn == NULL_RTX);
5866 nop_pattern = constm1_rtx;
5869 emit_insn (nop_pattern);
5870 exit_insn = get_insns ();
5872 set_block_for_insn (exit_insn, EXIT_BLOCK_PTR_FOR_FN (cfun));
5875 /* Free special insns used in the scheduler. */
5877 free_nop_and_exit_insns (void)
5880 nop_pattern = NULL_RTX;
5883 /* Setup a special vinsn used in new insns initialization. */
5885 setup_nop_vinsn (void)
5887 nop_vinsn = vinsn_create (exit_insn, false);
5888 vinsn_attach (nop_vinsn);
5891 /* Free a special vinsn used in new insns initialization. */
5893 free_nop_vinsn (void)
5895 gcc_assert (VINSN_COUNT (nop_vinsn) == 1);
5896 vinsn_detach (nop_vinsn);
5900 /* Call a set_sched_flags hook. */
5902 sel_set_sched_flags (void)
5904 /* ??? This means that set_sched_flags were called, and we decided to
5905 support speculation. However, set_sched_flags also modifies flags
5906 on current_sched_info, doing this only at global init. And we
5907 sometimes change c_s_i later. So put the correct flags again. */
5908 if (spec_info && targetm.sched.set_sched_flags)
5909 targetm.sched.set_sched_flags (spec_info);
5912 /* Setup pointers to global sched info structures. */
5914 sel_setup_sched_infos (void)
5916 rgn_setup_common_sched_info ();
5918 memcpy (&sel_common_sched_info, common_sched_info,
5919 sizeof (sel_common_sched_info));
5921 sel_common_sched_info.fix_recovery_cfg = NULL;
5922 sel_common_sched_info.add_block = NULL;
5923 sel_common_sched_info.estimate_number_of_insns
5924 = sel_estimate_number_of_insns;
5925 sel_common_sched_info.luid_for_non_insn = sel_luid_for_non_insn;
5926 sel_common_sched_info.sched_pass_id = SCHED_SEL_PASS;
5928 common_sched_info = &sel_common_sched_info;
5930 current_sched_info = &sched_sel_haifa_sched_info;
5931 current_sched_info->sched_max_insns_priority =
5932 get_rgn_sched_max_insns_priority ();
5934 sel_set_sched_flags ();
5938 /* Adds basic block BB to region RGN at the position *BB_ORD_INDEX,
5939 *BB_ORD_INDEX after that is increased. */
5941 sel_add_block_to_region (basic_block bb, int *bb_ord_index, int rgn)
5943 RGN_NR_BLOCKS (rgn) += 1;
5944 RGN_DONT_CALC_DEPS (rgn) = 0;
5945 RGN_HAS_REAL_EBB (rgn) = 0;
5946 CONTAINING_RGN (bb->index) = rgn;
5947 BLOCK_TO_BB (bb->index) = *bb_ord_index;
5948 rgn_bb_table[RGN_BLOCKS (rgn) + *bb_ord_index] = bb->index;
5951 /* FIXME: it is true only when not scheduling ebbs. */
5952 RGN_BLOCKS (rgn + 1) = RGN_BLOCKS (rgn) + RGN_NR_BLOCKS (rgn);
5955 /* Functions to support pipelining of outer loops. */
5957 /* Creates a new empty region and returns it's number. */
5959 sel_create_new_region (void)
5961 int new_rgn_number = nr_regions;
5963 RGN_NR_BLOCKS (new_rgn_number) = 0;
5965 /* FIXME: This will work only when EBBs are not created. */
5966 if (new_rgn_number != 0)
5967 RGN_BLOCKS (new_rgn_number) = RGN_BLOCKS (new_rgn_number - 1) +
5968 RGN_NR_BLOCKS (new_rgn_number - 1);
5970 RGN_BLOCKS (new_rgn_number) = 0;
5972 /* Set the blocks of the next region so the other functions may
5973 calculate the number of blocks in the region. */
5974 RGN_BLOCKS (new_rgn_number + 1) = RGN_BLOCKS (new_rgn_number) +
5975 RGN_NR_BLOCKS (new_rgn_number);
5979 return new_rgn_number;
5982 /* If X has a smaller topological sort number than Y, returns -1;
5983 if greater, returns 1. */
5985 bb_top_order_comparator (const void *x, const void *y)
5987 basic_block bb1 = *(const basic_block *) x;
5988 basic_block bb2 = *(const basic_block *) y;
5990 gcc_assert (bb1 == bb2
5991 || rev_top_order_index[bb1->index]
5992 != rev_top_order_index[bb2->index]);
5994 /* It's a reverse topological order in REV_TOP_ORDER_INDEX, so
5995 bbs with greater number should go earlier. */
5996 if (rev_top_order_index[bb1->index] > rev_top_order_index[bb2->index])
6002 /* Create a region for LOOP and return its number. If we don't want
6003 to pipeline LOOP, return -1. */
6005 make_region_from_loop (class loop *loop)
6008 int new_rgn_number = -1;
6011 /* Basic block index, to be assigned to BLOCK_TO_BB. */
6012 int bb_ord_index = 0;
6013 basic_block *loop_blocks;
6014 basic_block preheader_block;
6017 > (unsigned) PARAM_VALUE (PARAM_MAX_PIPELINE_REGION_BLOCKS))
6020 /* Don't pipeline loops whose latch belongs to some of its inner loops. */
6021 for (inner = loop->inner; inner; inner = inner->inner)
6022 if (flow_bb_inside_loop_p (inner, loop->latch))
6025 loop->ninsns = num_loop_insns (loop);
6026 if ((int) loop->ninsns > PARAM_VALUE (PARAM_MAX_PIPELINE_REGION_INSNS))
6029 loop_blocks = get_loop_body_in_custom_order (loop, bb_top_order_comparator);
6031 for (i = 0; i < loop->num_nodes; i++)
6032 if (loop_blocks[i]->flags & BB_IRREDUCIBLE_LOOP)
6038 preheader_block = loop_preheader_edge (loop)->src;
6039 gcc_assert (preheader_block);
6040 gcc_assert (loop_blocks[0] == loop->header);
6042 new_rgn_number = sel_create_new_region ();
6044 sel_add_block_to_region (preheader_block, &bb_ord_index, new_rgn_number);
6045 bitmap_set_bit (bbs_in_loop_rgns, preheader_block->index);
6047 for (i = 0; i < loop->num_nodes; i++)
6049 /* Add only those blocks that haven't been scheduled in the inner loop.
6050 The exception is the basic blocks with bookkeeping code - they should
6051 be added to the region (and they actually don't belong to the loop
6052 body, but to the region containing that loop body). */
6054 gcc_assert (new_rgn_number >= 0);
6056 if (! bitmap_bit_p (bbs_in_loop_rgns, loop_blocks[i]->index))
6058 sel_add_block_to_region (loop_blocks[i], &bb_ord_index,
6060 bitmap_set_bit (bbs_in_loop_rgns, loop_blocks[i]->index);
6065 MARK_LOOP_FOR_PIPELINING (loop);
6067 return new_rgn_number;
6070 /* Create a new region from preheader blocks LOOP_BLOCKS. */
6072 make_region_from_loop_preheader (vec<basic_block> *&loop_blocks)
6075 int new_rgn_number = -1;
6078 /* Basic block index, to be assigned to BLOCK_TO_BB. */
6079 int bb_ord_index = 0;
6081 new_rgn_number = sel_create_new_region ();
6083 FOR_EACH_VEC_ELT (*loop_blocks, i, bb)
6085 gcc_assert (new_rgn_number >= 0);
6087 sel_add_block_to_region (bb, &bb_ord_index, new_rgn_number);
6090 vec_free (loop_blocks);
6094 /* Create region(s) from loop nest LOOP, such that inner loops will be
6095 pipelined before outer loops. Returns true when a region for LOOP
6098 make_regions_from_loop_nest (class loop *loop)
6100 class loop *cur_loop;
6103 /* Traverse all inner nodes of the loop. */
6104 for (cur_loop = loop->inner; cur_loop; cur_loop = cur_loop->next)
6105 if (! bitmap_bit_p (bbs_in_loop_rgns, cur_loop->header->index))
6108 /* At this moment all regular inner loops should have been pipelined.
6109 Try to create a region from this loop. */
6110 rgn_number = make_region_from_loop (loop);
6115 loop_nests.safe_push (loop);
6119 /* Initalize data structures needed. */
6121 sel_init_pipelining (void)
6123 /* Collect loop information to be used in outer loops pipelining. */
6124 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
6125 | LOOPS_HAVE_FALLTHRU_PREHEADERS
6126 | LOOPS_HAVE_RECORDED_EXITS
6127 | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS);
6128 current_loop_nest = NULL;
6130 bbs_in_loop_rgns = sbitmap_alloc (last_basic_block_for_fn (cfun));
6131 bitmap_clear (bbs_in_loop_rgns);
6133 recompute_rev_top_order ();
6136 /* Returns a class loop for region RGN. */
6138 get_loop_nest_for_rgn (unsigned int rgn)
6140 /* Regions created with extend_rgns don't have corresponding loop nests,
6141 because they don't represent loops. */
6142 if (rgn < loop_nests.length ())
6143 return loop_nests[rgn];
6148 /* True when LOOP was included into pipelining regions. */
6150 considered_for_pipelining_p (class loop *loop)
6152 if (loop_depth (loop) == 0)
6155 /* Now, the loop could be too large or irreducible. Check whether its
6156 region is in LOOP_NESTS.
6157 We determine the region number of LOOP as the region number of its
6158 latch. We can't use header here, because this header could be
6159 just removed preheader and it will give us the wrong region number.
6160 Latch can't be used because it could be in the inner loop too. */
6161 if (LOOP_MARKED_FOR_PIPELINING_P (loop))
6163 int rgn = CONTAINING_RGN (loop->latch->index);
6165 gcc_assert ((unsigned) rgn < loop_nests.length ());
6172 /* Makes regions from the rest of the blocks, after loops are chosen
6175 make_regions_from_the_rest (void)
6186 /* Index in rgn_bb_table where to start allocating new regions. */
6187 cur_rgn_blocks = nr_regions ? RGN_BLOCKS (nr_regions) : 0;
6189 /* Make regions from all the rest basic blocks - those that don't belong to
6190 any loop or belong to irreducible loops. Prepare the data structures
6193 /* LOOP_HDR[I] == -1 if I-th bb doesn't belong to any loop,
6194 LOOP_HDR[I] == LOOP_HDR[J] iff basic blocks I and J reside within the same
6196 loop_hdr = XNEWVEC (int, last_basic_block_for_fn (cfun));
6197 degree = XCNEWVEC (int, last_basic_block_for_fn (cfun));
6200 /* For each basic block that belongs to some loop assign the number
6201 of innermost loop it belongs to. */
6202 for (i = 0; i < last_basic_block_for_fn (cfun); i++)
6205 FOR_EACH_BB_FN (bb, cfun)
6207 if (bb->loop_father && bb->loop_father->num != 0
6208 && !(bb->flags & BB_IRREDUCIBLE_LOOP))
6209 loop_hdr[bb->index] = bb->loop_father->num;
6212 /* For each basic block degree is calculated as the number of incoming
6213 edges, that are going out of bbs that are not yet scheduled.
6214 The basic blocks that are scheduled have degree value of zero. */
6215 FOR_EACH_BB_FN (bb, cfun)
6217 degree[bb->index] = 0;
6219 if (!bitmap_bit_p (bbs_in_loop_rgns, bb->index))
6221 FOR_EACH_EDGE (e, ei, bb->preds)
6222 if (!bitmap_bit_p (bbs_in_loop_rgns, e->src->index))
6223 degree[bb->index]++;
6226 degree[bb->index] = -1;
6229 extend_rgns (degree, &cur_rgn_blocks, bbs_in_loop_rgns, loop_hdr);
6231 /* Any block that did not end up in a region is placed into a region
6233 FOR_EACH_BB_FN (bb, cfun)
6234 if (degree[bb->index] >= 0)
6236 rgn_bb_table[cur_rgn_blocks] = bb->index;
6237 RGN_NR_BLOCKS (nr_regions) = 1;
6238 RGN_BLOCKS (nr_regions) = cur_rgn_blocks++;
6239 RGN_DONT_CALC_DEPS (nr_regions) = 0;
6240 RGN_HAS_REAL_EBB (nr_regions) = 0;
6241 CONTAINING_RGN (bb->index) = nr_regions++;
6242 BLOCK_TO_BB (bb->index) = 0;
6249 /* Free data structures used in pipelining of loops. */
6250 void sel_finish_pipelining (void)
6254 /* Release aux fields so we don't free them later by mistake. */
6255 FOR_EACH_LOOP (loop, 0)
6258 loop_optimizer_finalize ();
6260 loop_nests.release ();
6262 free (rev_top_order_index);
6263 rev_top_order_index = NULL;
6266 /* This function replaces the find_rgns when
6267 FLAG_SEL_SCHED_PIPELINING_OUTER_LOOPS is set. */
6269 sel_find_rgns (void)
6271 sel_init_pipelining ();
6278 FOR_EACH_LOOP (loop, (flag_sel_sched_pipelining_outer_loops
6280 : LI_ONLY_INNERMOST))
6281 make_regions_from_loop_nest (loop);
6284 /* Make regions from all the rest basic blocks and schedule them.
6285 These blocks include blocks that don't belong to any loop or belong
6286 to irreducible loops. */
6287 make_regions_from_the_rest ();
6289 /* We don't need bbs_in_loop_rgns anymore. */
6290 sbitmap_free (bbs_in_loop_rgns);
6291 bbs_in_loop_rgns = NULL;
6294 /* Add the preheader blocks from previous loop to current region taking
6295 it from LOOP_PREHEADER_BLOCKS (current_loop_nest) and record them in *BBS.
6296 This function is only used with -fsel-sched-pipelining-outer-loops. */
6298 sel_add_loop_preheaders (bb_vec_t *bbs)
6302 vec<basic_block> *preheader_blocks
6303 = LOOP_PREHEADER_BLOCKS (current_loop_nest);
6305 if (!preheader_blocks)
6308 for (i = 0; preheader_blocks->iterate (i, &bb); i++)
6310 bbs->safe_push (bb);
6311 last_added_blocks.safe_push (bb);
6315 vec_free (preheader_blocks);
6318 /* While pipelining outer loops, returns TRUE if BB is a loop preheader.
6319 Please note that the function should also work when pipelining_p is
6320 false, because it is used when deciding whether we should or should
6321 not reschedule pipelined code. */
6323 sel_is_loop_preheader_p (basic_block bb)
6325 if (current_loop_nest)
6329 if (preheader_removed)
6332 /* Preheader is the first block in the region. */
6333 if (BLOCK_TO_BB (bb->index) == 0)
6336 /* We used to find a preheader with the topological information.
6337 Check that the above code is equivalent to what we did before. */
6339 if (in_current_region_p (current_loop_nest->header))
6340 gcc_assert (!(BLOCK_TO_BB (bb->index)
6341 < BLOCK_TO_BB (current_loop_nest->header->index)));
6343 /* Support the situation when the latch block of outer loop
6344 could be from here. */
6345 for (outer = loop_outer (current_loop_nest);
6347 outer = loop_outer (outer))
6348 if (considered_for_pipelining_p (outer) && outer->latch == bb)
6355 /* Check whether JUMP_BB ends with a jump insn that leads only to DEST_BB and
6356 can be removed, making the corresponding edge fallthrough (assuming that
6357 all basic blocks between JUMP_BB and DEST_BB are empty). */
6359 bb_has_removable_jump_to_p (basic_block jump_bb, basic_block dest_bb)
6361 if (!onlyjump_p (BB_END (jump_bb))
6362 || tablejump_p (BB_END (jump_bb), NULL, NULL))
6365 /* Several outgoing edges, abnormal edge or destination of jump is
6367 if (EDGE_COUNT (jump_bb->succs) != 1
6368 || EDGE_SUCC (jump_bb, 0)->flags & (EDGE_ABNORMAL | EDGE_CROSSING)
6369 || EDGE_SUCC (jump_bb, 0)->dest != dest_bb)
6372 /* If not anything of the upper. */
6376 /* Removes the loop preheader from the current region and saves it in
6377 PREHEADER_BLOCKS of the father loop, so they will be added later to
6378 region that represents an outer loop. */
6380 sel_remove_loop_preheader (void)
6383 int cur_rgn = CONTAINING_RGN (BB_TO_BLOCK (0));
6385 bool all_empty_p = true;
6386 vec<basic_block> *preheader_blocks
6387 = LOOP_PREHEADER_BLOCKS (loop_outer (current_loop_nest));
6389 vec_check_alloc (preheader_blocks, 0);
6391 gcc_assert (current_loop_nest);
6392 old_len = preheader_blocks->length ();
6394 /* Add blocks that aren't within the current loop to PREHEADER_BLOCKS. */
6395 for (i = 0; i < RGN_NR_BLOCKS (cur_rgn); i++)
6397 bb = BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (i));
6399 /* If the basic block belongs to region, but doesn't belong to
6400 corresponding loop, then it should be a preheader. */
6401 if (sel_is_loop_preheader_p (bb))
6403 preheader_blocks->safe_push (bb);
6404 if (BB_END (bb) != bb_note (bb))
6405 all_empty_p = false;
6409 /* Remove these blocks only after iterating over the whole region. */
6410 for (i = preheader_blocks->length () - 1; i >= old_len; i--)
6412 bb = (*preheader_blocks)[i];
6413 sel_remove_bb (bb, false);
6416 if (!considered_for_pipelining_p (loop_outer (current_loop_nest)))
6419 /* Immediately create new region from preheader. */
6420 make_region_from_loop_preheader (preheader_blocks);
6423 /* If all preheader blocks are empty - dont create new empty region.
6424 Instead, remove them completely. */
6425 FOR_EACH_VEC_ELT (*preheader_blocks, i, bb)
6429 basic_block prev_bb = bb->prev_bb, next_bb = bb->next_bb;
6431 /* Redirect all incoming edges to next basic block. */
6432 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
6434 if (! (e->flags & EDGE_FALLTHRU))
6435 redirect_edge_and_branch (e, bb->next_bb);
6437 redirect_edge_succ (e, bb->next_bb);
6439 gcc_assert (BB_NOTE_LIST (bb) == NULL);
6440 delete_and_free_basic_block (bb);
6442 /* Check if after deleting preheader there is a nonconditional
6443 jump in PREV_BB that leads to the next basic block NEXT_BB.
6444 If it is so - delete this jump and clear data sets of its
6445 basic block if it becomes empty. */
6446 if (next_bb->prev_bb == prev_bb
6447 && prev_bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
6448 && bb_has_removable_jump_to_p (prev_bb, next_bb))
6450 redirect_edge_and_branch (EDGE_SUCC (prev_bb, 0), next_bb);
6451 if (BB_END (prev_bb) == bb_note (prev_bb))
6452 free_data_sets (prev_bb);
6455 set_immediate_dominator (CDI_DOMINATORS, next_bb,
6456 recompute_dominator (CDI_DOMINATORS,
6460 vec_free (preheader_blocks);
6463 /* Store preheader within the father's loop structure. */
6464 SET_LOOP_PREHEADER_BLOCKS (loop_outer (current_loop_nest),