1 /* Instruction scheduling pass. Selective scheduler and pipeliner.
2 Copyright (C) 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
27 #include "hard-reg-set.h"
31 #include "insn-config.h"
32 #include "insn-attr.h"
39 #include "tree-pass.h"
40 #include "sched-int.h"
44 #include "langhooks.h"
45 #include "rtlhooks-def.h"
47 #ifdef INSN_SCHEDULING
48 #include "sel-sched-ir.h"
49 /* We don't have to use it except for sel_print_insn. */
50 #include "sel-sched-dump.h"
52 /* A vector holding bb info for whole scheduling pass. */
53 VEC(sel_global_bb_info_def, heap) *sel_global_bb_info = NULL;
55 /* A vector holding bb info. */
56 VEC(sel_region_bb_info_def, heap) *sel_region_bb_info = NULL;
58 /* A pool for allocating all lists. */
59 alloc_pool sched_lists_pool;
61 /* This contains information about successors for compute_av_set. */
62 struct succs_info current_succs;
64 /* Data structure to describe interaction with the generic scheduler utils. */
65 static struct common_sched_info_def sel_common_sched_info;
67 /* The loop nest being pipelined. */
68 struct loop *current_loop_nest;
70 /* LOOP_NESTS is a vector containing the corresponding loop nest for
72 static VEC(loop_p, heap) *loop_nests = NULL;
74 /* Saves blocks already in loop regions, indexed by bb->index. */
75 static sbitmap bbs_in_loop_rgns = NULL;
77 /* CFG hooks that are saved before changing create_basic_block hook. */
78 static struct cfg_hooks orig_cfg_hooks;
81 /* Array containing reverse topological index of function basic blocks,
82 indexed by BB->INDEX. */
83 static int *rev_top_order_index = NULL;
85 /* Length of the above array. */
86 static int rev_top_order_index_len = -1;
88 /* A regset pool structure. */
91 /* The stack to which regsets are returned. */
100 /* In VV we save all generated regsets so that, when destructing the
101 pool, we can compare it with V and check that every regset was returned
105 /* The pointer of VV stack. */
111 /* The difference between allocated and returned regsets. */
113 } regset_pool = { NULL, 0, 0, NULL, 0, 0, 0 };
115 /* This represents the nop pool. */
118 /* The vector which holds previously emitted nops. */
126 } nop_pool = { NULL, 0, 0 };
128 /* The pool for basic block notes. */
129 static rtx_vec_t bb_note_pool;
131 /* A NOP pattern used to emit placeholder insns. */
132 rtx nop_pattern = NULL_RTX;
133 /* A special instruction that resides in EXIT_BLOCK.
134 EXIT_INSN is successor of the insns that lead to EXIT_BLOCK. */
135 rtx exit_insn = NULL_RTX;
137 /* TRUE if while scheduling current region, which is loop, its preheader
139 bool preheader_removed = false;
142 /* Forward static declarations. */
143 static void fence_clear (fence_t);
145 static void deps_init_id (idata_t, insn_t, bool);
146 static void init_id_from_df (idata_t, insn_t, bool);
147 static expr_t set_insn_init (expr_t, vinsn_t, int);
149 static void cfg_preds (basic_block, insn_t **, int *);
150 static void prepare_insn_expr (insn_t, int);
151 static void free_history_vect (VEC (expr_history_def, heap) **);
153 static void move_bb_info (basic_block, basic_block);
154 static void remove_empty_bb (basic_block, bool);
155 static void sel_merge_blocks (basic_block, basic_block);
156 static void sel_remove_loop_preheader (void);
158 static bool insn_is_the_only_one_in_bb_p (insn_t);
159 static void create_initial_data_sets (basic_block);
161 static void invalidate_av_set (basic_block);
162 static void extend_insn_data (void);
163 static void sel_init_new_insn (insn_t, int);
164 static void finish_insns (void);
166 /* Various list functions. */
168 /* Copy an instruction list L. */
170 ilist_copy (ilist_t l)
172 ilist_t head = NULL, *tailp = &head;
176 ilist_add (tailp, ILIST_INSN (l));
177 tailp = &ILIST_NEXT (*tailp);
184 /* Invert an instruction list L. */
186 ilist_invert (ilist_t l)
192 ilist_add (&res, ILIST_INSN (l));
199 /* Add a new boundary to the LP list with parameters TO, PTR, and DC. */
201 blist_add (blist_t *lp, insn_t to, ilist_t ptr, deps_t dc)
206 bnd = BLIST_BND (*lp);
211 BND_AV1 (bnd) = NULL;
215 /* Remove the list note pointed to by LP. */
217 blist_remove (blist_t *lp)
219 bnd_t b = BLIST_BND (*lp);
221 av_set_clear (&BND_AV (b));
222 av_set_clear (&BND_AV1 (b));
223 ilist_clear (&BND_PTR (b));
228 /* Init a fence tail L. */
230 flist_tail_init (flist_tail_t l)
232 FLIST_TAIL_HEAD (l) = NULL;
233 FLIST_TAIL_TAILP (l) = &FLIST_TAIL_HEAD (l);
236 /* Try to find fence corresponding to INSN in L. */
238 flist_lookup (flist_t l, insn_t insn)
242 if (FENCE_INSN (FLIST_FENCE (l)) == insn)
243 return FLIST_FENCE (l);
251 /* Init the fields of F before running fill_insns. */
253 init_fence_for_scheduling (fence_t f)
255 FENCE_BNDS (f) = NULL;
256 FENCE_PROCESSED_P (f) = false;
257 FENCE_SCHEDULED_P (f) = false;
260 /* Add new fence consisting of INSN and STATE to the list pointed to by LP. */
262 flist_add (flist_t *lp, insn_t insn, state_t state, deps_t dc, void *tc,
263 insn_t last_scheduled_insn, VEC(rtx,gc) *executing_insns,
264 int *ready_ticks, int ready_ticks_size, insn_t sched_next,
265 int cycle, int cycle_issued_insns, int issue_more,
266 bool starts_cycle_p, bool after_stall_p)
271 f = FLIST_FENCE (*lp);
273 FENCE_INSN (f) = insn;
275 gcc_assert (state != NULL);
276 FENCE_STATE (f) = state;
278 FENCE_CYCLE (f) = cycle;
279 FENCE_ISSUED_INSNS (f) = cycle_issued_insns;
280 FENCE_STARTS_CYCLE_P (f) = starts_cycle_p;
281 FENCE_AFTER_STALL_P (f) = after_stall_p;
283 gcc_assert (dc != NULL);
286 gcc_assert (tc != NULL || targetm.sched.alloc_sched_context == NULL);
289 FENCE_LAST_SCHEDULED_INSN (f) = last_scheduled_insn;
290 FENCE_ISSUE_MORE (f) = issue_more;
291 FENCE_EXECUTING_INSNS (f) = executing_insns;
292 FENCE_READY_TICKS (f) = ready_ticks;
293 FENCE_READY_TICKS_SIZE (f) = ready_ticks_size;
294 FENCE_SCHED_NEXT (f) = sched_next;
296 init_fence_for_scheduling (f);
299 /* Remove the head node of the list pointed to by LP. */
301 flist_remove (flist_t *lp)
303 if (FENCE_INSN (FLIST_FENCE (*lp)))
304 fence_clear (FLIST_FENCE (*lp));
308 /* Clear the fence list pointed to by LP. */
310 flist_clear (flist_t *lp)
316 /* Add ORIGINAL_INSN the def list DL honoring CROSSES_CALL. */
318 def_list_add (def_list_t *dl, insn_t original_insn, bool crosses_call)
323 d = DEF_LIST_DEF (*dl);
325 d->orig_insn = original_insn;
326 d->crosses_call = crosses_call;
330 /* Functions to work with target contexts. */
332 /* Bulk target context. It is convenient for debugging purposes to ensure
333 that there are no uninitialized (null) target contexts. */
334 static tc_t bulk_tc = (tc_t) 1;
336 /* Target hooks wrappers. In the future we can provide some default
337 implementations for them. */
339 /* Allocate a store for the target context. */
341 alloc_target_context (void)
343 return (targetm.sched.alloc_sched_context
344 ? targetm.sched.alloc_sched_context () : bulk_tc);
347 /* Init target context TC.
348 If CLEAN_P is true, then make TC as it is beginning of the scheduler.
349 Overwise, copy current backend context to TC. */
351 init_target_context (tc_t tc, bool clean_p)
353 if (targetm.sched.init_sched_context)
354 targetm.sched.init_sched_context (tc, clean_p);
357 /* Allocate and initialize a target context. Meaning of CLEAN_P is the same as
358 int init_target_context (). */
360 create_target_context (bool clean_p)
362 tc_t tc = alloc_target_context ();
364 init_target_context (tc, clean_p);
368 /* Copy TC to the current backend context. */
370 set_target_context (tc_t tc)
372 if (targetm.sched.set_sched_context)
373 targetm.sched.set_sched_context (tc);
376 /* TC is about to be destroyed. Free any internal data. */
378 clear_target_context (tc_t tc)
380 if (targetm.sched.clear_sched_context)
381 targetm.sched.clear_sched_context (tc);
384 /* Clear and free it. */
386 delete_target_context (tc_t tc)
388 clear_target_context (tc);
390 if (targetm.sched.free_sched_context)
391 targetm.sched.free_sched_context (tc);
394 /* Make a copy of FROM in TO.
395 NB: May be this should be a hook. */
397 copy_target_context (tc_t to, tc_t from)
399 tc_t tmp = create_target_context (false);
401 set_target_context (from);
402 init_target_context (to, false);
404 set_target_context (tmp);
405 delete_target_context (tmp);
408 /* Create a copy of TC. */
410 create_copy_of_target_context (tc_t tc)
412 tc_t copy = alloc_target_context ();
414 copy_target_context (copy, tc);
419 /* Clear TC and initialize it according to CLEAN_P. The meaning of CLEAN_P
420 is the same as in init_target_context (). */
422 reset_target_context (tc_t tc, bool clean_p)
424 clear_target_context (tc);
425 init_target_context (tc, clean_p);
428 /* Functions to work with dependence contexts.
429 Dc (aka deps context, aka deps_t, aka struct deps *) is short for dependence
430 context. It accumulates information about processed insns to decide if
431 current insn is dependent on the processed ones. */
433 /* Make a copy of FROM in TO. */
435 copy_deps_context (deps_t to, deps_t from)
437 init_deps (to, false);
438 deps_join (to, from);
441 /* Allocate store for dep context. */
443 alloc_deps_context (void)
445 return XNEW (struct deps);
448 /* Allocate and initialize dep context. */
450 create_deps_context (void)
452 deps_t dc = alloc_deps_context ();
454 init_deps (dc, false);
458 /* Create a copy of FROM. */
460 create_copy_of_deps_context (deps_t from)
462 deps_t to = alloc_deps_context ();
464 copy_deps_context (to, from);
468 /* Clean up internal data of DC. */
470 clear_deps_context (deps_t dc)
475 /* Clear and free DC. */
477 delete_deps_context (deps_t dc)
479 clear_deps_context (dc);
483 /* Clear and init DC. */
485 reset_deps_context (deps_t dc)
487 clear_deps_context (dc);
488 init_deps (dc, false);
491 /* This structure describes the dependence analysis hooks for advancing
492 dependence context. */
493 static struct sched_deps_info_def advance_deps_context_sched_deps_info =
497 NULL, /* start_insn */
498 NULL, /* finish_insn */
499 NULL, /* start_lhs */
500 NULL, /* finish_lhs */
501 NULL, /* start_rhs */
502 NULL, /* finish_rhs */
504 haifa_note_reg_clobber,
506 NULL, /* note_mem_dep */
512 /* Process INSN and add its impact on DC. */
514 advance_deps_context (deps_t dc, insn_t insn)
516 sched_deps_info = &advance_deps_context_sched_deps_info;
517 deps_analyze_insn (dc, insn);
521 /* Functions to work with DFA states. */
523 /* Allocate store for a DFA state. */
527 return xmalloc (dfa_state_size);
530 /* Allocate and initialize DFA state. */
534 state_t state = state_alloc ();
537 advance_state (state);
541 /* Free DFA state. */
543 state_free (state_t state)
548 /* Make a copy of FROM in TO. */
550 state_copy (state_t to, state_t from)
552 memcpy (to, from, dfa_state_size);
555 /* Create a copy of FROM. */
557 state_create_copy (state_t from)
559 state_t to = state_alloc ();
561 state_copy (to, from);
566 /* Functions to work with fences. */
568 /* Clear the fence. */
570 fence_clear (fence_t f)
572 state_t s = FENCE_STATE (f);
573 deps_t dc = FENCE_DC (f);
574 void *tc = FENCE_TC (f);
576 ilist_clear (&FENCE_BNDS (f));
578 gcc_assert ((s != NULL && dc != NULL && tc != NULL)
579 || (s == NULL && dc == NULL && tc == NULL));
585 delete_deps_context (dc);
588 delete_target_context (tc);
589 VEC_free (rtx, gc, FENCE_EXECUTING_INSNS (f));
590 free (FENCE_READY_TICKS (f));
591 FENCE_READY_TICKS (f) = NULL;
594 /* Init a list of fences with successors of OLD_FENCE. */
596 init_fences (insn_t old_fence)
601 int ready_ticks_size = get_max_uid () + 1;
603 FOR_EACH_SUCC_1 (succ, si, old_fence,
604 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
610 gcc_assert (flag_sel_sched_pipelining_outer_loops);
612 flist_add (&fences, succ,
614 create_deps_context () /* dc */,
615 create_target_context (true) /* tc */,
616 NULL_RTX /* last_scheduled_insn */,
617 NULL, /* executing_insns */
618 XCNEWVEC (int, ready_ticks_size), /* ready_ticks */
620 NULL_RTX /* sched_next */,
621 1 /* cycle */, 0 /* cycle_issued_insns */,
622 issue_rate, /* issue_more */
623 1 /* starts_cycle_p */, 0 /* after_stall_p */);
627 /* Merges two fences (filling fields of fence F with resulting values) by
628 following rules: 1) state, target context and last scheduled insn are
629 propagated from fallthrough edge if it is available;
630 2) deps context and cycle is propagated from more probable edge;
631 3) all other fields are set to corresponding constant values.
633 INSN, STATE, DC, TC, LAST_SCHEDULED_INSN, EXECUTING_INSNS,
634 READY_TICKS, READY_TICKS_SIZE, SCHED_NEXT, CYCLE, ISSUE_MORE
635 and AFTER_STALL_P are the corresponding fields of the second fence. */
637 merge_fences (fence_t f, insn_t insn,
638 state_t state, deps_t dc, void *tc,
639 rtx last_scheduled_insn, VEC(rtx, gc) *executing_insns,
640 int *ready_ticks, int ready_ticks_size,
641 rtx sched_next, int cycle, int issue_more, bool after_stall_p)
643 insn_t last_scheduled_insn_old = FENCE_LAST_SCHEDULED_INSN (f);
645 gcc_assert (sel_bb_head_p (FENCE_INSN (f))
646 && !sched_next && !FENCE_SCHED_NEXT (f));
648 /* Check if we can decide which path fences came.
649 If we can't (or don't want to) - reset all. */
650 if (last_scheduled_insn == NULL
651 || last_scheduled_insn_old == NULL
652 /* This is a case when INSN is reachable on several paths from
653 one insn (this can happen when pipelining of outer loops is on and
654 there are two edges: one going around of inner loop and the other -
655 right through it; in such case just reset everything). */
656 || last_scheduled_insn == last_scheduled_insn_old)
658 state_reset (FENCE_STATE (f));
661 reset_deps_context (FENCE_DC (f));
662 delete_deps_context (dc);
664 reset_target_context (FENCE_TC (f), true);
665 delete_target_context (tc);
667 if (cycle > FENCE_CYCLE (f))
668 FENCE_CYCLE (f) = cycle;
670 FENCE_LAST_SCHEDULED_INSN (f) = NULL;
671 FENCE_ISSUE_MORE (f) = issue_rate;
672 VEC_free (rtx, gc, executing_insns);
674 if (FENCE_EXECUTING_INSNS (f))
675 VEC_block_remove (rtx, FENCE_EXECUTING_INSNS (f), 0,
676 VEC_length (rtx, FENCE_EXECUTING_INSNS (f)));
677 if (FENCE_READY_TICKS (f))
678 memset (FENCE_READY_TICKS (f), 0, FENCE_READY_TICKS_SIZE (f));
682 edge edge_old = NULL, edge_new = NULL;
687 /* Find fallthrough edge. */
688 gcc_assert (BLOCK_FOR_INSN (insn)->prev_bb);
689 candidate = find_fallthru_edge (BLOCK_FOR_INSN (insn)->prev_bb);
692 || (candidate->src != BLOCK_FOR_INSN (last_scheduled_insn)
693 && candidate->src != BLOCK_FOR_INSN (last_scheduled_insn_old)))
695 /* No fallthrough edge leading to basic block of INSN. */
696 state_reset (FENCE_STATE (f));
699 reset_target_context (FENCE_TC (f), true);
700 delete_target_context (tc);
702 FENCE_LAST_SCHEDULED_INSN (f) = NULL;
703 FENCE_ISSUE_MORE (f) = issue_rate;
706 if (candidate->src == BLOCK_FOR_INSN (last_scheduled_insn))
708 /* Would be weird if same insn is successor of several fallthrough
710 gcc_assert (BLOCK_FOR_INSN (insn)->prev_bb
711 != BLOCK_FOR_INSN (last_scheduled_insn_old));
713 state_free (FENCE_STATE (f));
714 FENCE_STATE (f) = state;
716 delete_target_context (FENCE_TC (f));
719 FENCE_LAST_SCHEDULED_INSN (f) = last_scheduled_insn;
720 FENCE_ISSUE_MORE (f) = issue_more;
724 /* Leave STATE, TC and LAST_SCHEDULED_INSN fields untouched. */
726 delete_target_context (tc);
728 gcc_assert (BLOCK_FOR_INSN (insn)->prev_bb
729 != BLOCK_FOR_INSN (last_scheduled_insn));
732 /* Find edge of first predecessor (last_scheduled_insn_old->insn). */
733 FOR_EACH_SUCC_1 (succ, si, last_scheduled_insn_old,
734 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
738 /* No same successor allowed from several edges. */
739 gcc_assert (!edge_old);
743 /* Find edge of second predecessor (last_scheduled_insn->insn). */
744 FOR_EACH_SUCC_1 (succ, si, last_scheduled_insn,
745 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
749 /* No same successor allowed from several edges. */
750 gcc_assert (!edge_new);
755 /* Check if we can choose most probable predecessor. */
756 if (edge_old == NULL || edge_new == NULL)
758 reset_deps_context (FENCE_DC (f));
759 delete_deps_context (dc);
760 VEC_free (rtx, gc, executing_insns);
763 FENCE_CYCLE (f) = MAX (FENCE_CYCLE (f), cycle);
764 if (FENCE_EXECUTING_INSNS (f))
765 VEC_block_remove (rtx, FENCE_EXECUTING_INSNS (f), 0,
766 VEC_length (rtx, FENCE_EXECUTING_INSNS (f)));
767 if (FENCE_READY_TICKS (f))
768 memset (FENCE_READY_TICKS (f), 0, FENCE_READY_TICKS_SIZE (f));
771 if (edge_new->probability > edge_old->probability)
773 delete_deps_context (FENCE_DC (f));
775 VEC_free (rtx, gc, FENCE_EXECUTING_INSNS (f));
776 FENCE_EXECUTING_INSNS (f) = executing_insns;
777 free (FENCE_READY_TICKS (f));
778 FENCE_READY_TICKS (f) = ready_ticks;
779 FENCE_READY_TICKS_SIZE (f) = ready_ticks_size;
780 FENCE_CYCLE (f) = cycle;
784 /* Leave DC and CYCLE untouched. */
785 delete_deps_context (dc);
786 VEC_free (rtx, gc, executing_insns);
791 /* Fill remaining invariant fields. */
793 FENCE_AFTER_STALL_P (f) = 1;
795 FENCE_ISSUED_INSNS (f) = 0;
796 FENCE_STARTS_CYCLE_P (f) = 1;
797 FENCE_SCHED_NEXT (f) = NULL;
800 /* Add a new fence to NEW_FENCES list, initializing it from all
803 add_to_fences (flist_tail_t new_fences, insn_t insn,
804 state_t state, deps_t dc, void *tc, rtx last_scheduled_insn,
805 VEC(rtx, gc) *executing_insns, int *ready_ticks,
806 int ready_ticks_size, rtx sched_next, int cycle,
807 int cycle_issued_insns, int issue_rate,
808 bool starts_cycle_p, bool after_stall_p)
810 fence_t f = flist_lookup (FLIST_TAIL_HEAD (new_fences), insn);
814 flist_add (FLIST_TAIL_TAILP (new_fences), insn, state, dc, tc,
815 last_scheduled_insn, executing_insns, ready_ticks,
816 ready_ticks_size, sched_next, cycle, cycle_issued_insns,
817 issue_rate, starts_cycle_p, after_stall_p);
819 FLIST_TAIL_TAILP (new_fences)
820 = &FLIST_NEXT (*FLIST_TAIL_TAILP (new_fences));
824 merge_fences (f, insn, state, dc, tc, last_scheduled_insn,
825 executing_insns, ready_ticks, ready_ticks_size,
826 sched_next, cycle, issue_rate, after_stall_p);
830 /* Move the first fence in the OLD_FENCES list to NEW_FENCES. */
832 move_fence_to_fences (flist_t old_fences, flist_tail_t new_fences)
835 flist_t *tailp = FLIST_TAIL_TAILP (new_fences);
837 old = FLIST_FENCE (old_fences);
838 f = flist_lookup (FLIST_TAIL_HEAD (new_fences),
839 FENCE_INSN (FLIST_FENCE (old_fences)));
842 merge_fences (f, old->insn, old->state, old->dc, old->tc,
843 old->last_scheduled_insn, old->executing_insns,
844 old->ready_ticks, old->ready_ticks_size,
845 old->sched_next, old->cycle, old->issue_more,
851 FLIST_TAIL_TAILP (new_fences) = &FLIST_NEXT (*tailp);
852 *FLIST_FENCE (*tailp) = *old;
853 init_fence_for_scheduling (FLIST_FENCE (*tailp));
855 FENCE_INSN (old) = NULL;
858 /* Add a new fence to NEW_FENCES list and initialize most of its data
861 add_clean_fence_to_fences (flist_tail_t new_fences, insn_t succ, fence_t fence)
863 int ready_ticks_size = get_max_uid () + 1;
865 add_to_fences (new_fences,
866 succ, state_create (), create_deps_context (),
867 create_target_context (true),
869 XCNEWVEC (int, ready_ticks_size), ready_ticks_size,
870 NULL_RTX, FENCE_CYCLE (fence) + 1,
871 0, issue_rate, 1, FENCE_AFTER_STALL_P (fence));
874 /* Add a new fence to NEW_FENCES list and initialize all of its data
875 from FENCE and SUCC. */
877 add_dirty_fence_to_fences (flist_tail_t new_fences, insn_t succ, fence_t fence)
879 int * new_ready_ticks
880 = XNEWVEC (int, FENCE_READY_TICKS_SIZE (fence));
882 memcpy (new_ready_ticks, FENCE_READY_TICKS (fence),
883 FENCE_READY_TICKS_SIZE (fence) * sizeof (int));
884 add_to_fences (new_fences,
885 succ, state_create_copy (FENCE_STATE (fence)),
886 create_copy_of_deps_context (FENCE_DC (fence)),
887 create_copy_of_target_context (FENCE_TC (fence)),
888 FENCE_LAST_SCHEDULED_INSN (fence),
889 VEC_copy (rtx, gc, FENCE_EXECUTING_INSNS (fence)),
891 FENCE_READY_TICKS_SIZE (fence),
892 FENCE_SCHED_NEXT (fence),
894 FENCE_ISSUED_INSNS (fence),
895 FENCE_ISSUE_MORE (fence),
896 FENCE_STARTS_CYCLE_P (fence),
897 FENCE_AFTER_STALL_P (fence));
901 /* Functions to work with regset and nop pools. */
903 /* Returns the new regset from pool. It might have some of the bits set
904 from the previous usage. */
906 get_regset_from_pool (void)
910 if (regset_pool.n != 0)
911 rs = regset_pool.v[--regset_pool.n];
913 /* We need to create the regset. */
915 rs = ALLOC_REG_SET (®_obstack);
917 if (regset_pool.nn == regset_pool.ss)
918 regset_pool.vv = XRESIZEVEC (regset, regset_pool.vv,
919 (regset_pool.ss = 2 * regset_pool.ss + 1));
920 regset_pool.vv[regset_pool.nn++] = rs;
928 /* Same as above, but returns the empty regset. */
930 get_clear_regset_from_pool (void)
932 regset rs = get_regset_from_pool ();
938 /* Return regset RS to the pool for future use. */
940 return_regset_to_pool (regset rs)
944 if (regset_pool.n == regset_pool.s)
945 regset_pool.v = XRESIZEVEC (regset, regset_pool.v,
946 (regset_pool.s = 2 * regset_pool.s + 1));
947 regset_pool.v[regset_pool.n++] = rs;
950 #ifdef ENABLE_CHECKING
951 /* This is used as a qsort callback for sorting regset pool stacks.
952 X and XX are addresses of two regsets. They are never equal. */
954 cmp_v_in_regset_pool (const void *x, const void *xx)
956 return *((const regset *) x) - *((const regset *) xx);
960 /* Free the regset pool possibly checking for memory leaks. */
962 free_regset_pool (void)
964 #ifdef ENABLE_CHECKING
966 regset *v = regset_pool.v;
968 int n = regset_pool.n;
970 regset *vv = regset_pool.vv;
972 int nn = regset_pool.nn;
976 gcc_assert (n <= nn);
978 /* Sort both vectors so it will be possible to compare them. */
979 qsort (v, n, sizeof (*v), cmp_v_in_regset_pool);
980 qsort (vv, nn, sizeof (*vv), cmp_v_in_regset_pool);
987 /* VV[II] was lost. */
993 gcc_assert (diff == regset_pool.diff);
997 /* If not true - we have a memory leak. */
998 gcc_assert (regset_pool.diff == 0);
1000 while (regset_pool.n)
1003 FREE_REG_SET (regset_pool.v[regset_pool.n]);
1006 free (regset_pool.v);
1007 regset_pool.v = NULL;
1010 free (regset_pool.vv);
1011 regset_pool.vv = NULL;
1015 regset_pool.diff = 0;
1019 /* Functions to work with nop pools. NOP insns are used as temporary
1020 placeholders of the insns being scheduled to allow correct update of
1021 the data sets. When update is finished, NOPs are deleted. */
1023 /* A vinsn that is used to represent a nop. This vinsn is shared among all
1024 nops sel-sched generates. */
1025 static vinsn_t nop_vinsn = NULL;
1027 /* Emit a nop before INSN, taking it from pool. */
1029 get_nop_from_pool (insn_t insn)
1032 bool old_p = nop_pool.n != 0;
1036 nop = nop_pool.v[--nop_pool.n];
1040 nop = emit_insn_before (nop, insn);
1043 flags = INSN_INIT_TODO_SSID;
1045 flags = INSN_INIT_TODO_LUID | INSN_INIT_TODO_SSID;
1047 set_insn_init (INSN_EXPR (insn), nop_vinsn, INSN_SEQNO (insn));
1048 sel_init_new_insn (nop, flags);
1053 /* Remove NOP from the instruction stream and return it to the pool. */
1055 return_nop_to_pool (insn_t nop)
1057 gcc_assert (INSN_IN_STREAM_P (nop));
1058 sel_remove_insn (nop, false, true);
1060 if (nop_pool.n == nop_pool.s)
1061 nop_pool.v = XRESIZEVEC (rtx, nop_pool.v,
1062 (nop_pool.s = 2 * nop_pool.s + 1));
1063 nop_pool.v[nop_pool.n++] = nop;
1066 /* Free the nop pool. */
1068 free_nop_pool (void)
1077 /* Skip unspec to support ia64 speculation. Called from rtx_equal_p_cb.
1078 The callback is given two rtxes XX and YY and writes the new rtxes
1079 to NX and NY in case some needs to be skipped. */
1081 skip_unspecs_callback (const_rtx *xx, const_rtx *yy, rtx *nx, rtx* ny)
1086 if (GET_CODE (x) == UNSPEC
1087 && (targetm.sched.skip_rtx_p == NULL
1088 || targetm.sched.skip_rtx_p (x)))
1090 *nx = XVECEXP (x, 0, 0);
1091 *ny = CONST_CAST_RTX (y);
1095 if (GET_CODE (y) == UNSPEC
1096 && (targetm.sched.skip_rtx_p == NULL
1097 || targetm.sched.skip_rtx_p (y)))
1099 *nx = CONST_CAST_RTX (x);
1100 *ny = XVECEXP (y, 0, 0);
1107 /* Callback, called from hash_rtx_cb. Helps to hash UNSPEC rtx X in a correct way
1108 to support ia64 speculation. When changes are needed, new rtx X and new mode
1109 NMODE are written, and the callback returns true. */
1111 hash_with_unspec_callback (const_rtx x, enum machine_mode mode ATTRIBUTE_UNUSED,
1112 rtx *nx, enum machine_mode* nmode)
1114 if (GET_CODE (x) == UNSPEC
1115 && targetm.sched.skip_rtx_p
1116 && targetm.sched.skip_rtx_p (x))
1118 *nx = XVECEXP (x, 0 ,0);
1126 /* Returns LHS and RHS are ok to be scheduled separately. */
1128 lhs_and_rhs_separable_p (rtx lhs, rtx rhs)
1130 if (lhs == NULL || rhs == NULL)
1133 /* Do not schedule CONST, CONST_INT and CONST_DOUBLE etc as rhs: no point
1134 to use reg, if const can be used. Moreover, scheduling const as rhs may
1135 lead to mode mismatch cause consts don't have modes but they could be
1136 merged from branches where the same const used in different modes. */
1137 if (CONSTANT_P (rhs))
1140 /* ??? Do not rename predicate registers to avoid ICEs in bundling. */
1141 if (COMPARISON_P (rhs))
1144 /* Do not allow single REG to be an rhs. */
1148 /* See comment at find_used_regs_1 (*1) for explanation of this
1150 /* FIXME: remove this later. */
1154 /* This will filter all tricky things like ZERO_EXTRACT etc.
1155 For now we don't handle it. */
1156 if (!REG_P (lhs) && !MEM_P (lhs))
1162 /* Initialize vinsn VI for INSN. Only for use from vinsn_create (). When
1163 FORCE_UNIQUE_P is true, the resulting vinsn will not be clonable. This is
1164 used e.g. for insns from recovery blocks. */
1166 vinsn_init (vinsn_t vi, insn_t insn, bool force_unique_p)
1168 hash_rtx_callback_function hrcf;
1171 VINSN_INSN_RTX (vi) = insn;
1172 VINSN_COUNT (vi) = 0;
1175 if (DF_INSN_UID_SAFE_GET (INSN_UID (insn)) != NULL)
1176 init_id_from_df (VINSN_ID (vi), insn, force_unique_p);
1178 deps_init_id (VINSN_ID (vi), insn, force_unique_p);
1180 /* Hash vinsn depending on whether it is separable or not. */
1181 hrcf = targetm.sched.skip_rtx_p ? hash_with_unspec_callback : NULL;
1182 if (VINSN_SEPARABLE_P (vi))
1184 rtx rhs = VINSN_RHS (vi);
1186 VINSN_HASH (vi) = hash_rtx_cb (rhs, GET_MODE (rhs),
1187 NULL, NULL, false, hrcf);
1188 VINSN_HASH_RTX (vi) = hash_rtx_cb (VINSN_PATTERN (vi),
1189 VOIDmode, NULL, NULL,
1194 VINSN_HASH (vi) = hash_rtx_cb (VINSN_PATTERN (vi), VOIDmode,
1195 NULL, NULL, false, hrcf);
1196 VINSN_HASH_RTX (vi) = VINSN_HASH (vi);
1199 insn_class = haifa_classify_insn (insn);
1201 && (!targetm.sched.get_insn_spec_ds
1202 || ((targetm.sched.get_insn_spec_ds (insn) & BEGIN_CONTROL)
1204 VINSN_MAY_TRAP_P (vi) = true;
1206 VINSN_MAY_TRAP_P (vi) = false;
1209 /* Indicate that VI has become the part of an rtx object. */
1211 vinsn_attach (vinsn_t vi)
1213 /* Assert that VI is not pending for deletion. */
1214 gcc_assert (VINSN_INSN_RTX (vi));
1219 /* Create and init VI from the INSN. Use UNIQUE_P for determining the correct
1222 vinsn_create (insn_t insn, bool force_unique_p)
1224 vinsn_t vi = XCNEW (struct vinsn_def);
1226 vinsn_init (vi, insn, force_unique_p);
1230 /* Return a copy of VI. When REATTACH_P is true, detach VI and attach
1233 vinsn_copy (vinsn_t vi, bool reattach_p)
1236 bool unique = VINSN_UNIQUE_P (vi);
1239 copy = create_copy_of_insn_rtx (VINSN_INSN_RTX (vi));
1240 new_vi = create_vinsn_from_insn_rtx (copy, unique);
1244 vinsn_attach (new_vi);
1250 /* Delete the VI vinsn and free its data. */
1252 vinsn_delete (vinsn_t vi)
1254 gcc_assert (VINSN_COUNT (vi) == 0);
1256 return_regset_to_pool (VINSN_REG_SETS (vi));
1257 return_regset_to_pool (VINSN_REG_USES (vi));
1258 return_regset_to_pool (VINSN_REG_CLOBBERS (vi));
1263 /* Indicate that VI is no longer a part of some rtx object.
1264 Remove VI if it is no longer needed. */
1266 vinsn_detach (vinsn_t vi)
1268 gcc_assert (VINSN_COUNT (vi) > 0);
1270 if (--VINSN_COUNT (vi) == 0)
1274 /* Returns TRUE if VI is a branch. */
1276 vinsn_cond_branch_p (vinsn_t vi)
1280 if (!VINSN_UNIQUE_P (vi))
1283 insn = VINSN_INSN_RTX (vi);
1284 if (BB_END (BLOCK_FOR_INSN (insn)) != insn)
1287 return control_flow_insn_p (insn);
1290 /* Return latency of INSN. */
1292 sel_insn_rtx_cost (rtx insn)
1296 /* A USE insn, or something else we don't need to
1297 understand. We can't pass these directly to
1298 result_ready_cost or insn_default_latency because it will
1299 trigger a fatal error for unrecognizable insns. */
1300 if (recog_memoized (insn) < 0)
1304 cost = insn_default_latency (insn);
1313 /* Return the cost of the VI.
1314 !!! FIXME: Unify with haifa-sched.c: insn_cost (). */
1316 sel_vinsn_cost (vinsn_t vi)
1318 int cost = vi->cost;
1322 cost = sel_insn_rtx_cost (VINSN_INSN_RTX (vi));
1330 /* Functions for insn emitting. */
1332 /* Emit new insn after AFTER based on PATTERN and initialize its data from
1335 sel_gen_insn_from_rtx_after (rtx pattern, expr_t expr, int seqno, insn_t after)
1339 gcc_assert (EXPR_TARGET_AVAILABLE (expr) == true);
1341 new_insn = emit_insn_after (pattern, after);
1342 set_insn_init (expr, NULL, seqno);
1343 sel_init_new_insn (new_insn, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SSID);
1348 /* Force newly generated vinsns to be unique. */
1349 static bool init_insn_force_unique_p = false;
1351 /* Emit new speculation recovery insn after AFTER based on PATTERN and
1352 initialize its data from EXPR and SEQNO. */
1354 sel_gen_recovery_insn_from_rtx_after (rtx pattern, expr_t expr, int seqno,
1359 gcc_assert (!init_insn_force_unique_p);
1361 init_insn_force_unique_p = true;
1362 insn = sel_gen_insn_from_rtx_after (pattern, expr, seqno, after);
1363 CANT_MOVE (insn) = 1;
1364 init_insn_force_unique_p = false;
1369 /* Emit new insn after AFTER based on EXPR and SEQNO. If VINSN is not NULL,
1370 take it as a new vinsn instead of EXPR's vinsn.
1371 We simplify insns later, after scheduling region in
1372 simplify_changed_insns. */
1374 sel_gen_insn_from_expr_after (expr_t expr, vinsn_t vinsn, int seqno,
1381 emit_expr = set_insn_init (expr, vinsn ? vinsn : EXPR_VINSN (expr),
1383 insn = EXPR_INSN_RTX (emit_expr);
1384 add_insn_after (insn, after, BLOCK_FOR_INSN (insn));
1386 flags = INSN_INIT_TODO_SSID;
1387 if (INSN_LUID (insn) == 0)
1388 flags |= INSN_INIT_TODO_LUID;
1389 sel_init_new_insn (insn, flags);
1394 /* Move insn from EXPR after AFTER. */
1396 sel_move_insn (expr_t expr, int seqno, insn_t after)
1398 insn_t insn = EXPR_INSN_RTX (expr);
1399 basic_block bb = BLOCK_FOR_INSN (after);
1400 insn_t next = NEXT_INSN (after);
1402 /* Assert that in move_op we disconnected this insn properly. */
1403 gcc_assert (EXPR_VINSN (INSN_EXPR (insn)) != NULL);
1404 PREV_INSN (insn) = after;
1405 NEXT_INSN (insn) = next;
1407 NEXT_INSN (after) = insn;
1408 PREV_INSN (next) = insn;
1410 /* Update links from insn to bb and vice versa. */
1411 df_insn_change_bb (insn, bb);
1412 if (BB_END (bb) == after)
1415 prepare_insn_expr (insn, seqno);
1420 /* Functions to work with right-hand sides. */
1422 /* Search for a hash value determined by UID/NEW_VINSN in a sorted vector
1423 VECT and return true when found. Use NEW_VINSN for comparison only when
1424 COMPARE_VINSNS is true. Write to INDP the index on which
1425 the search has stopped, such that inserting the new element at INDP will
1426 retain VECT's sort order. */
1428 find_in_history_vect_1 (VEC(expr_history_def, heap) *vect,
1429 unsigned uid, vinsn_t new_vinsn,
1430 bool compare_vinsns, int *indp)
1432 expr_history_def *arr;
1433 int i, j, len = VEC_length (expr_history_def, vect);
1441 arr = VEC_address (expr_history_def, vect);
1446 unsigned auid = arr[i].uid;
1447 vinsn_t avinsn = arr[i].new_expr_vinsn;
1450 /* When undoing transformation on a bookkeeping copy, the new vinsn
1451 may not be exactly equal to the one that is saved in the vector.
1452 This is because the insn whose copy we're checking was possibly
1453 substituted itself. */
1454 && (! compare_vinsns
1455 || vinsn_equal_p (avinsn, new_vinsn)))
1460 else if (auid > uid)
1469 /* Search for a uid of INSN and NEW_VINSN in a sorted vector VECT. Return
1470 the position found or -1, if no such value is in vector.
1471 Search also for UIDs of insn's originators, if ORIGINATORS_P is true. */
1473 find_in_history_vect (VEC(expr_history_def, heap) *vect, rtx insn,
1474 vinsn_t new_vinsn, bool originators_p)
1478 if (find_in_history_vect_1 (vect, INSN_UID (insn), new_vinsn,
1482 if (INSN_ORIGINATORS (insn) && originators_p)
1487 EXECUTE_IF_SET_IN_BITMAP (INSN_ORIGINATORS (insn), 0, uid, bi)
1488 if (find_in_history_vect_1 (vect, uid, new_vinsn, false, &ind))
1495 /* Insert new element in a sorted history vector pointed to by PVECT,
1496 if it is not there already. The element is searched using
1497 UID/NEW_EXPR_VINSN pair. TYPE, OLD_EXPR_VINSN and SPEC_DS save
1498 the history of a transformation. */
1500 insert_in_history_vect (VEC (expr_history_def, heap) **pvect,
1501 unsigned uid, enum local_trans_type type,
1502 vinsn_t old_expr_vinsn, vinsn_t new_expr_vinsn,
1505 VEC(expr_history_def, heap) *vect = *pvect;
1506 expr_history_def temp;
1510 res = find_in_history_vect_1 (vect, uid, new_expr_vinsn, true, &ind);
1514 expr_history_def *phist = VEC_index (expr_history_def, vect, ind);
1516 /* It is possible that speculation types of expressions that were
1517 propagated through different paths will be different here. In this
1518 case, merge the status to get the correct check later. */
1519 if (phist->spec_ds != spec_ds)
1520 phist->spec_ds = ds_max_merge (phist->spec_ds, spec_ds);
1525 temp.old_expr_vinsn = old_expr_vinsn;
1526 temp.new_expr_vinsn = new_expr_vinsn;
1527 temp.spec_ds = spec_ds;
1530 vinsn_attach (old_expr_vinsn);
1531 vinsn_attach (new_expr_vinsn);
1532 VEC_safe_insert (expr_history_def, heap, vect, ind, &temp);
1536 /* Free history vector PVECT. */
1538 free_history_vect (VEC (expr_history_def, heap) **pvect)
1541 expr_history_def *phist;
1547 VEC_iterate (expr_history_def, *pvect, i, phist);
1550 vinsn_detach (phist->old_expr_vinsn);
1551 vinsn_detach (phist->new_expr_vinsn);
1554 VEC_free (expr_history_def, heap, *pvect);
1559 /* Compare two vinsns as rhses if possible and as vinsns otherwise. */
1561 vinsn_equal_p (vinsn_t x, vinsn_t y)
1563 rtx_equal_p_callback_function repcf;
1568 if (VINSN_TYPE (x) != VINSN_TYPE (y))
1571 if (VINSN_HASH (x) != VINSN_HASH (y))
1574 repcf = targetm.sched.skip_rtx_p ? skip_unspecs_callback : NULL;
1575 if (VINSN_SEPARABLE_P (x))
1577 /* Compare RHSes of VINSNs. */
1578 gcc_assert (VINSN_RHS (x));
1579 gcc_assert (VINSN_RHS (y));
1581 return rtx_equal_p_cb (VINSN_RHS (x), VINSN_RHS (y), repcf);
1584 return rtx_equal_p_cb (VINSN_PATTERN (x), VINSN_PATTERN (y), repcf);
1588 /* Functions for working with expressions. */
1590 /* Initialize EXPR. */
1592 init_expr (expr_t expr, vinsn_t vi, int spec, int use, int priority,
1593 int sched_times, int orig_bb_index, ds_t spec_done_ds,
1594 ds_t spec_to_check_ds, int orig_sched_cycle,
1595 VEC(expr_history_def, heap) *history, bool target_available,
1596 bool was_substituted, bool was_renamed, bool needs_spec_check_p,
1601 EXPR_VINSN (expr) = vi;
1602 EXPR_SPEC (expr) = spec;
1603 EXPR_USEFULNESS (expr) = use;
1604 EXPR_PRIORITY (expr) = priority;
1605 EXPR_PRIORITY_ADJ (expr) = 0;
1606 EXPR_SCHED_TIMES (expr) = sched_times;
1607 EXPR_ORIG_BB_INDEX (expr) = orig_bb_index;
1608 EXPR_ORIG_SCHED_CYCLE (expr) = orig_sched_cycle;
1609 EXPR_SPEC_DONE_DS (expr) = spec_done_ds;
1610 EXPR_SPEC_TO_CHECK_DS (expr) = spec_to_check_ds;
1613 EXPR_HISTORY_OF_CHANGES (expr) = history;
1615 EXPR_HISTORY_OF_CHANGES (expr) = NULL;
1617 EXPR_TARGET_AVAILABLE (expr) = target_available;
1618 EXPR_WAS_SUBSTITUTED (expr) = was_substituted;
1619 EXPR_WAS_RENAMED (expr) = was_renamed;
1620 EXPR_NEEDS_SPEC_CHECK_P (expr) = needs_spec_check_p;
1621 EXPR_CANT_MOVE (expr) = cant_move;
1624 /* Make a copy of the expr FROM into the expr TO. */
1626 copy_expr (expr_t to, expr_t from)
1628 VEC(expr_history_def, heap) *temp = NULL;
1630 if (EXPR_HISTORY_OF_CHANGES (from))
1633 expr_history_def *phist;
1635 temp = VEC_copy (expr_history_def, heap, EXPR_HISTORY_OF_CHANGES (from));
1637 VEC_iterate (expr_history_def, temp, i, phist);
1640 vinsn_attach (phist->old_expr_vinsn);
1641 vinsn_attach (phist->new_expr_vinsn);
1645 init_expr (to, EXPR_VINSN (from), EXPR_SPEC (from),
1646 EXPR_USEFULNESS (from), EXPR_PRIORITY (from),
1647 EXPR_SCHED_TIMES (from), EXPR_ORIG_BB_INDEX (from),
1648 EXPR_SPEC_DONE_DS (from), EXPR_SPEC_TO_CHECK_DS (from),
1649 EXPR_ORIG_SCHED_CYCLE (from), temp,
1650 EXPR_TARGET_AVAILABLE (from), EXPR_WAS_SUBSTITUTED (from),
1651 EXPR_WAS_RENAMED (from), EXPR_NEEDS_SPEC_CHECK_P (from),
1652 EXPR_CANT_MOVE (from));
1655 /* Same, but the final expr will not ever be in av sets, so don't copy
1656 "uninteresting" data such as bitmap cache. */
1658 copy_expr_onside (expr_t to, expr_t from)
1660 init_expr (to, EXPR_VINSN (from), EXPR_SPEC (from), EXPR_USEFULNESS (from),
1661 EXPR_PRIORITY (from), EXPR_SCHED_TIMES (from), 0,
1662 EXPR_SPEC_DONE_DS (from), EXPR_SPEC_TO_CHECK_DS (from), 0, NULL,
1663 EXPR_TARGET_AVAILABLE (from), EXPR_WAS_SUBSTITUTED (from),
1664 EXPR_WAS_RENAMED (from), EXPR_NEEDS_SPEC_CHECK_P (from),
1665 EXPR_CANT_MOVE (from));
1668 /* Prepare the expr of INSN for scheduling. Used when moving insn and when
1669 initializing new insns. */
1671 prepare_insn_expr (insn_t insn, int seqno)
1673 expr_t expr = INSN_EXPR (insn);
1676 INSN_SEQNO (insn) = seqno;
1677 EXPR_ORIG_BB_INDEX (expr) = BLOCK_NUM (insn);
1678 EXPR_SPEC (expr) = 0;
1679 EXPR_ORIG_SCHED_CYCLE (expr) = 0;
1680 EXPR_WAS_SUBSTITUTED (expr) = 0;
1681 EXPR_WAS_RENAMED (expr) = 0;
1682 EXPR_TARGET_AVAILABLE (expr) = 1;
1683 INSN_LIVE_VALID_P (insn) = false;
1685 /* ??? If this expression is speculative, make its dependence
1686 as weak as possible. We can filter this expression later
1687 in process_spec_exprs, because we do not distinguish
1688 between the status we got during compute_av_set and the
1689 existing status. To be fixed. */
1690 ds = EXPR_SPEC_DONE_DS (expr);
1692 EXPR_SPEC_DONE_DS (expr) = ds_get_max_dep_weak (ds);
1694 free_history_vect (&EXPR_HISTORY_OF_CHANGES (expr));
1697 /* Update target_available bits when merging exprs TO and FROM. SPLIT_POINT
1698 is non-null when expressions are merged from different successors at
1701 update_target_availability (expr_t to, expr_t from, insn_t split_point)
1703 if (EXPR_TARGET_AVAILABLE (to) < 0
1704 || EXPR_TARGET_AVAILABLE (from) < 0)
1705 EXPR_TARGET_AVAILABLE (to) = -1;
1708 /* We try to detect the case when one of the expressions
1709 can only be reached through another one. In this case,
1710 we can do better. */
1711 if (split_point == NULL)
1715 toind = EXPR_ORIG_BB_INDEX (to);
1716 fromind = EXPR_ORIG_BB_INDEX (from);
1718 if (toind && toind == fromind)
1719 /* Do nothing -- everything is done in
1720 merge_with_other_exprs. */
1723 EXPR_TARGET_AVAILABLE (to) = -1;
1726 EXPR_TARGET_AVAILABLE (to) &= EXPR_TARGET_AVAILABLE (from);
1730 /* Update speculation bits when merging exprs TO and FROM. SPLIT_POINT
1731 is non-null when expressions are merged from different successors at
1734 update_speculative_bits (expr_t to, expr_t from, insn_t split_point)
1736 ds_t old_to_ds, old_from_ds;
1738 old_to_ds = EXPR_SPEC_DONE_DS (to);
1739 old_from_ds = EXPR_SPEC_DONE_DS (from);
1741 EXPR_SPEC_DONE_DS (to) = ds_max_merge (old_to_ds, old_from_ds);
1742 EXPR_SPEC_TO_CHECK_DS (to) |= EXPR_SPEC_TO_CHECK_DS (from);
1743 EXPR_NEEDS_SPEC_CHECK_P (to) |= EXPR_NEEDS_SPEC_CHECK_P (from);
1745 /* When merging e.g. control & data speculative exprs, or a control
1746 speculative with a control&data speculative one, we really have
1747 to change vinsn too. Also, when speculative status is changed,
1748 we also need to record this as a transformation in expr's history. */
1749 if ((old_to_ds & SPECULATIVE) || (old_from_ds & SPECULATIVE))
1751 old_to_ds = ds_get_speculation_types (old_to_ds);
1752 old_from_ds = ds_get_speculation_types (old_from_ds);
1754 if (old_to_ds != old_from_ds)
1758 /* When both expressions are speculative, we need to change
1760 if ((old_to_ds & SPECULATIVE) && (old_from_ds & SPECULATIVE))
1764 res = speculate_expr (to, EXPR_SPEC_DONE_DS (to));
1765 gcc_assert (res >= 0);
1768 if (split_point != NULL)
1770 /* Record the change with proper status. */
1771 record_ds = EXPR_SPEC_DONE_DS (to) & SPECULATIVE;
1772 record_ds &= ~(old_to_ds & SPECULATIVE);
1773 record_ds &= ~(old_from_ds & SPECULATIVE);
1775 insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (to),
1776 INSN_UID (split_point), TRANS_SPECULATION,
1777 EXPR_VINSN (from), EXPR_VINSN (to),
1785 /* Merge bits of FROM expr to TO expr. When SPLIT_POINT is not NULL,
1786 this is done along different paths. */
1788 merge_expr_data (expr_t to, expr_t from, insn_t split_point)
1791 expr_history_def *phist;
1793 /* For now, we just set the spec of resulting expr to be minimum of the specs
1795 if (EXPR_SPEC (to) > EXPR_SPEC (from))
1796 EXPR_SPEC (to) = EXPR_SPEC (from);
1799 EXPR_USEFULNESS (to) += EXPR_USEFULNESS (from);
1801 EXPR_USEFULNESS (to) = MAX (EXPR_USEFULNESS (to),
1802 EXPR_USEFULNESS (from));
1804 if (EXPR_PRIORITY (to) < EXPR_PRIORITY (from))
1805 EXPR_PRIORITY (to) = EXPR_PRIORITY (from);
1807 if (EXPR_SCHED_TIMES (to) > EXPR_SCHED_TIMES (from))
1808 EXPR_SCHED_TIMES (to) = EXPR_SCHED_TIMES (from);
1810 if (EXPR_ORIG_BB_INDEX (to) != EXPR_ORIG_BB_INDEX (from))
1811 EXPR_ORIG_BB_INDEX (to) = 0;
1813 EXPR_ORIG_SCHED_CYCLE (to) = MIN (EXPR_ORIG_SCHED_CYCLE (to),
1814 EXPR_ORIG_SCHED_CYCLE (from));
1816 /* We keep this vector sorted. */
1818 VEC_iterate (expr_history_def, EXPR_HISTORY_OF_CHANGES (from),
1821 insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (to),
1822 phist->uid, phist->type,
1823 phist->old_expr_vinsn, phist->new_expr_vinsn,
1826 EXPR_WAS_SUBSTITUTED (to) |= EXPR_WAS_SUBSTITUTED (from);
1827 EXPR_WAS_RENAMED (to) |= EXPR_WAS_RENAMED (from);
1828 EXPR_CANT_MOVE (to) |= EXPR_CANT_MOVE (from);
1830 update_target_availability (to, from, split_point);
1831 update_speculative_bits (to, from, split_point);
1834 /* Merge bits of FROM expr to TO expr. Vinsns in the exprs should be equal
1835 in terms of vinsn_equal_p. SPLIT_POINT is non-null when expressions
1836 are merged from different successors at a split point. */
1838 merge_expr (expr_t to, expr_t from, insn_t split_point)
1840 vinsn_t to_vi = EXPR_VINSN (to);
1841 vinsn_t from_vi = EXPR_VINSN (from);
1843 gcc_assert (vinsn_equal_p (to_vi, from_vi));
1845 /* Make sure that speculative pattern is propagated into exprs that
1846 have non-speculative one. This will provide us with consistent
1847 speculative bits and speculative patterns inside expr. */
1848 if (EXPR_SPEC_DONE_DS (to) == 0
1849 && EXPR_SPEC_DONE_DS (from) != 0)
1850 change_vinsn_in_expr (to, EXPR_VINSN (from));
1852 merge_expr_data (to, from, split_point);
1853 gcc_assert (EXPR_USEFULNESS (to) <= REG_BR_PROB_BASE);
1856 /* Clear the information of this EXPR. */
1858 clear_expr (expr_t expr)
1861 vinsn_detach (EXPR_VINSN (expr));
1862 EXPR_VINSN (expr) = NULL;
1864 free_history_vect (&EXPR_HISTORY_OF_CHANGES (expr));
1867 /* For a given LV_SET, mark EXPR having unavailable target register. */
1869 set_unavailable_target_for_expr (expr_t expr, regset lv_set)
1871 if (EXPR_SEPARABLE_P (expr))
1873 if (REG_P (EXPR_LHS (expr))
1874 && bitmap_bit_p (lv_set, REGNO (EXPR_LHS (expr))))
1876 /* If it's an insn like r1 = use (r1, ...), and it exists in
1877 different forms in each of the av_sets being merged, we can't say
1878 whether original destination register is available or not.
1879 However, this still works if destination register is not used
1880 in the original expression: if the branch at which LV_SET we're
1881 looking here is not actually 'other branch' in sense that same
1882 expression is available through it (but it can't be determined
1883 at computation stage because of transformations on one of the
1884 branches), it still won't affect the availability.
1885 Liveness of a register somewhere on a code motion path means
1886 it's either read somewhere on a codemotion path, live on
1887 'other' branch, live at the point immediately following
1888 the original operation, or is read by the original operation.
1889 The latter case is filtered out in the condition below.
1890 It still doesn't cover the case when register is defined and used
1891 somewhere within the code motion path, and in this case we could
1892 miss a unifying code motion along both branches using a renamed
1893 register, but it won't affect a code correctness since upon
1894 an actual code motion a bookkeeping code would be generated. */
1895 if (bitmap_bit_p (VINSN_REG_USES (EXPR_VINSN (expr)),
1896 REGNO (EXPR_LHS (expr))))
1897 EXPR_TARGET_AVAILABLE (expr) = -1;
1899 EXPR_TARGET_AVAILABLE (expr) = false;
1905 reg_set_iterator rsi;
1907 EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_SETS (EXPR_VINSN (expr)),
1909 if (bitmap_bit_p (lv_set, regno))
1911 EXPR_TARGET_AVAILABLE (expr) = false;
1915 EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_CLOBBERS (EXPR_VINSN (expr)),
1917 if (bitmap_bit_p (lv_set, regno))
1919 EXPR_TARGET_AVAILABLE (expr) = false;
1925 /* Try to make EXPR speculative. Return 1 when EXPR's pattern
1926 or dependence status have changed, 2 when also the target register
1927 became unavailable, 0 if nothing had to be changed. */
1929 speculate_expr (expr_t expr, ds_t ds)
1934 ds_t target_ds, current_ds;
1936 /* Obtain the status we need to put on EXPR. */
1937 target_ds = (ds & SPECULATIVE);
1938 current_ds = EXPR_SPEC_DONE_DS (expr);
1939 ds = ds_full_merge (current_ds, target_ds, NULL_RTX, NULL_RTX);
1941 orig_insn_rtx = EXPR_INSN_RTX (expr);
1943 res = sched_speculate_insn (orig_insn_rtx, ds, &spec_pat);
1948 EXPR_SPEC_DONE_DS (expr) = ds;
1949 return current_ds != ds ? 1 : 0;
1953 rtx spec_insn_rtx = create_insn_rtx_from_pattern (spec_pat, NULL_RTX);
1954 vinsn_t spec_vinsn = create_vinsn_from_insn_rtx (spec_insn_rtx, false);
1956 change_vinsn_in_expr (expr, spec_vinsn);
1957 EXPR_SPEC_DONE_DS (expr) = ds;
1958 EXPR_NEEDS_SPEC_CHECK_P (expr) = true;
1960 /* Do not allow clobbering the address register of speculative
1962 if (bitmap_bit_p (VINSN_REG_USES (EXPR_VINSN (expr)),
1963 expr_dest_regno (expr)))
1965 EXPR_TARGET_AVAILABLE (expr) = false;
1981 /* Return a destination register, if any, of EXPR. */
1983 expr_dest_reg (expr_t expr)
1985 rtx dest = VINSN_LHS (EXPR_VINSN (expr));
1987 if (dest != NULL_RTX && REG_P (dest))
1993 /* Returns the REGNO of the R's destination. */
1995 expr_dest_regno (expr_t expr)
1997 rtx dest = expr_dest_reg (expr);
1999 gcc_assert (dest != NULL_RTX);
2000 return REGNO (dest);
2003 /* For a given LV_SET, mark all expressions in JOIN_SET, but not present in
2004 AV_SET having unavailable target register. */
2006 mark_unavailable_targets (av_set_t join_set, av_set_t av_set, regset lv_set)
2009 av_set_iterator avi;
2011 FOR_EACH_EXPR (expr, avi, join_set)
2012 if (av_set_lookup (av_set, EXPR_VINSN (expr)) == NULL)
2013 set_unavailable_target_for_expr (expr, lv_set);
2017 /* Av set functions. */
2019 /* Add a new element to av set SETP.
2020 Return the element added. */
2022 av_set_add_element (av_set_t *setp)
2024 /* Insert at the beginning of the list. */
2029 /* Add EXPR to SETP. */
2031 av_set_add (av_set_t *setp, expr_t expr)
2035 gcc_assert (!INSN_NOP_P (EXPR_INSN_RTX (expr)));
2036 elem = av_set_add_element (setp);
2037 copy_expr (_AV_SET_EXPR (elem), expr);
2040 /* Same, but do not copy EXPR. */
2042 av_set_add_nocopy (av_set_t *setp, expr_t expr)
2046 elem = av_set_add_element (setp);
2047 *_AV_SET_EXPR (elem) = *expr;
2050 /* Remove expr pointed to by IP from the av_set. */
2052 av_set_iter_remove (av_set_iterator *ip)
2054 clear_expr (_AV_SET_EXPR (*ip->lp));
2055 _list_iter_remove (ip);
2058 /* Search for an expr in SET, such that it's equivalent to SOUGHT_VINSN in the
2059 sense of vinsn_equal_p function. Return NULL if no such expr is
2060 in SET was found. */
2062 av_set_lookup (av_set_t set, vinsn_t sought_vinsn)
2067 FOR_EACH_EXPR (expr, i, set)
2068 if (vinsn_equal_p (EXPR_VINSN (expr), sought_vinsn))
2073 /* Same, but also remove the EXPR found. */
2075 av_set_lookup_and_remove (av_set_t *setp, vinsn_t sought_vinsn)
2080 FOR_EACH_EXPR_1 (expr, i, setp)
2081 if (vinsn_equal_p (EXPR_VINSN (expr), sought_vinsn))
2083 _list_iter_remove_nofree (&i);
2089 /* Search for an expr in SET, such that it's equivalent to EXPR in the
2090 sense of vinsn_equal_p function of their vinsns, but not EXPR itself.
2091 Returns NULL if no such expr is in SET was found. */
2093 av_set_lookup_other_equiv_expr (av_set_t set, expr_t expr)
2098 FOR_EACH_EXPR (cur_expr, i, set)
2100 if (cur_expr == expr)
2102 if (vinsn_equal_p (EXPR_VINSN (cur_expr), EXPR_VINSN (expr)))
2109 /* If other expression is already in AVP, remove one of them. */
2111 merge_with_other_exprs (av_set_t *avp, av_set_iterator *ip, expr_t expr)
2115 expr2 = av_set_lookup_other_equiv_expr (*avp, expr);
2118 /* Reset target availability on merge, since taking it only from one
2119 of the exprs would be controversial for different code. */
2120 EXPR_TARGET_AVAILABLE (expr2) = -1;
2121 EXPR_USEFULNESS (expr2) = 0;
2123 merge_expr (expr2, expr, NULL);
2125 /* Fix usefulness as it should be now REG_BR_PROB_BASE. */
2126 EXPR_USEFULNESS (expr2) = REG_BR_PROB_BASE;
2128 av_set_iter_remove (ip);
2135 /* Return true if there is an expr that correlates to VI in SET. */
2137 av_set_is_in_p (av_set_t set, vinsn_t vi)
2139 return av_set_lookup (set, vi) != NULL;
2142 /* Return a copy of SET. */
2144 av_set_copy (av_set_t set)
2148 av_set_t res = NULL;
2150 FOR_EACH_EXPR (expr, i, set)
2151 av_set_add (&res, expr);
2156 /* Join two av sets that do not have common elements by attaching second set
2157 (pointed to by FROMP) to the end of first set (TO_TAILP must point to
2158 _AV_SET_NEXT of first set's last element). */
2160 join_distinct_sets (av_set_t *to_tailp, av_set_t *fromp)
2162 gcc_assert (*to_tailp == NULL);
2167 /* Makes set pointed to by TO to be the union of TO and FROM. Clear av_set
2168 pointed to by FROMP afterwards. */
2170 av_set_union_and_clear (av_set_t *top, av_set_t *fromp, insn_t insn)
2175 /* Delete from TOP all exprs, that present in FROMP. */
2176 FOR_EACH_EXPR_1 (expr1, i, top)
2178 expr_t expr2 = av_set_lookup (*fromp, EXPR_VINSN (expr1));
2182 merge_expr (expr2, expr1, insn);
2183 av_set_iter_remove (&i);
2187 join_distinct_sets (i.lp, fromp);
2190 /* Same as above, but also update availability of target register in
2191 TOP judging by TO_LV_SET and FROM_LV_SET. */
2193 av_set_union_and_live (av_set_t *top, av_set_t *fromp, regset to_lv_set,
2194 regset from_lv_set, insn_t insn)
2198 av_set_t *to_tailp, in_both_set = NULL;
2200 /* Delete from TOP all expres, that present in FROMP. */
2201 FOR_EACH_EXPR_1 (expr1, i, top)
2203 expr_t expr2 = av_set_lookup_and_remove (fromp, EXPR_VINSN (expr1));
2207 /* It may be that the expressions have different destination
2208 registers, in which case we need to check liveness here. */
2209 if (EXPR_SEPARABLE_P (expr1))
2211 int regno1 = (REG_P (EXPR_LHS (expr1))
2212 ? (int) expr_dest_regno (expr1) : -1);
2213 int regno2 = (REG_P (EXPR_LHS (expr2))
2214 ? (int) expr_dest_regno (expr2) : -1);
2216 /* ??? We don't have a way to check restrictions for
2217 *other* register on the current path, we did it only
2218 for the current target register. Give up. */
2219 if (regno1 != regno2)
2220 EXPR_TARGET_AVAILABLE (expr2) = -1;
2222 else if (EXPR_INSN_RTX (expr1) != EXPR_INSN_RTX (expr2))
2223 EXPR_TARGET_AVAILABLE (expr2) = -1;
2225 merge_expr (expr2, expr1, insn);
2226 av_set_add_nocopy (&in_both_set, expr2);
2227 av_set_iter_remove (&i);
2230 /* EXPR1 is present in TOP, but not in FROMP. Check it on
2232 set_unavailable_target_for_expr (expr1, from_lv_set);
2236 /* These expressions are not present in TOP. Check liveness
2237 restrictions on TO_LV_SET. */
2238 FOR_EACH_EXPR (expr1, i, *fromp)
2239 set_unavailable_target_for_expr (expr1, to_lv_set);
2241 join_distinct_sets (i.lp, &in_both_set);
2242 join_distinct_sets (to_tailp, fromp);
2245 /* Clear av_set pointed to by SETP. */
2247 av_set_clear (av_set_t *setp)
2252 FOR_EACH_EXPR_1 (expr, i, setp)
2253 av_set_iter_remove (&i);
2255 gcc_assert (*setp == NULL);
2258 /* Leave only one non-speculative element in the SETP. */
2260 av_set_leave_one_nonspec (av_set_t *setp)
2264 bool has_one_nonspec = false;
2266 /* Keep all speculative exprs, and leave one non-speculative
2268 FOR_EACH_EXPR_1 (expr, i, setp)
2270 if (!EXPR_SPEC_DONE_DS (expr))
2272 if (has_one_nonspec)
2273 av_set_iter_remove (&i);
2275 has_one_nonspec = true;
2280 /* Return the N'th element of the SET. */
2282 av_set_element (av_set_t set, int n)
2287 FOR_EACH_EXPR (expr, i, set)
2295 /* Deletes all expressions from AVP that are conditional branches (IFs). */
2297 av_set_substract_cond_branches (av_set_t *avp)
2302 FOR_EACH_EXPR_1 (expr, i, avp)
2303 if (vinsn_cond_branch_p (EXPR_VINSN (expr)))
2304 av_set_iter_remove (&i);
2307 /* Multiplies usefulness attribute of each member of av-set *AVP by
2308 value PROB / ALL_PROB. */
2310 av_set_split_usefulness (av_set_t av, int prob, int all_prob)
2315 FOR_EACH_EXPR (expr, i, av)
2316 EXPR_USEFULNESS (expr) = (all_prob
2317 ? (EXPR_USEFULNESS (expr) * prob) / all_prob
2321 /* Leave in AVP only those expressions, which are present in AV,
2324 av_set_intersect (av_set_t *avp, av_set_t av)
2329 FOR_EACH_EXPR_1 (expr, i, avp)
2330 if (av_set_lookup (av, EXPR_VINSN (expr)) == NULL)
2331 av_set_iter_remove (&i);
2336 /* Dependence hooks to initialize insn data. */
2338 /* This is used in hooks callable from dependence analysis when initializing
2339 instruction's data. */
2342 /* Where the dependence was found (lhs/rhs). */
2345 /* The actual data object to initialize. */
2348 /* True when the insn should not be made clonable. */
2349 bool force_unique_p;
2351 /* True when insn should be treated as of type USE, i.e. never renamed. */
2353 } deps_init_id_data;
2356 /* Setup ID for INSN. FORCE_UNIQUE_P is true when INSN should not be
2359 setup_id_for_insn (idata_t id, insn_t insn, bool force_unique_p)
2363 /* Determine whether INSN could be cloned and return appropriate vinsn type.
2364 That clonable insns which can be separated into lhs and rhs have type SET.
2365 Other clonable insns have type USE. */
2366 type = GET_CODE (insn);
2368 /* Only regular insns could be cloned. */
2369 if (type == INSN && !force_unique_p)
2371 else if (type == JUMP_INSN && simplejump_p (insn))
2374 IDATA_TYPE (id) = type;
2375 IDATA_REG_SETS (id) = get_clear_regset_from_pool ();
2376 IDATA_REG_USES (id) = get_clear_regset_from_pool ();
2377 IDATA_REG_CLOBBERS (id) = get_clear_regset_from_pool ();
2380 /* Start initializing insn data. */
2382 deps_init_id_start_insn (insn_t insn)
2384 gcc_assert (deps_init_id_data.where == DEPS_IN_NOWHERE);
2386 setup_id_for_insn (deps_init_id_data.id, insn,
2387 deps_init_id_data.force_unique_p);
2388 deps_init_id_data.where = DEPS_IN_INSN;
2391 /* Start initializing lhs data. */
2393 deps_init_id_start_lhs (rtx lhs)
2395 gcc_assert (deps_init_id_data.where == DEPS_IN_INSN);
2396 gcc_assert (IDATA_LHS (deps_init_id_data.id) == NULL);
2398 if (IDATA_TYPE (deps_init_id_data.id) == SET)
2400 IDATA_LHS (deps_init_id_data.id) = lhs;
2401 deps_init_id_data.where = DEPS_IN_LHS;
2405 /* Finish initializing lhs data. */
2407 deps_init_id_finish_lhs (void)
2409 deps_init_id_data.where = DEPS_IN_INSN;
2412 /* Note a set of REGNO. */
2414 deps_init_id_note_reg_set (int regno)
2416 haifa_note_reg_set (regno);
2418 if (deps_init_id_data.where == DEPS_IN_RHS)
2419 deps_init_id_data.force_use_p = true;
2421 if (IDATA_TYPE (deps_init_id_data.id) != PC)
2422 SET_REGNO_REG_SET (IDATA_REG_SETS (deps_init_id_data.id), regno);
2425 /* Make instructions that set stack registers to be ineligible for
2426 renaming to avoid issues with find_used_regs. */
2427 if (IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG))
2428 deps_init_id_data.force_use_p = true;
2432 /* Note a clobber of REGNO. */
2434 deps_init_id_note_reg_clobber (int regno)
2436 haifa_note_reg_clobber (regno);
2438 if (deps_init_id_data.where == DEPS_IN_RHS)
2439 deps_init_id_data.force_use_p = true;
2441 if (IDATA_TYPE (deps_init_id_data.id) != PC)
2442 SET_REGNO_REG_SET (IDATA_REG_CLOBBERS (deps_init_id_data.id), regno);
2445 /* Note a use of REGNO. */
2447 deps_init_id_note_reg_use (int regno)
2449 haifa_note_reg_use (regno);
2451 if (IDATA_TYPE (deps_init_id_data.id) != PC)
2452 SET_REGNO_REG_SET (IDATA_REG_USES (deps_init_id_data.id), regno);
2455 /* Start initializing rhs data. */
2457 deps_init_id_start_rhs (rtx rhs)
2459 gcc_assert (deps_init_id_data.where == DEPS_IN_INSN);
2461 /* And there was no sel_deps_reset_to_insn (). */
2462 if (IDATA_LHS (deps_init_id_data.id) != NULL)
2464 IDATA_RHS (deps_init_id_data.id) = rhs;
2465 deps_init_id_data.where = DEPS_IN_RHS;
2469 /* Finish initializing rhs data. */
2471 deps_init_id_finish_rhs (void)
2473 gcc_assert (deps_init_id_data.where == DEPS_IN_RHS
2474 || deps_init_id_data.where == DEPS_IN_INSN);
2475 deps_init_id_data.where = DEPS_IN_INSN;
2478 /* Finish initializing insn data. */
2480 deps_init_id_finish_insn (void)
2482 gcc_assert (deps_init_id_data.where == DEPS_IN_INSN);
2484 if (IDATA_TYPE (deps_init_id_data.id) == SET)
2486 rtx lhs = IDATA_LHS (deps_init_id_data.id);
2487 rtx rhs = IDATA_RHS (deps_init_id_data.id);
2489 if (lhs == NULL || rhs == NULL || !lhs_and_rhs_separable_p (lhs, rhs)
2490 || deps_init_id_data.force_use_p)
2492 /* This should be a USE, as we don't want to schedule its RHS
2493 separately. However, we still want to have them recorded
2494 for the purposes of substitution. That's why we don't
2495 simply call downgrade_to_use () here. */
2496 gcc_assert (IDATA_TYPE (deps_init_id_data.id) == SET);
2497 gcc_assert (!lhs == !rhs);
2499 IDATA_TYPE (deps_init_id_data.id) = USE;
2503 deps_init_id_data.where = DEPS_IN_NOWHERE;
2506 /* This is dependence info used for initializing insn's data. */
2507 static struct sched_deps_info_def deps_init_id_sched_deps_info;
2509 /* This initializes most of the static part of the above structure. */
2510 static const struct sched_deps_info_def const_deps_init_id_sched_deps_info =
2514 deps_init_id_start_insn,
2515 deps_init_id_finish_insn,
2516 deps_init_id_start_lhs,
2517 deps_init_id_finish_lhs,
2518 deps_init_id_start_rhs,
2519 deps_init_id_finish_rhs,
2520 deps_init_id_note_reg_set,
2521 deps_init_id_note_reg_clobber,
2522 deps_init_id_note_reg_use,
2523 NULL, /* note_mem_dep */
2524 NULL, /* note_dep */
2527 0, /* use_deps_list */
2528 0 /* generate_spec_deps */
2531 /* Initialize INSN's lhs and rhs in ID. When FORCE_UNIQUE_P is true,
2532 we don't actually need information about lhs and rhs. */
2534 setup_id_lhs_rhs (idata_t id, insn_t insn, bool force_unique_p)
2536 rtx pat = PATTERN (insn);
2538 if (GET_CODE (insn) == INSN
2539 && GET_CODE (pat) == SET
2542 IDATA_RHS (id) = SET_SRC (pat);
2543 IDATA_LHS (id) = SET_DEST (pat);
2546 IDATA_LHS (id) = IDATA_RHS (id) = NULL;
2549 /* Possibly downgrade INSN to USE. */
2551 maybe_downgrade_id_to_use (idata_t id, insn_t insn)
2553 bool must_be_use = false;
2554 unsigned uid = INSN_UID (insn);
2556 rtx lhs = IDATA_LHS (id);
2557 rtx rhs = IDATA_RHS (id);
2559 /* We downgrade only SETs. */
2560 if (IDATA_TYPE (id) != SET)
2563 if (!lhs || !lhs_and_rhs_separable_p (lhs, rhs))
2565 IDATA_TYPE (id) = USE;
2569 for (rec = DF_INSN_UID_DEFS (uid); *rec; rec++)
2573 if (DF_REF_INSN (def)
2574 && DF_REF_FLAGS_IS_SET (def, DF_REF_PRE_POST_MODIFY)
2575 && loc_mentioned_in_p (DF_REF_LOC (def), IDATA_RHS (id)))
2582 /* Make instructions that set stack registers to be ineligible for
2583 renaming to avoid issues with find_used_regs. */
2584 if (IN_RANGE (DF_REF_REGNO (def), FIRST_STACK_REG, LAST_STACK_REG))
2593 IDATA_TYPE (id) = USE;
2596 /* Setup register sets describing INSN in ID. */
2598 setup_id_reg_sets (idata_t id, insn_t insn)
2600 unsigned uid = INSN_UID (insn);
2602 regset tmp = get_clear_regset_from_pool ();
2604 for (rec = DF_INSN_UID_DEFS (uid); *rec; rec++)
2607 unsigned int regno = DF_REF_REGNO (def);
2609 /* Post modifies are treated like clobbers by sched-deps.c. */
2610 if (DF_REF_FLAGS_IS_SET (def, (DF_REF_MUST_CLOBBER
2611 | DF_REF_PRE_POST_MODIFY)))
2612 SET_REGNO_REG_SET (IDATA_REG_CLOBBERS (id), regno);
2613 else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
2615 SET_REGNO_REG_SET (IDATA_REG_SETS (id), regno);
2618 /* For stack registers, treat writes to them as writes
2619 to the first one to be consistent with sched-deps.c. */
2620 if (IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG))
2621 SET_REGNO_REG_SET (IDATA_REG_SETS (id), FIRST_STACK_REG);
2624 /* Mark special refs that generate read/write def pair. */
2625 if (DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL)
2626 || regno == STACK_POINTER_REGNUM)
2627 bitmap_set_bit (tmp, regno);
2630 for (rec = DF_INSN_UID_USES (uid); *rec; rec++)
2633 unsigned int regno = DF_REF_REGNO (use);
2635 /* When these refs are met for the first time, skip them, as
2636 these uses are just counterparts of some defs. */
2637 if (bitmap_bit_p (tmp, regno))
2638 bitmap_clear_bit (tmp, regno);
2639 else if (! DF_REF_FLAGS_IS_SET (use, DF_REF_CALL_STACK_USAGE))
2641 SET_REGNO_REG_SET (IDATA_REG_USES (id), regno);
2644 /* For stack registers, treat reads from them as reads from
2645 the first one to be consistent with sched-deps.c. */
2646 if (IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG))
2647 SET_REGNO_REG_SET (IDATA_REG_USES (id), FIRST_STACK_REG);
2652 return_regset_to_pool (tmp);
2655 /* Initialize instruction data for INSN in ID using DF's data. */
2657 init_id_from_df (idata_t id, insn_t insn, bool force_unique_p)
2659 gcc_assert (DF_INSN_UID_SAFE_GET (INSN_UID (insn)) != NULL);
2661 setup_id_for_insn (id, insn, force_unique_p);
2662 setup_id_lhs_rhs (id, insn, force_unique_p);
2664 if (INSN_NOP_P (insn))
2667 maybe_downgrade_id_to_use (id, insn);
2668 setup_id_reg_sets (id, insn);
2671 /* Initialize instruction data for INSN in ID. */
2673 deps_init_id (idata_t id, insn_t insn, bool force_unique_p)
2675 struct deps _dc, *dc = &_dc;
2677 deps_init_id_data.where = DEPS_IN_NOWHERE;
2678 deps_init_id_data.id = id;
2679 deps_init_id_data.force_unique_p = force_unique_p;
2680 deps_init_id_data.force_use_p = false;
2682 init_deps (dc, false);
2684 memcpy (&deps_init_id_sched_deps_info,
2685 &const_deps_init_id_sched_deps_info,
2686 sizeof (deps_init_id_sched_deps_info));
2688 if (spec_info != NULL)
2689 deps_init_id_sched_deps_info.generate_spec_deps = 1;
2691 sched_deps_info = &deps_init_id_sched_deps_info;
2693 deps_analyze_insn (dc, insn);
2697 deps_init_id_data.id = NULL;
2702 /* Implement hooks for collecting fundamental insn properties like if insn is
2703 an ASM or is within a SCHED_GROUP. */
2705 /* True when a "one-time init" data for INSN was already inited. */
2707 first_time_insn_init (insn_t insn)
2709 return INSN_LIVE (insn) == NULL;
2712 /* Hash an entry in a transformed_insns hashtable. */
2714 hash_transformed_insns (const void *p)
2716 return VINSN_HASH_RTX (((const struct transformed_insns *) p)->vinsn_old);
2719 /* Compare the entries in a transformed_insns hashtable. */
2721 eq_transformed_insns (const void *p, const void *q)
2723 rtx i1 = VINSN_INSN_RTX (((const struct transformed_insns *) p)->vinsn_old);
2724 rtx i2 = VINSN_INSN_RTX (((const struct transformed_insns *) q)->vinsn_old);
2726 if (INSN_UID (i1) == INSN_UID (i2))
2728 return rtx_equal_p (PATTERN (i1), PATTERN (i2));
2731 /* Free an entry in a transformed_insns hashtable. */
2733 free_transformed_insns (void *p)
2735 struct transformed_insns *pti = (struct transformed_insns *) p;
2737 vinsn_detach (pti->vinsn_old);
2738 vinsn_detach (pti->vinsn_new);
2742 /* Init the s_i_d data for INSN which should be inited just once, when
2743 we first see the insn. */
2745 init_first_time_insn_data (insn_t insn)
2747 /* This should not be set if this is the first time we init data for
2749 gcc_assert (first_time_insn_init (insn));
2751 /* These are needed for nops too. */
2752 INSN_LIVE (insn) = get_regset_from_pool ();
2753 INSN_LIVE_VALID_P (insn) = false;
2755 if (!INSN_NOP_P (insn))
2757 INSN_ANALYZED_DEPS (insn) = BITMAP_ALLOC (NULL);
2758 INSN_FOUND_DEPS (insn) = BITMAP_ALLOC (NULL);
2759 INSN_TRANSFORMED_INSNS (insn)
2760 = htab_create (16, hash_transformed_insns,
2761 eq_transformed_insns, free_transformed_insns);
2762 init_deps (&INSN_DEPS_CONTEXT (insn), true);
2766 /* Free almost all above data for INSN that is scheduled already.
2767 Used for extra-large basic blocks. */
2769 free_data_for_scheduled_insn (insn_t insn)
2771 gcc_assert (! first_time_insn_init (insn));
2773 if (! INSN_ANALYZED_DEPS (insn))
2776 BITMAP_FREE (INSN_ANALYZED_DEPS (insn));
2777 BITMAP_FREE (INSN_FOUND_DEPS (insn));
2778 htab_delete (INSN_TRANSFORMED_INSNS (insn));
2780 /* This is allocated only for bookkeeping insns. */
2781 if (INSN_ORIGINATORS (insn))
2782 BITMAP_FREE (INSN_ORIGINATORS (insn));
2783 free_deps (&INSN_DEPS_CONTEXT (insn));
2785 INSN_ANALYZED_DEPS (insn) = NULL;
2787 /* Clear the readonly flag so we would ICE when trying to recalculate
2788 the deps context (as we believe that it should not happen). */
2789 (&INSN_DEPS_CONTEXT (insn))->readonly = 0;
2792 /* Free the same data as above for INSN. */
2794 free_first_time_insn_data (insn_t insn)
2796 gcc_assert (! first_time_insn_init (insn));
2798 free_data_for_scheduled_insn (insn);
2799 return_regset_to_pool (INSN_LIVE (insn));
2800 INSN_LIVE (insn) = NULL;
2801 INSN_LIVE_VALID_P (insn) = false;
2804 /* Initialize region-scope data structures for basic blocks. */
2806 init_global_and_expr_for_bb (basic_block bb)
2808 if (sel_bb_empty_p (bb))
2811 invalidate_av_set (bb);
2814 /* Data for global dependency analysis (to initialize CANT_MOVE and
2818 /* Previous insn. */
2822 /* Determine if INSN is in the sched_group, is an asm or should not be
2823 cloned. After that initialize its expr. */
2825 init_global_and_expr_for_insn (insn_t insn)
2830 if (NOTE_INSN_BASIC_BLOCK_P (insn))
2832 init_global_data.prev_insn = NULL_RTX;
2836 gcc_assert (INSN_P (insn));
2838 if (SCHED_GROUP_P (insn))
2839 /* Setup a sched_group. */
2841 insn_t prev_insn = init_global_data.prev_insn;
2844 INSN_SCHED_NEXT (prev_insn) = insn;
2846 init_global_data.prev_insn = insn;
2849 init_global_data.prev_insn = NULL_RTX;
2851 if (GET_CODE (PATTERN (insn)) == ASM_INPUT
2852 || asm_noperands (PATTERN (insn)) >= 0)
2853 /* Mark INSN as an asm. */
2854 INSN_ASM_P (insn) = true;
2857 bool force_unique_p;
2860 /* Certain instructions cannot be cloned. */
2861 if (CANT_MOVE (insn)
2862 || INSN_ASM_P (insn)
2863 || SCHED_GROUP_P (insn)
2864 || prologue_epilogue_contains (insn)
2865 /* Exception handling insns are always unique. */
2866 || (flag_non_call_exceptions && can_throw_internal (insn))
2867 /* TRAP_IF though have an INSN code is control_flow_insn_p (). */
2868 || control_flow_insn_p (insn))
2869 force_unique_p = true;
2871 force_unique_p = false;
2873 if (targetm.sched.get_insn_spec_ds)
2875 spec_done_ds = targetm.sched.get_insn_spec_ds (insn);
2876 spec_done_ds = ds_get_max_dep_weak (spec_done_ds);
2881 /* Initialize INSN's expr. */
2882 init_expr (INSN_EXPR (insn), vinsn_create (insn, force_unique_p), 0,
2883 REG_BR_PROB_BASE, INSN_PRIORITY (insn), 0, BLOCK_NUM (insn),
2884 spec_done_ds, 0, 0, NULL, true, false, false, false,
2888 init_first_time_insn_data (insn);
2891 /* Scan the region and initialize instruction data for basic blocks BBS. */
2893 sel_init_global_and_expr (bb_vec_t bbs)
2895 /* ??? It would be nice to implement push / pop scheme for sched_infos. */
2896 const struct sched_scan_info_def ssi =
2898 NULL, /* extend_bb */
2899 init_global_and_expr_for_bb, /* init_bb */
2900 extend_insn_data, /* extend_insn */
2901 init_global_and_expr_for_insn /* init_insn */
2904 sched_scan (&ssi, bbs, NULL, NULL, NULL);
2907 /* Finalize region-scope data structures for basic blocks. */
2909 finish_global_and_expr_for_bb (basic_block bb)
2911 av_set_clear (&BB_AV_SET (bb));
2912 BB_AV_LEVEL (bb) = 0;
2915 /* Finalize INSN's data. */
2917 finish_global_and_expr_insn (insn_t insn)
2919 if (LABEL_P (insn) || NOTE_INSN_BASIC_BLOCK_P (insn))
2922 gcc_assert (INSN_P (insn));
2924 if (INSN_LUID (insn) > 0)
2926 free_first_time_insn_data (insn);
2927 INSN_WS_LEVEL (insn) = 0;
2928 CANT_MOVE (insn) = 0;
2930 /* We can no longer assert this, as vinsns of this insn could be
2931 easily live in other insn's caches. This should be changed to
2932 a counter-like approach among all vinsns. */
2933 gcc_assert (true || VINSN_COUNT (INSN_VINSN (insn)) == 1);
2934 clear_expr (INSN_EXPR (insn));
2938 /* Finalize per instruction data for the whole region. */
2940 sel_finish_global_and_expr (void)
2946 bbs = VEC_alloc (basic_block, heap, current_nr_blocks);
2948 for (i = 0; i < current_nr_blocks; i++)
2949 VEC_quick_push (basic_block, bbs, BASIC_BLOCK (BB_TO_BLOCK (i)));
2951 /* Clear AV_SETs and INSN_EXPRs. */
2953 const struct sched_scan_info_def ssi =
2955 NULL, /* extend_bb */
2956 finish_global_and_expr_for_bb, /* init_bb */
2957 NULL, /* extend_insn */
2958 finish_global_and_expr_insn /* init_insn */
2961 sched_scan (&ssi, bbs, NULL, NULL, NULL);
2964 VEC_free (basic_block, heap, bbs);
2971 /* In the below hooks, we merely calculate whether or not a dependence
2972 exists, and in what part of insn. However, we will need more data
2973 when we'll start caching dependence requests. */
2975 /* Container to hold information for dependency analysis. */
2980 /* A variable to track which part of rtx we are scanning in
2981 sched-deps.c: sched_analyze_insn (). */
2984 /* Current producer. */
2987 /* Current consumer. */
2990 /* Is SEL_DEPS_HAS_DEP_P[DEPS_IN_X] is true, then X has a dependence.
2991 X is from { INSN, LHS, RHS }. */
2992 ds_t has_dep_p[DEPS_IN_NOWHERE];
2993 } has_dependence_data;
2995 /* Start analyzing dependencies of INSN. */
2997 has_dependence_start_insn (insn_t insn ATTRIBUTE_UNUSED)
2999 gcc_assert (has_dependence_data.where == DEPS_IN_NOWHERE);
3001 has_dependence_data.where = DEPS_IN_INSN;
3004 /* Finish analyzing dependencies of an insn. */
3006 has_dependence_finish_insn (void)
3008 gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
3010 has_dependence_data.where = DEPS_IN_NOWHERE;
3013 /* Start analyzing dependencies of LHS. */
3015 has_dependence_start_lhs (rtx lhs ATTRIBUTE_UNUSED)
3017 gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
3019 if (VINSN_LHS (has_dependence_data.con) != NULL)
3020 has_dependence_data.where = DEPS_IN_LHS;
3023 /* Finish analyzing dependencies of an lhs. */
3025 has_dependence_finish_lhs (void)
3027 has_dependence_data.where = DEPS_IN_INSN;
3030 /* Start analyzing dependencies of RHS. */
3032 has_dependence_start_rhs (rtx rhs ATTRIBUTE_UNUSED)
3034 gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
3036 if (VINSN_RHS (has_dependence_data.con) != NULL)
3037 has_dependence_data.where = DEPS_IN_RHS;
3040 /* Start analyzing dependencies of an rhs. */
3042 has_dependence_finish_rhs (void)
3044 gcc_assert (has_dependence_data.where == DEPS_IN_RHS
3045 || has_dependence_data.where == DEPS_IN_INSN);
3047 has_dependence_data.where = DEPS_IN_INSN;
3050 /* Note a set of REGNO. */
3052 has_dependence_note_reg_set (int regno)
3054 struct deps_reg *reg_last = &has_dependence_data.dc->reg_last[regno];
3056 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3058 (has_dependence_data.con)))
3060 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3062 if (reg_last->sets != NULL
3063 || reg_last->clobbers != NULL)
3064 *dsp = (*dsp & ~SPECULATIVE) | DEP_OUTPUT;
3067 *dsp = (*dsp & ~SPECULATIVE) | DEP_ANTI;
3071 /* Note a clobber of REGNO. */
3073 has_dependence_note_reg_clobber (int regno)
3075 struct deps_reg *reg_last = &has_dependence_data.dc->reg_last[regno];
3077 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3079 (has_dependence_data.con)))
3081 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3084 *dsp = (*dsp & ~SPECULATIVE) | DEP_OUTPUT;
3087 *dsp = (*dsp & ~SPECULATIVE) | DEP_ANTI;
3091 /* Note a use of REGNO. */
3093 has_dependence_note_reg_use (int regno)
3095 struct deps_reg *reg_last = &has_dependence_data.dc->reg_last[regno];
3097 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3099 (has_dependence_data.con)))
3101 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3104 *dsp = (*dsp & ~SPECULATIVE) | DEP_TRUE;
3106 if (reg_last->clobbers)
3107 *dsp = (*dsp & ~SPECULATIVE) | DEP_ANTI;
3109 /* Handle BE_IN_SPEC. */
3112 ds_t pro_spec_checked_ds;
3114 pro_spec_checked_ds = INSN_SPEC_CHECKED_DS (has_dependence_data.pro);
3115 pro_spec_checked_ds = ds_get_max_dep_weak (pro_spec_checked_ds);
3117 if (pro_spec_checked_ds != 0)
3118 /* Merge BE_IN_SPEC bits into *DSP. */
3119 *dsp = ds_full_merge (*dsp, pro_spec_checked_ds,
3120 NULL_RTX, NULL_RTX);
3125 /* Note a memory dependence. */
3127 has_dependence_note_mem_dep (rtx mem ATTRIBUTE_UNUSED,
3128 rtx pending_mem ATTRIBUTE_UNUSED,
3129 insn_t pending_insn ATTRIBUTE_UNUSED,
3130 ds_t ds ATTRIBUTE_UNUSED)
3132 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3133 VINSN_INSN_RTX (has_dependence_data.con)))
3135 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3137 *dsp = ds_full_merge (ds, *dsp, pending_mem, mem);
3141 /* Note a dependence. */
3143 has_dependence_note_dep (insn_t pro ATTRIBUTE_UNUSED,
3144 ds_t ds ATTRIBUTE_UNUSED)
3146 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3147 VINSN_INSN_RTX (has_dependence_data.con)))
3149 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3151 *dsp = ds_full_merge (ds, *dsp, NULL_RTX, NULL_RTX);
3155 /* Mark the insn as having a hard dependence that prevents speculation. */
3157 sel_mark_hard_insn (rtx insn)
3161 /* Only work when we're in has_dependence_p mode.
3162 ??? This is a hack, this should actually be a hook. */
3163 if (!has_dependence_data.dc || !has_dependence_data.pro)
3166 gcc_assert (insn == VINSN_INSN_RTX (has_dependence_data.con));
3167 gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
3169 for (i = 0; i < DEPS_IN_NOWHERE; i++)
3170 has_dependence_data.has_dep_p[i] &= ~SPECULATIVE;
3173 /* This structure holds the hooks for the dependency analysis used when
3174 actually processing dependencies in the scheduler. */
3175 static struct sched_deps_info_def has_dependence_sched_deps_info;
3177 /* This initializes most of the fields of the above structure. */
3178 static const struct sched_deps_info_def const_has_dependence_sched_deps_info =
3182 has_dependence_start_insn,
3183 has_dependence_finish_insn,
3184 has_dependence_start_lhs,
3185 has_dependence_finish_lhs,
3186 has_dependence_start_rhs,
3187 has_dependence_finish_rhs,
3188 has_dependence_note_reg_set,
3189 has_dependence_note_reg_clobber,
3190 has_dependence_note_reg_use,
3191 has_dependence_note_mem_dep,
3192 has_dependence_note_dep,
3195 0, /* use_deps_list */
3196 0 /* generate_spec_deps */
3199 /* Initialize has_dependence_sched_deps_info with extra spec field. */
3201 setup_has_dependence_sched_deps_info (void)
3203 memcpy (&has_dependence_sched_deps_info,
3204 &const_has_dependence_sched_deps_info,
3205 sizeof (has_dependence_sched_deps_info));
3207 if (spec_info != NULL)
3208 has_dependence_sched_deps_info.generate_spec_deps = 1;
3210 sched_deps_info = &has_dependence_sched_deps_info;
3213 /* Remove all dependences found and recorded in has_dependence_data array. */
3215 sel_clear_has_dependence (void)
3219 for (i = 0; i < DEPS_IN_NOWHERE; i++)
3220 has_dependence_data.has_dep_p[i] = 0;
3223 /* Return nonzero if EXPR has is dependent upon PRED. Return the pointer
3224 to the dependence information array in HAS_DEP_PP. */
3226 has_dependence_p (expr_t expr, insn_t pred, ds_t **has_dep_pp)
3232 if (INSN_SIMPLEJUMP_P (pred))
3233 /* Unconditional jump is just a transfer of control flow.
3237 dc = &INSN_DEPS_CONTEXT (pred);
3239 /* We init this field lazily. */
3240 if (dc->reg_last == NULL)
3241 init_deps_reg_last (dc);
3245 has_dependence_data.pro = NULL;
3246 /* Initialize empty dep context with information about PRED. */
3247 advance_deps_context (dc, pred);
3251 has_dependence_data.where = DEPS_IN_NOWHERE;
3252 has_dependence_data.pro = pred;
3253 has_dependence_data.con = EXPR_VINSN (expr);
3254 has_dependence_data.dc = dc;
3256 sel_clear_has_dependence ();
3258 /* Now catch all dependencies that would be generated between PRED and
3260 setup_has_dependence_sched_deps_info ();
3261 deps_analyze_insn (dc, EXPR_INSN_RTX (expr));
3262 has_dependence_data.dc = NULL;
3264 /* When a barrier was found, set DEPS_IN_INSN bits. */
3265 if (dc->last_reg_pending_barrier == TRUE_BARRIER)
3266 has_dependence_data.has_dep_p[DEPS_IN_INSN] = DEP_TRUE;
3267 else if (dc->last_reg_pending_barrier == MOVE_BARRIER)
3268 has_dependence_data.has_dep_p[DEPS_IN_INSN] = DEP_ANTI;
3270 /* Do not allow stores to memory to move through checks. Currently
3271 we don't move this to sched-deps.c as the check doesn't have
3272 obvious places to which this dependence can be attached.
3273 FIMXE: this should go to a hook. */
3275 && MEM_P (EXPR_LHS (expr))
3276 && sel_insn_is_speculation_check (pred))
3277 has_dependence_data.has_dep_p[DEPS_IN_INSN] = DEP_ANTI;
3279 *has_dep_pp = has_dependence_data.has_dep_p;
3281 for (i = 0; i < DEPS_IN_NOWHERE; i++)
3282 ds = ds_full_merge (ds, has_dependence_data.has_dep_p[i],
3283 NULL_RTX, NULL_RTX);
3289 /* Dependence hooks implementation that checks dependence latency constraints
3290 on the insns being scheduled. The entry point for these routines is
3291 tick_check_p predicate. */
3295 /* An expr we are currently checking. */
3298 /* A minimal cycle for its scheduling. */
3301 /* Whether we have seen a true dependence while checking. */
3302 bool seen_true_dep_p;
3305 /* Update minimal scheduling cycle for tick_check_insn given that it depends
3306 on PRO with status DS and weight DW. */
3308 tick_check_dep_with_dw (insn_t pro_insn, ds_t ds, dw_t dw)
3310 expr_t con_expr = tick_check_data.expr;
3311 insn_t con_insn = EXPR_INSN_RTX (con_expr);
3313 if (con_insn != pro_insn)
3318 if (/* PROducer was removed from above due to pipelining. */
3319 !INSN_IN_STREAM_P (pro_insn)
3320 /* Or PROducer was originally on the next iteration regarding the
3322 || (INSN_SCHED_TIMES (pro_insn)
3323 - EXPR_SCHED_TIMES (con_expr)) > 1)
3324 /* Don't count this dependence. */
3328 if (dt == REG_DEP_TRUE)
3329 tick_check_data.seen_true_dep_p = true;
3331 gcc_assert (INSN_SCHED_CYCLE (pro_insn) > 0);
3334 dep_def _dep, *dep = &_dep;
3336 init_dep (dep, pro_insn, con_insn, dt);
3338 tick = INSN_SCHED_CYCLE (pro_insn) + dep_cost_1 (dep, dw);
3341 /* When there are several kinds of dependencies between pro and con,
3342 only REG_DEP_TRUE should be taken into account. */
3343 if (tick > tick_check_data.cycle
3344 && (dt == REG_DEP_TRUE || !tick_check_data.seen_true_dep_p))
3345 tick_check_data.cycle = tick;
3349 /* An implementation of note_dep hook. */
3351 tick_check_note_dep (insn_t pro, ds_t ds)
3353 tick_check_dep_with_dw (pro, ds, 0);
3356 /* An implementation of note_mem_dep hook. */
3358 tick_check_note_mem_dep (rtx mem1, rtx mem2, insn_t pro, ds_t ds)
3362 dw = (ds_to_dt (ds) == REG_DEP_TRUE
3363 ? estimate_dep_weak (mem1, mem2)
3366 tick_check_dep_with_dw (pro, ds, dw);
3369 /* This structure contains hooks for dependence analysis used when determining
3370 whether an insn is ready for scheduling. */
3371 static struct sched_deps_info_def tick_check_sched_deps_info =
3382 haifa_note_reg_clobber,
3384 tick_check_note_mem_dep,
3385 tick_check_note_dep,
3390 /* Estimate number of cycles from the current cycle of FENCE until EXPR can be
3391 scheduled. Return 0 if all data from producers in DC is ready. */
3393 tick_check_p (expr_t expr, deps_t dc, fence_t fence)
3396 /* Initialize variables. */
3397 tick_check_data.expr = expr;
3398 tick_check_data.cycle = 0;
3399 tick_check_data.seen_true_dep_p = false;
3400 sched_deps_info = &tick_check_sched_deps_info;
3402 gcc_assert (!dc->readonly);
3404 deps_analyze_insn (dc, EXPR_INSN_RTX (expr));
3407 cycles_left = tick_check_data.cycle - FENCE_CYCLE (fence);
3409 return cycles_left >= 0 ? cycles_left : 0;
3413 /* Functions to work with insns. */
3415 /* Returns true if LHS of INSN is the same as DEST of an insn
3418 lhs_of_insn_equals_to_dest_p (insn_t insn, rtx dest)
3420 rtx lhs = INSN_LHS (insn);
3422 if (lhs == NULL || dest == NULL)
3425 return rtx_equal_p (lhs, dest);
3428 /* Return s_i_d entry of INSN. Callable from debugger. */
3430 insn_sid (insn_t insn)
3435 /* True when INSN is a speculative check. We can tell this by looking
3436 at the data structures of the selective scheduler, not by examining
3439 sel_insn_is_speculation_check (rtx insn)
3441 return s_i_d && !! INSN_SPEC_CHECKED_DS (insn);
3444 /* Extracts machine mode MODE and destination location DST_LOC
3447 get_dest_and_mode (rtx insn, rtx *dst_loc, enum machine_mode *mode)
3449 rtx pat = PATTERN (insn);
3451 gcc_assert (dst_loc);
3452 gcc_assert (GET_CODE (pat) == SET);
3454 *dst_loc = SET_DEST (pat);
3456 gcc_assert (*dst_loc);
3457 gcc_assert (MEM_P (*dst_loc) || REG_P (*dst_loc));
3460 *mode = GET_MODE (*dst_loc);
3463 /* Returns true when moving through JUMP will result in bookkeeping
3466 bookkeeping_can_be_created_if_moved_through_p (insn_t jump)
3471 FOR_EACH_SUCC (succ, si, jump)
3472 if (sel_num_cfg_preds_gt_1 (succ))
3478 /* Return 'true' if INSN is the only one in its basic block. */
3480 insn_is_the_only_one_in_bb_p (insn_t insn)
3482 return sel_bb_head_p (insn) && sel_bb_end_p (insn);
3485 #ifdef ENABLE_CHECKING
3486 /* Check that the region we're scheduling still has at most one
3489 verify_backedges (void)
3497 for (i = 0; i < current_nr_blocks; i++)
3498 FOR_EACH_EDGE (e, ei, BASIC_BLOCK (BB_TO_BLOCK (i))->succs)
3499 if (in_current_region_p (e->dest)
3500 && BLOCK_TO_BB (e->dest->index) < i)
3503 gcc_assert (n <= 1);
3509 /* Functions to work with control flow. */
3511 /* Recompute BLOCK_TO_BB and BB_FOR_BLOCK for current region so that blocks
3512 are sorted in topological order (it might have been invalidated by
3513 redirecting an edge). */
3515 sel_recompute_toporder (void)
3518 int *postorder, n_blocks;
3520 postorder = XALLOCAVEC (int, n_basic_blocks);
3521 n_blocks = post_order_compute (postorder, false, false);
3523 rgn = CONTAINING_RGN (BB_TO_BLOCK (0));
3524 for (n = 0, i = n_blocks - 1; i >= 0; i--)
3525 if (CONTAINING_RGN (postorder[i]) == rgn)
3527 BLOCK_TO_BB (postorder[i]) = n;
3528 BB_TO_BLOCK (n) = postorder[i];
3532 /* Assert that we updated info for all blocks. We may miss some blocks if
3533 this function is called when redirecting an edge made a block
3534 unreachable, but that block is not deleted yet. */
3535 gcc_assert (n == RGN_NR_BLOCKS (rgn));
3538 /* Tidy the possibly empty block BB. */
3540 maybe_tidy_empty_bb (basic_block bb, bool recompute_toporder_p)
3542 basic_block succ_bb, pred_bb;
3543 VEC (basic_block, heap) *dom_bbs;
3548 /* Keep empty bb only if this block immediately precedes EXIT and
3549 has incoming non-fallthrough edge, or it has no predecessors or
3550 successors. Otherwise remove it. */
3551 if (!sel_bb_empty_p (bb)
3552 || (single_succ_p (bb)
3553 && single_succ (bb) == EXIT_BLOCK_PTR
3554 && (!single_pred_p (bb)
3555 || !(single_pred_edge (bb)->flags & EDGE_FALLTHRU)))
3556 || EDGE_COUNT (bb->preds) == 0
3557 || EDGE_COUNT (bb->succs) == 0)
3560 /* Do not attempt to redirect complex edges. */
3561 FOR_EACH_EDGE (e, ei, bb->preds)
3562 if (e->flags & EDGE_COMPLEX)
3565 free_data_sets (bb);
3567 /* Do not delete BB if it has more than one successor.
3568 That can occur when we moving a jump. */
3569 if (!single_succ_p (bb))
3571 gcc_assert (can_merge_blocks_p (bb->prev_bb, bb));
3572 sel_merge_blocks (bb->prev_bb, bb);
3576 succ_bb = single_succ (bb);
3581 /* Redirect all non-fallthru edges to the next bb. */
3586 FOR_EACH_EDGE (e, ei, bb->preds)
3590 if (!(e->flags & EDGE_FALLTHRU))
3592 /* We will update dominators here only when we'll get
3593 an unreachable block when redirecting, otherwise
3594 sel_redirect_edge_and_branch will take care of it. */
3596 && single_pred_p (e->dest))
3597 VEC_safe_push (basic_block, heap, dom_bbs, e->dest);
3598 recompute_toporder_p |= sel_redirect_edge_and_branch (e, succ_bb);
3605 if (can_merge_blocks_p (bb->prev_bb, bb))
3606 sel_merge_blocks (bb->prev_bb, bb);
3609 /* This is a block without fallthru predecessor. Just delete it. */
3610 gcc_assert (pred_bb != NULL);
3612 if (in_current_region_p (pred_bb))
3613 move_bb_info (pred_bb, bb);
3614 remove_empty_bb (bb, true);
3617 if (!VEC_empty (basic_block, dom_bbs))
3619 VEC_safe_push (basic_block, heap, dom_bbs, succ_bb);
3620 iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, false);
3621 VEC_free (basic_block, heap, dom_bbs);
3624 if (recompute_toporder_p)
3625 sel_recompute_toporder ();
3627 #ifdef ENABLE_CHECKING
3628 verify_backedges ();
3629 verify_dominators (CDI_DOMINATORS);
3635 /* Tidy the control flow after we have removed original insn from
3636 XBB. Return true if we have removed some blocks. When FULL_TIDYING
3637 is true, also try to optimize control flow on non-empty blocks. */
3639 tidy_control_flow (basic_block xbb, bool full_tidying)
3641 bool changed = true;
3643 /* First check whether XBB is empty. */
3644 changed = maybe_tidy_empty_bb (xbb, false);
3645 if (changed || !full_tidying)
3648 /* Check if there is a unnecessary jump after insn left. */
3649 if (jump_leads_only_to_bb_p (BB_END (xbb), xbb->next_bb)
3650 && INSN_SCHED_TIMES (BB_END (xbb)) == 0
3651 && !IN_CURRENT_FENCE_P (BB_END (xbb)))
3653 if (sel_remove_insn (BB_END (xbb), false, false))
3655 tidy_fallthru_edge (EDGE_SUCC (xbb, 0));
3658 /* Check if there is an unnecessary jump in previous basic block leading
3659 to next basic block left after removing INSN from stream.
3660 If it is so, remove that jump and redirect edge to current
3661 basic block (where there was INSN before deletion). This way
3662 when NOP will be deleted several instructions later with its
3663 basic block we will not get a jump to next instruction, which
3665 if (sel_bb_head (xbb) == sel_bb_end (xbb)
3666 && !sel_bb_empty_p (xbb)
3667 && INSN_NOP_P (sel_bb_end (xbb))
3668 /* Flow goes fallthru from current block to the next. */
3669 && EDGE_COUNT (xbb->succs) == 1
3670 && (EDGE_SUCC (xbb, 0)->flags & EDGE_FALLTHRU)
3671 /* When successor is an EXIT block, it may not be the next block. */
3672 && single_succ (xbb) != EXIT_BLOCK_PTR
3673 /* And unconditional jump in previous basic block leads to
3674 next basic block of XBB and this jump can be safely removed. */
3675 && in_current_region_p (xbb->prev_bb)
3676 && jump_leads_only_to_bb_p (BB_END (xbb->prev_bb), xbb->next_bb)
3677 && INSN_SCHED_TIMES (BB_END (xbb->prev_bb)) == 0
3678 /* Also this jump is not at the scheduling boundary. */
3679 && !IN_CURRENT_FENCE_P (BB_END (xbb->prev_bb)))
3681 bool recompute_toporder_p;
3682 /* Clear data structures of jump - jump itself will be removed
3683 by sel_redirect_edge_and_branch. */
3684 clear_expr (INSN_EXPR (BB_END (xbb->prev_bb)));
3685 recompute_toporder_p
3686 = sel_redirect_edge_and_branch (EDGE_SUCC (xbb->prev_bb, 0), xbb);
3688 gcc_assert (EDGE_SUCC (xbb->prev_bb, 0)->flags & EDGE_FALLTHRU);
3690 /* It can turn out that after removing unused jump, basic block
3691 that contained that jump, becomes empty too. In such case
3693 if (sel_bb_empty_p (xbb->prev_bb))
3694 changed = maybe_tidy_empty_bb (xbb->prev_bb, recompute_toporder_p);
3695 else if (recompute_toporder_p)
3696 sel_recompute_toporder ();
3702 /* Purge meaningless empty blocks in the middle of a region. */
3704 purge_empty_blocks (void)
3706 /* Do not attempt to delete preheader. */
3707 int i = sel_is_loop_preheader_p (BASIC_BLOCK (BB_TO_BLOCK (0))) ? 1 : 0;
3709 while (i < current_nr_blocks)
3711 basic_block b = BASIC_BLOCK (BB_TO_BLOCK (i));
3713 if (maybe_tidy_empty_bb (b, false))
3720 /* Rip-off INSN from the insn stream. When ONLY_DISCONNECT is true,
3721 do not delete insn's data, because it will be later re-emitted.
3722 Return true if we have removed some blocks afterwards. */
3724 sel_remove_insn (insn_t insn, bool only_disconnect, bool full_tidying)
3726 basic_block bb = BLOCK_FOR_INSN (insn);
3728 gcc_assert (INSN_IN_STREAM_P (insn));
3730 if (only_disconnect)
3732 insn_t prev = PREV_INSN (insn);
3733 insn_t next = NEXT_INSN (insn);
3734 basic_block bb = BLOCK_FOR_INSN (insn);
3736 NEXT_INSN (prev) = next;
3737 PREV_INSN (next) = prev;
3739 if (BB_HEAD (bb) == insn)
3741 gcc_assert (BLOCK_FOR_INSN (prev) == bb);
3742 BB_HEAD (bb) = prev;
3744 if (BB_END (bb) == insn)
3750 clear_expr (INSN_EXPR (insn));
3753 /* It is necessary to null this fields before calling add_insn (). */
3754 PREV_INSN (insn) = NULL_RTX;
3755 NEXT_INSN (insn) = NULL_RTX;
3757 return tidy_control_flow (bb, full_tidying);
3760 /* Estimate number of the insns in BB. */
3762 sel_estimate_number_of_insns (basic_block bb)
3765 insn_t insn = NEXT_INSN (BB_HEAD (bb)), next_tail = NEXT_INSN (BB_END (bb));
3767 for (; insn != next_tail; insn = NEXT_INSN (insn))
3774 /* We don't need separate luids for notes or labels. */
3776 sel_luid_for_non_insn (rtx x)
3778 gcc_assert (NOTE_P (x) || LABEL_P (x));
3783 /* Return seqno of the only predecessor of INSN. */
3785 get_seqno_of_a_pred (insn_t insn)
3789 gcc_assert (INSN_SIMPLEJUMP_P (insn));
3791 if (!sel_bb_head_p (insn))
3792 seqno = INSN_SEQNO (PREV_INSN (insn));
3795 basic_block bb = BLOCK_FOR_INSN (insn);
3797 if (single_pred_p (bb)
3798 && !in_current_region_p (single_pred (bb)))
3800 /* We can have preds outside a region when splitting edges
3801 for pipelining of an outer loop. Use succ instead.
3802 There should be only one of them. */
3807 gcc_assert (flag_sel_sched_pipelining_outer_loops
3808 && current_loop_nest);
3809 FOR_EACH_SUCC_1 (succ, si, insn,
3810 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
3816 gcc_assert (succ != NULL);
3817 seqno = INSN_SEQNO (succ);
3824 cfg_preds (BLOCK_FOR_INSN (insn), &preds, &n);
3825 gcc_assert (n == 1);
3827 seqno = INSN_SEQNO (preds[0]);
3836 /* Find the proper seqno for inserting at INSN. Returns -1 if no predecessors
3837 with positive seqno exist. */
3839 get_seqno_by_preds (rtx insn)
3841 basic_block bb = BLOCK_FOR_INSN (insn);
3842 rtx tmp = insn, head = BB_HEAD (bb);
3848 return INSN_SEQNO (tmp);
3850 tmp = PREV_INSN (tmp);
3852 cfg_preds (bb, &preds, &n);
3853 for (i = 0, seqno = -1; i < n; i++)
3854 seqno = MAX (seqno, INSN_SEQNO (preds[i]));
3861 /* Extend pass-scope data structures for basic blocks. */
3863 sel_extend_global_bb_info (void)
3865 VEC_safe_grow_cleared (sel_global_bb_info_def, heap, sel_global_bb_info,
3869 /* Extend region-scope data structures for basic blocks. */
3871 extend_region_bb_info (void)
3873 VEC_safe_grow_cleared (sel_region_bb_info_def, heap, sel_region_bb_info,
3877 /* Extend all data structures to fit for all basic blocks. */
3879 extend_bb_info (void)
3881 sel_extend_global_bb_info ();
3882 extend_region_bb_info ();
3885 /* Finalize pass-scope data structures for basic blocks. */
3887 sel_finish_global_bb_info (void)
3889 VEC_free (sel_global_bb_info_def, heap, sel_global_bb_info);
3892 /* Finalize region-scope data structures for basic blocks. */
3894 finish_region_bb_info (void)
3896 VEC_free (sel_region_bb_info_def, heap, sel_region_bb_info);
3900 /* Data for each insn in current region. */
3901 VEC (sel_insn_data_def, heap) *s_i_d = NULL;
3903 /* A vector for the insns we've emitted. */
3904 static insn_vec_t new_insns = NULL;
3906 /* Extend data structures for insns from current region. */
3908 extend_insn_data (void)
3912 sched_extend_target ();
3913 sched_deps_init (false);
3915 /* Extend data structures for insns from current region. */
3916 reserve = (sched_max_luid + 1
3917 - VEC_length (sel_insn_data_def, s_i_d));
3919 && ! VEC_space (sel_insn_data_def, s_i_d, reserve))
3923 if (sched_max_luid / 2 > 1024)
3924 size = sched_max_luid + 1024;
3926 size = 3 * sched_max_luid / 2;
3929 VEC_safe_grow_cleared (sel_insn_data_def, heap, s_i_d, size);
3933 /* Finalize data structures for insns from current region. */
3939 /* Clear here all dependence contexts that may have left from insns that were
3940 removed during the scheduling. */
3941 for (i = 0; i < VEC_length (sel_insn_data_def, s_i_d); i++)
3943 sel_insn_data_def *sid_entry = VEC_index (sel_insn_data_def, s_i_d, i);
3945 if (sid_entry->live)
3946 return_regset_to_pool (sid_entry->live);
3947 if (sid_entry->analyzed_deps)
3949 BITMAP_FREE (sid_entry->analyzed_deps);
3950 BITMAP_FREE (sid_entry->found_deps);
3951 htab_delete (sid_entry->transformed_insns);
3952 free_deps (&sid_entry->deps_context);
3954 if (EXPR_VINSN (&sid_entry->expr))
3956 clear_expr (&sid_entry->expr);
3958 /* Also, clear CANT_MOVE bit here, because we really don't want it
3959 to be passed to the next region. */
3960 CANT_MOVE_BY_LUID (i) = 0;
3964 VEC_free (sel_insn_data_def, heap, s_i_d);
3967 /* A proxy to pass initialization data to init_insn (). */
3968 static sel_insn_data_def _insn_init_ssid;
3969 static sel_insn_data_t insn_init_ssid = &_insn_init_ssid;
3971 /* If true create a new vinsn. Otherwise use the one from EXPR. */
3972 static bool insn_init_create_new_vinsn_p;
3974 /* Set all necessary data for initialization of the new insn[s]. */
3976 set_insn_init (expr_t expr, vinsn_t vi, int seqno)
3978 expr_t x = &insn_init_ssid->expr;
3980 copy_expr_onside (x, expr);
3983 insn_init_create_new_vinsn_p = false;
3984 change_vinsn_in_expr (x, vi);
3987 insn_init_create_new_vinsn_p = true;
3989 insn_init_ssid->seqno = seqno;
3993 /* Init data for INSN. */
3995 init_insn_data (insn_t insn)
3998 sel_insn_data_t ssid = insn_init_ssid;
4000 /* The fields mentioned below are special and hence are not being
4001 propagated to the new insns. */
4002 gcc_assert (!ssid->asm_p && ssid->sched_next == NULL
4003 && !ssid->after_stall_p && ssid->sched_cycle == 0);
4004 gcc_assert (INSN_P (insn) && INSN_LUID (insn) > 0);
4006 expr = INSN_EXPR (insn);
4007 copy_expr (expr, &ssid->expr);
4008 prepare_insn_expr (insn, ssid->seqno);
4010 if (insn_init_create_new_vinsn_p)
4011 change_vinsn_in_expr (expr, vinsn_create (insn, init_insn_force_unique_p));
4013 if (first_time_insn_init (insn))
4014 init_first_time_insn_data (insn);
4017 /* This is used to initialize spurious jumps generated by
4018 sel_redirect_edge (). */
4020 init_simplejump_data (insn_t insn)
4022 init_expr (INSN_EXPR (insn), vinsn_create (insn, false), 0,
4023 REG_BR_PROB_BASE, 0, 0, 0, 0, 0, 0, NULL, true, false, false,
4025 INSN_SEQNO (insn) = get_seqno_of_a_pred (insn);
4026 init_first_time_insn_data (insn);
4029 /* Perform deferred initialization of insns. This is used to process
4030 a new jump that may be created by redirect_edge. */
4032 sel_init_new_insn (insn_t insn, int flags)
4034 /* We create data structures for bb when the first insn is emitted in it. */
4036 && INSN_IN_STREAM_P (insn)
4037 && insn_is_the_only_one_in_bb_p (insn))
4040 create_initial_data_sets (BLOCK_FOR_INSN (insn));
4043 if (flags & INSN_INIT_TODO_LUID)
4044 sched_init_luids (NULL, NULL, NULL, insn);
4046 if (flags & INSN_INIT_TODO_SSID)
4048 extend_insn_data ();
4049 init_insn_data (insn);
4050 clear_expr (&insn_init_ssid->expr);
4053 if (flags & INSN_INIT_TODO_SIMPLEJUMP)
4055 extend_insn_data ();
4056 init_simplejump_data (insn);
4059 gcc_assert (CONTAINING_RGN (BLOCK_NUM (insn))
4060 == CONTAINING_RGN (BB_TO_BLOCK (0)));
4064 /* Functions to init/finish work with lv sets. */
4066 /* Init BB_LV_SET of BB from DF_LR_IN set of BB. */
4068 init_lv_set (basic_block bb)
4070 gcc_assert (!BB_LV_SET_VALID_P (bb));
4072 BB_LV_SET (bb) = get_regset_from_pool ();
4073 COPY_REG_SET (BB_LV_SET (bb), DF_LR_IN (bb));
4074 BB_LV_SET_VALID_P (bb) = true;
4077 /* Copy liveness information to BB from FROM_BB. */
4079 copy_lv_set_from (basic_block bb, basic_block from_bb)
4081 gcc_assert (!BB_LV_SET_VALID_P (bb));
4083 COPY_REG_SET (BB_LV_SET (bb), BB_LV_SET (from_bb));
4084 BB_LV_SET_VALID_P (bb) = true;
4087 /* Initialize lv set of all bb headers. */
4093 /* Initialize of LV sets. */
4097 /* Don't forget EXIT_BLOCK. */
4098 init_lv_set (EXIT_BLOCK_PTR);
4101 /* Release lv set of HEAD. */
4103 free_lv_set (basic_block bb)
4105 gcc_assert (BB_LV_SET (bb) != NULL);
4107 return_regset_to_pool (BB_LV_SET (bb));
4108 BB_LV_SET (bb) = NULL;
4109 BB_LV_SET_VALID_P (bb) = false;
4112 /* Finalize lv sets of all bb headers. */
4118 /* Don't forget EXIT_BLOCK. */
4119 free_lv_set (EXIT_BLOCK_PTR);
4127 /* Initialize an invalid AV_SET for BB.
4128 This set will be updated next time compute_av () process BB. */
4130 invalidate_av_set (basic_block bb)
4132 gcc_assert (BB_AV_LEVEL (bb) <= 0
4133 && BB_AV_SET (bb) == NULL);
4135 BB_AV_LEVEL (bb) = -1;
4138 /* Create initial data sets for BB (they will be invalid). */
4140 create_initial_data_sets (basic_block bb)
4143 BB_LV_SET_VALID_P (bb) = false;
4145 BB_LV_SET (bb) = get_regset_from_pool ();
4146 invalidate_av_set (bb);
4149 /* Free av set of BB. */
4151 free_av_set (basic_block bb)
4153 av_set_clear (&BB_AV_SET (bb));
4154 BB_AV_LEVEL (bb) = 0;
4157 /* Free data sets of BB. */
4159 free_data_sets (basic_block bb)
4165 /* Exchange lv sets of TO and FROM. */
4167 exchange_lv_sets (basic_block to, basic_block from)
4170 regset to_lv_set = BB_LV_SET (to);
4172 BB_LV_SET (to) = BB_LV_SET (from);
4173 BB_LV_SET (from) = to_lv_set;
4177 bool to_lv_set_valid_p = BB_LV_SET_VALID_P (to);
4179 BB_LV_SET_VALID_P (to) = BB_LV_SET_VALID_P (from);
4180 BB_LV_SET_VALID_P (from) = to_lv_set_valid_p;
4185 /* Exchange av sets of TO and FROM. */
4187 exchange_av_sets (basic_block to, basic_block from)
4190 av_set_t to_av_set = BB_AV_SET (to);
4192 BB_AV_SET (to) = BB_AV_SET (from);
4193 BB_AV_SET (from) = to_av_set;
4197 int to_av_level = BB_AV_LEVEL (to);
4199 BB_AV_LEVEL (to) = BB_AV_LEVEL (from);
4200 BB_AV_LEVEL (from) = to_av_level;
4204 /* Exchange data sets of TO and FROM. */
4206 exchange_data_sets (basic_block to, basic_block from)
4208 exchange_lv_sets (to, from);
4209 exchange_av_sets (to, from);
4212 /* Copy data sets of FROM to TO. */
4214 copy_data_sets (basic_block to, basic_block from)
4216 gcc_assert (!BB_LV_SET_VALID_P (to) && !BB_AV_SET_VALID_P (to));
4217 gcc_assert (BB_AV_SET (to) == NULL);
4219 BB_AV_LEVEL (to) = BB_AV_LEVEL (from);
4220 BB_LV_SET_VALID_P (to) = BB_LV_SET_VALID_P (from);
4222 if (BB_AV_SET_VALID_P (from))
4224 BB_AV_SET (to) = av_set_copy (BB_AV_SET (from));
4226 if (BB_LV_SET_VALID_P (from))
4228 gcc_assert (BB_LV_SET (to) != NULL);
4229 COPY_REG_SET (BB_LV_SET (to), BB_LV_SET (from));
4233 /* Return an av set for INSN, if any. */
4235 get_av_set (insn_t insn)
4239 gcc_assert (AV_SET_VALID_P (insn));
4241 if (sel_bb_head_p (insn))
4242 av_set = BB_AV_SET (BLOCK_FOR_INSN (insn));
4249 /* Implementation of AV_LEVEL () macro. Return AV_LEVEL () of INSN. */
4251 get_av_level (insn_t insn)
4255 gcc_assert (INSN_P (insn));
4257 if (sel_bb_head_p (insn))
4258 av_level = BB_AV_LEVEL (BLOCK_FOR_INSN (insn));
4260 av_level = INSN_WS_LEVEL (insn);
4267 /* Variables to work with control-flow graph. */
4269 /* The basic block that already has been processed by the sched_data_update (),
4270 but hasn't been in sel_add_bb () yet. */
4271 static VEC (basic_block, heap) *last_added_blocks = NULL;
4273 /* A pool for allocating successor infos. */
4276 /* A stack for saving succs_info structures. */
4277 struct succs_info *stack;
4282 /* Top of the stack. */
4285 /* Maximal value of the top. */
4289 /* Functions to work with control-flow graph. */
4291 /* Return basic block note of BB. */
4293 sel_bb_head (basic_block bb)
4297 if (bb == EXIT_BLOCK_PTR)
4299 gcc_assert (exit_insn != NULL_RTX);
4306 note = bb_note (bb);
4307 head = next_nonnote_insn (note);
4309 if (head && (BARRIER_P (head) || BLOCK_FOR_INSN (head) != bb))
4316 /* Return true if INSN is a basic block header. */
4318 sel_bb_head_p (insn_t insn)
4320 return sel_bb_head (BLOCK_FOR_INSN (insn)) == insn;
4323 /* Return last insn of BB. */
4325 sel_bb_end (basic_block bb)
4327 if (sel_bb_empty_p (bb))
4330 gcc_assert (bb != EXIT_BLOCK_PTR);
4335 /* Return true if INSN is the last insn in its basic block. */
4337 sel_bb_end_p (insn_t insn)
4339 return insn == sel_bb_end (BLOCK_FOR_INSN (insn));
4342 /* Return true if BB consist of single NOTE_INSN_BASIC_BLOCK. */
4344 sel_bb_empty_p (basic_block bb)
4346 return sel_bb_head (bb) == NULL;
4349 /* True when BB belongs to the current scheduling region. */
4351 in_current_region_p (basic_block bb)
4353 if (bb->index < NUM_FIXED_BLOCKS)
4356 return CONTAINING_RGN (bb->index) == CONTAINING_RGN (BB_TO_BLOCK (0));
4359 /* Return the block which is a fallthru bb of a conditional jump JUMP. */
4361 fallthru_bb_of_jump (rtx jump)
4366 if (any_uncondjump_p (jump))
4367 return single_succ (BLOCK_FOR_INSN (jump));
4369 if (!any_condjump_p (jump))
4372 /* A basic block that ends with a conditional jump may still have one successor
4373 (and be followed by a barrier), we are not interested. */
4374 if (single_succ_p (BLOCK_FOR_INSN (jump)))
4377 return FALLTHRU_EDGE (BLOCK_FOR_INSN (jump))->dest;
4380 /* Remove all notes from BB. */
4382 init_bb (basic_block bb)
4384 remove_notes (bb_note (bb), BB_END (bb));
4385 BB_NOTE_LIST (bb) = note_list;
4389 sel_init_bbs (bb_vec_t bbs, basic_block bb)
4391 const struct sched_scan_info_def ssi =
4393 extend_bb_info, /* extend_bb */
4394 init_bb, /* init_bb */
4395 NULL, /* extend_insn */
4396 NULL /* init_insn */
4399 sched_scan (&ssi, bbs, bb, new_insns, NULL);
4402 /* Restore notes for the whole region. */
4404 sel_restore_notes (void)
4409 for (bb = 0; bb < current_nr_blocks; bb++)
4411 basic_block first, last;
4413 first = EBB_FIRST_BB (bb);
4414 last = EBB_LAST_BB (bb)->next_bb;
4418 note_list = BB_NOTE_LIST (first);
4419 restore_other_notes (NULL, first);
4420 BB_NOTE_LIST (first) = NULL_RTX;
4422 FOR_BB_INSNS (first, insn)
4424 reemit_notes (insn);
4426 first = first->next_bb;
4428 while (first != last);
4432 /* Free per-bb data structures. */
4434 sel_finish_bbs (void)
4436 sel_restore_notes ();
4438 /* Remove current loop preheader from this loop. */
4439 if (current_loop_nest)
4440 sel_remove_loop_preheader ();
4442 finish_region_bb_info ();
4445 /* Return true if INSN has a single successor of type FLAGS. */
4447 sel_insn_has_single_succ_p (insn_t insn, int flags)
4451 bool first_p = true;
4453 FOR_EACH_SUCC_1 (succ, si, insn, flags)
4464 /* Allocate successor's info. */
4465 static struct succs_info *
4466 alloc_succs_info (void)
4468 if (succs_info_pool.top == succs_info_pool.max_top)
4472 if (++succs_info_pool.max_top >= succs_info_pool.size)
4475 i = ++succs_info_pool.top;
4476 succs_info_pool.stack[i].succs_ok = VEC_alloc (rtx, heap, 10);
4477 succs_info_pool.stack[i].succs_other = VEC_alloc (rtx, heap, 10);
4478 succs_info_pool.stack[i].probs_ok = VEC_alloc (int, heap, 10);
4481 succs_info_pool.top++;
4483 return &succs_info_pool.stack[succs_info_pool.top];
4486 /* Free successor's info. */
4488 free_succs_info (struct succs_info * sinfo)
4490 gcc_assert (succs_info_pool.top >= 0
4491 && &succs_info_pool.stack[succs_info_pool.top] == sinfo);
4492 succs_info_pool.top--;
4494 /* Clear stale info. */
4495 VEC_block_remove (rtx, sinfo->succs_ok,
4496 0, VEC_length (rtx, sinfo->succs_ok));
4497 VEC_block_remove (rtx, sinfo->succs_other,
4498 0, VEC_length (rtx, sinfo->succs_other));
4499 VEC_block_remove (int, sinfo->probs_ok,
4500 0, VEC_length (int, sinfo->probs_ok));
4501 sinfo->all_prob = 0;
4502 sinfo->succs_ok_n = 0;
4503 sinfo->all_succs_n = 0;
4506 /* Compute successor info for INSN. FLAGS are the flags passed
4507 to the FOR_EACH_SUCC_1 iterator. */
4509 compute_succs_info (insn_t insn, short flags)
4513 struct succs_info *sinfo = alloc_succs_info ();
4515 /* Traverse *all* successors and decide what to do with each. */
4516 FOR_EACH_SUCC_1 (succ, si, insn, SUCCS_ALL)
4518 /* FIXME: this doesn't work for skipping to loop exits, as we don't
4519 perform code motion through inner loops. */
4520 short current_flags = si.current_flags & ~SUCCS_SKIP_TO_LOOP_EXITS;
4522 if (current_flags & flags)
4524 VEC_safe_push (rtx, heap, sinfo->succs_ok, succ);
4525 VEC_safe_push (int, heap, sinfo->probs_ok,
4526 /* FIXME: Improve calculation when skipping
4527 inner loop to exits. */
4529 ? si.e1->probability
4530 : REG_BR_PROB_BASE));
4531 sinfo->succs_ok_n++;
4534 VEC_safe_push (rtx, heap, sinfo->succs_other, succ);
4536 /* Compute all_prob. */
4538 sinfo->all_prob = REG_BR_PROB_BASE;
4540 sinfo->all_prob += si.e1->probability;
4542 sinfo->all_succs_n++;
4548 /* Return the predecessors of BB in PREDS and their number in N.
4549 Empty blocks are skipped. SIZE is used to allocate PREDS. */
4551 cfg_preds_1 (basic_block bb, insn_t **preds, int *n, int *size)
4556 gcc_assert (BLOCK_TO_BB (bb->index) != 0);
4558 FOR_EACH_EDGE (e, ei, bb->preds)
4560 basic_block pred_bb = e->src;
4561 insn_t bb_end = BB_END (pred_bb);
4563 /* ??? This code is not supposed to walk out of a region. */
4564 gcc_assert (in_current_region_p (pred_bb));
4566 if (sel_bb_empty_p (pred_bb))
4567 cfg_preds_1 (pred_bb, preds, n, size);
4571 *preds = XRESIZEVEC (insn_t, *preds,
4572 (*size = 2 * *size + 1));
4573 (*preds)[(*n)++] = bb_end;
4577 gcc_assert (*n != 0);
4580 /* Find all predecessors of BB and record them in PREDS and their number
4581 in N. Empty blocks are skipped, and only normal (forward in-region)
4582 edges are processed. */
4584 cfg_preds (basic_block bb, insn_t **preds, int *n)
4590 cfg_preds_1 (bb, preds, n, &size);
4593 /* Returns true if we are moving INSN through join point. */
4595 sel_num_cfg_preds_gt_1 (insn_t insn)
4599 if (!sel_bb_head_p (insn) || INSN_BB (insn) == 0)
4602 bb = BLOCK_FOR_INSN (insn);
4606 if (EDGE_COUNT (bb->preds) > 1)
4609 gcc_assert (EDGE_PRED (bb, 0)->dest == bb);
4610 bb = EDGE_PRED (bb, 0)->src;
4612 if (!sel_bb_empty_p (bb))
4619 /* Returns true when BB should be the end of an ebb. Adapted from the
4620 code in sched-ebb.c. */
4622 bb_ends_ebb_p (basic_block bb)
4624 basic_block next_bb = bb_next_bb (bb);
4628 if (next_bb == EXIT_BLOCK_PTR
4629 || bitmap_bit_p (forced_ebb_heads, next_bb->index)
4630 || (LABEL_P (BB_HEAD (next_bb))
4631 /* NB: LABEL_NUSES () is not maintained outside of jump.c.
4632 Work around that. */
4633 && !single_pred_p (next_bb)))
4636 if (!in_current_region_p (next_bb))
4639 FOR_EACH_EDGE (e, ei, bb->succs)
4640 if ((e->flags & EDGE_FALLTHRU) != 0)
4642 gcc_assert (e->dest == next_bb);
4650 /* Returns true when INSN and SUCC are in the same EBB, given that SUCC is a
4651 successor of INSN. */
4653 in_same_ebb_p (insn_t insn, insn_t succ)
4655 basic_block ptr = BLOCK_FOR_INSN (insn);
4659 if (ptr == BLOCK_FOR_INSN (succ))
4662 if (bb_ends_ebb_p (ptr))
4665 ptr = bb_next_bb (ptr);
4672 /* Recomputes the reverse topological order for the function and
4673 saves it in REV_TOP_ORDER_INDEX. REV_TOP_ORDER_INDEX_LEN is also
4674 modified appropriately. */
4676 recompute_rev_top_order (void)
4681 if (!rev_top_order_index || rev_top_order_index_len < last_basic_block)
4683 rev_top_order_index_len = last_basic_block;
4684 rev_top_order_index = XRESIZEVEC (int, rev_top_order_index,
4685 rev_top_order_index_len);
4688 postorder = XNEWVEC (int, n_basic_blocks);
4690 n_blocks = post_order_compute (postorder, true, false);
4691 gcc_assert (n_basic_blocks == n_blocks);
4693 /* Build reverse function: for each basic block with BB->INDEX == K
4694 rev_top_order_index[K] is it's reverse topological sort number. */
4695 for (i = 0; i < n_blocks; i++)
4697 gcc_assert (postorder[i] < rev_top_order_index_len);
4698 rev_top_order_index[postorder[i]] = i;
4704 /* Clear all flags from insns in BB that could spoil its rescheduling. */
4706 clear_outdated_rtx_info (basic_block bb)
4710 FOR_BB_INSNS (bb, insn)
4713 SCHED_GROUP_P (insn) = 0;
4714 INSN_AFTER_STALL_P (insn) = 0;
4715 INSN_SCHED_TIMES (insn) = 0;
4716 EXPR_PRIORITY_ADJ (INSN_EXPR (insn)) = 0;
4718 /* We cannot use the changed caches, as previously we could ignore
4719 the LHS dependence due to enabled renaming and transform
4720 the expression, and currently we'll be unable to do this. */
4721 htab_empty (INSN_TRANSFORMED_INSNS (insn));
4725 /* Add BB_NOTE to the pool of available basic block notes. */
4727 return_bb_to_pool (basic_block bb)
4729 rtx note = bb_note (bb);
4731 gcc_assert (NOTE_BASIC_BLOCK (note) == bb
4732 && bb->aux == NULL);
4734 /* It turns out that current cfg infrastructure does not support
4735 reuse of basic blocks. Don't bother for now. */
4736 /*VEC_safe_push (rtx, heap, bb_note_pool, note);*/
4739 /* Get a bb_note from pool or return NULL_RTX if pool is empty. */
4741 get_bb_note_from_pool (void)
4743 if (VEC_empty (rtx, bb_note_pool))
4747 rtx note = VEC_pop (rtx, bb_note_pool);
4749 PREV_INSN (note) = NULL_RTX;
4750 NEXT_INSN (note) = NULL_RTX;
4756 /* Free bb_note_pool. */
4758 free_bb_note_pool (void)
4760 VEC_free (rtx, heap, bb_note_pool);
4763 /* Setup scheduler pool and successor structure. */
4765 alloc_sched_pools (void)
4769 succs_size = MAX_WS + 1;
4770 succs_info_pool.stack = XCNEWVEC (struct succs_info, succs_size);
4771 succs_info_pool.size = succs_size;
4772 succs_info_pool.top = -1;
4773 succs_info_pool.max_top = -1;
4775 sched_lists_pool = create_alloc_pool ("sel-sched-lists",
4776 sizeof (struct _list_node), 500);
4779 /* Free the pools. */
4781 free_sched_pools (void)
4785 free_alloc_pool (sched_lists_pool);
4786 gcc_assert (succs_info_pool.top == -1);
4787 for (i = 0; i < succs_info_pool.max_top; i++)
4789 VEC_free (rtx, heap, succs_info_pool.stack[i].succs_ok);
4790 VEC_free (rtx, heap, succs_info_pool.stack[i].succs_other);
4791 VEC_free (int, heap, succs_info_pool.stack[i].probs_ok);
4793 free (succs_info_pool.stack);
4797 /* Returns a position in RGN where BB can be inserted retaining
4798 topological order. */
4800 find_place_to_insert_bb (basic_block bb, int rgn)
4802 bool has_preds_outside_rgn = false;
4806 /* Find whether we have preds outside the region. */
4807 FOR_EACH_EDGE (e, ei, bb->preds)
4808 if (!in_current_region_p (e->src))
4810 has_preds_outside_rgn = true;
4814 /* Recompute the top order -- needed when we have > 1 pred
4815 and in case we don't have preds outside. */
4816 if (flag_sel_sched_pipelining_outer_loops
4817 && (has_preds_outside_rgn || EDGE_COUNT (bb->preds) > 1))
4819 int i, bbi = bb->index, cur_bbi;
4821 recompute_rev_top_order ();
4822 for (i = RGN_NR_BLOCKS (rgn) - 1; i >= 0; i--)
4824 cur_bbi = BB_TO_BLOCK (i);
4825 if (rev_top_order_index[bbi]
4826 < rev_top_order_index[cur_bbi])
4830 /* We skipped the right block, so we increase i. We accomodate
4831 it for increasing by step later, so we decrease i. */
4834 else if (has_preds_outside_rgn)
4836 /* This is the case when we generate an extra empty block
4837 to serve as region head during pipelining. */
4838 e = EDGE_SUCC (bb, 0);
4839 gcc_assert (EDGE_COUNT (bb->succs) == 1
4840 && in_current_region_p (EDGE_SUCC (bb, 0)->dest)
4841 && (BLOCK_TO_BB (e->dest->index) == 0));
4845 /* We don't have preds outside the region. We should have
4846 the only pred, because the multiple preds case comes from
4847 the pipelining of outer loops, and that is handled above.
4848 Just take the bbi of this single pred. */
4849 if (EDGE_COUNT (bb->succs) > 0)
4853 gcc_assert (EDGE_COUNT (bb->preds) == 1);
4855 pred_bbi = EDGE_PRED (bb, 0)->src->index;
4856 return BLOCK_TO_BB (pred_bbi);
4859 /* BB has no successors. It is safe to put it in the end. */
4860 return current_nr_blocks - 1;
4863 /* Deletes an empty basic block freeing its data. */
4865 delete_and_free_basic_block (basic_block bb)
4867 gcc_assert (sel_bb_empty_p (bb));
4872 bitmap_clear_bit (blocks_to_reschedule, bb->index);
4874 /* Can't assert av_set properties because we use sel_aremove_bb
4875 when removing loop preheader from the region. At the point of
4876 removing the preheader we already have deallocated sel_region_bb_info. */
4877 gcc_assert (BB_LV_SET (bb) == NULL
4878 && !BB_LV_SET_VALID_P (bb)
4879 && BB_AV_LEVEL (bb) == 0
4880 && BB_AV_SET (bb) == NULL);
4882 delete_basic_block (bb);
4885 /* Add BB to the current region and update the region data. */
4887 add_block_to_current_region (basic_block bb)
4889 int i, pos, bbi = -2, rgn;
4891 rgn = CONTAINING_RGN (BB_TO_BLOCK (0));
4892 bbi = find_place_to_insert_bb (bb, rgn);
4894 pos = RGN_BLOCKS (rgn) + bbi;
4896 gcc_assert (RGN_HAS_REAL_EBB (rgn) == 0
4897 && ebb_head[bbi] == pos);
4899 /* Make a place for the new block. */
4902 for (i = RGN_BLOCKS (rgn + 1) - 1; i >= pos; i--)
4903 BLOCK_TO_BB (rgn_bb_table[i])++;
4905 memmove (rgn_bb_table + pos + 1,
4907 (RGN_BLOCKS (nr_regions) - pos) * sizeof (*rgn_bb_table));
4909 /* Initialize data for BB. */
4910 rgn_bb_table[pos] = bb->index;
4911 BLOCK_TO_BB (bb->index) = bbi;
4912 CONTAINING_RGN (bb->index) = rgn;
4914 RGN_NR_BLOCKS (rgn)++;
4916 for (i = rgn + 1; i <= nr_regions; i++)
4920 /* Remove BB from the current region and update the region data. */
4922 remove_bb_from_region (basic_block bb)
4924 int i, pos, bbi = -2, rgn;
4926 rgn = CONTAINING_RGN (BB_TO_BLOCK (0));
4927 bbi = BLOCK_TO_BB (bb->index);
4928 pos = RGN_BLOCKS (rgn) + bbi;
4930 gcc_assert (RGN_HAS_REAL_EBB (rgn) == 0
4931 && ebb_head[bbi] == pos);
4933 for (i = RGN_BLOCKS (rgn + 1) - 1; i >= pos; i--)
4934 BLOCK_TO_BB (rgn_bb_table[i])--;
4936 memmove (rgn_bb_table + pos,
4937 rgn_bb_table + pos + 1,
4938 (RGN_BLOCKS (nr_regions) - pos) * sizeof (*rgn_bb_table));
4940 RGN_NR_BLOCKS (rgn)--;
4941 for (i = rgn + 1; i <= nr_regions; i++)
4945 /* Add BB to the current region and update all data. If BB is NULL, add all
4946 blocks from last_added_blocks vector. */
4948 sel_add_bb (basic_block bb)
4950 /* Extend luids so that new notes will receive zero luids. */
4951 sched_init_luids (NULL, NULL, NULL, NULL);
4953 sel_init_bbs (last_added_blocks, NULL);
4955 /* When bb is passed explicitly, the vector should contain
4956 the only element that equals to bb; otherwise, the vector
4957 should not be NULL. */
4958 gcc_assert (last_added_blocks != NULL);
4962 gcc_assert (VEC_length (basic_block, last_added_blocks) == 1
4963 && VEC_index (basic_block,
4964 last_added_blocks, 0) == bb);
4965 add_block_to_current_region (bb);
4967 /* We associate creating/deleting data sets with the first insn
4968 appearing / disappearing in the bb. */
4969 if (!sel_bb_empty_p (bb) && BB_LV_SET (bb) == NULL)
4970 create_initial_data_sets (bb);
4972 VEC_free (basic_block, heap, last_added_blocks);
4975 /* BB is NULL - process LAST_ADDED_BLOCKS instead. */
4978 basic_block temp_bb = NULL;
4981 VEC_iterate (basic_block, last_added_blocks, i, bb); i++)
4983 add_block_to_current_region (bb);
4987 /* We need to fetch at least one bb so we know the region
4989 gcc_assert (temp_bb != NULL);
4992 VEC_free (basic_block, heap, last_added_blocks);
4995 rgn_setup_region (CONTAINING_RGN (bb->index));
4998 /* Remove BB from the current region and update all data.
4999 If REMOVE_FROM_CFG_PBB is true, also remove the block cfom cfg. */
5001 sel_remove_bb (basic_block bb, bool remove_from_cfg_p)
5003 unsigned idx = bb->index;
5005 gcc_assert (bb != NULL && BB_NOTE_LIST (bb) == NULL_RTX);
5007 remove_bb_from_region (bb);
5008 return_bb_to_pool (bb);
5009 bitmap_clear_bit (blocks_to_reschedule, idx);
5011 if (remove_from_cfg_p)
5013 basic_block succ = single_succ (bb);
5014 delete_and_free_basic_block (bb);
5015 set_immediate_dominator (CDI_DOMINATORS, succ,
5016 recompute_dominator (CDI_DOMINATORS, succ));
5019 rgn_setup_region (CONTAINING_RGN (idx));
5022 /* Concatenate info of EMPTY_BB to info of MERGE_BB. */
5024 move_bb_info (basic_block merge_bb, basic_block empty_bb)
5026 gcc_assert (in_current_region_p (merge_bb));
5028 concat_note_lists (BB_NOTE_LIST (empty_bb),
5029 &BB_NOTE_LIST (merge_bb));
5030 BB_NOTE_LIST (empty_bb) = NULL_RTX;
5034 /* Remove EMPTY_BB. If REMOVE_FROM_CFG_P is false, remove EMPTY_BB from
5035 region, but keep it in CFG. */
5037 remove_empty_bb (basic_block empty_bb, bool remove_from_cfg_p)
5039 /* The block should contain just a note or a label.
5040 We try to check whether it is unused below. */
5041 gcc_assert (BB_HEAD (empty_bb) == BB_END (empty_bb)
5042 || LABEL_P (BB_HEAD (empty_bb)));
5044 /* If basic block has predecessors or successors, redirect them. */
5045 if (remove_from_cfg_p
5046 && (EDGE_COUNT (empty_bb->preds) > 0
5047 || EDGE_COUNT (empty_bb->succs) > 0))
5052 /* We need to init PRED and SUCC before redirecting edges. */
5053 if (EDGE_COUNT (empty_bb->preds) > 0)
5057 gcc_assert (EDGE_COUNT (empty_bb->preds) == 1);
5059 e = EDGE_PRED (empty_bb, 0);
5060 gcc_assert (e->src == empty_bb->prev_bb
5061 && (e->flags & EDGE_FALLTHRU));
5063 pred = empty_bb->prev_bb;
5068 if (EDGE_COUNT (empty_bb->succs) > 0)
5070 /* We do not check fallthruness here as above, because
5071 after removing a jump the edge may actually be not fallthru. */
5072 gcc_assert (EDGE_COUNT (empty_bb->succs) == 1);
5073 succ = EDGE_SUCC (empty_bb, 0)->dest;
5078 if (EDGE_COUNT (empty_bb->preds) > 0 && succ != NULL)
5080 edge e = EDGE_PRED (empty_bb, 0);
5082 if (e->flags & EDGE_FALLTHRU)
5083 redirect_edge_succ_nodup (e, succ);
5085 sel_redirect_edge_and_branch (EDGE_PRED (empty_bb, 0), succ);
5088 if (EDGE_COUNT (empty_bb->succs) > 0 && pred != NULL)
5090 edge e = EDGE_SUCC (empty_bb, 0);
5092 if (find_edge (pred, e->dest) == NULL)
5093 redirect_edge_pred (e, pred);
5097 /* Finish removing. */
5098 sel_remove_bb (empty_bb, remove_from_cfg_p);
5101 /* An implementation of create_basic_block hook, which additionally updates
5102 per-bb data structures. */
5104 sel_create_basic_block (void *headp, void *endp, basic_block after)
5109 gcc_assert (flag_sel_sched_pipelining_outer_loops
5110 || last_added_blocks == NULL);
5112 new_bb_note = get_bb_note_from_pool ();
5114 if (new_bb_note == NULL_RTX)
5115 new_bb = orig_cfg_hooks.create_basic_block (headp, endp, after);
5118 new_bb = create_basic_block_structure ((rtx) headp, (rtx) endp,
5119 new_bb_note, after);
5123 VEC_safe_push (basic_block, heap, last_added_blocks, new_bb);
5128 /* Implement sched_init_only_bb (). */
5130 sel_init_only_bb (basic_block bb, basic_block after)
5132 gcc_assert (after == NULL);
5135 rgn_make_new_region_out_of_new_block (bb);
5138 /* Update the latch when we've splitted or merged it from FROM block to TO.
5139 This should be checked for all outer loops, too. */
5141 change_loops_latches (basic_block from, basic_block to)
5143 gcc_assert (from != to);
5145 if (current_loop_nest)
5149 for (loop = current_loop_nest; loop; loop = loop_outer (loop))
5150 if (considered_for_pipelining_p (loop) && loop->latch == from)
5152 gcc_assert (loop == current_loop_nest);
5154 gcc_assert (loop_latch_edge (loop));
5159 /* Splits BB on two basic blocks, adding it to the region and extending
5160 per-bb data structures. Returns the newly created bb. */
5162 sel_split_block (basic_block bb, rtx after)
5167 new_bb = sched_split_block_1 (bb, after);
5168 sel_add_bb (new_bb);
5170 /* This should be called after sel_add_bb, because this uses
5171 CONTAINING_RGN for the new block, which is not yet initialized.
5172 FIXME: this function may be a no-op now. */
5173 change_loops_latches (bb, new_bb);
5175 /* Update ORIG_BB_INDEX for insns moved into the new block. */
5176 FOR_BB_INSNS (new_bb, insn)
5178 EXPR_ORIG_BB_INDEX (INSN_EXPR (insn)) = new_bb->index;
5180 if (sel_bb_empty_p (bb))
5182 gcc_assert (!sel_bb_empty_p (new_bb));
5184 /* NEW_BB has data sets that need to be updated and BB holds
5185 data sets that should be removed. Exchange these data sets
5186 so that we won't lose BB's valid data sets. */
5187 exchange_data_sets (new_bb, bb);
5188 free_data_sets (bb);
5191 if (!sel_bb_empty_p (new_bb)
5192 && bitmap_bit_p (blocks_to_reschedule, bb->index))
5193 bitmap_set_bit (blocks_to_reschedule, new_bb->index);
5198 /* If BB ends with a jump insn whose ID is bigger then PREV_MAX_UID, return it.
5199 Otherwise returns NULL. */
5201 check_for_new_jump (basic_block bb, int prev_max_uid)
5205 end = sel_bb_end (bb);
5206 if (end && INSN_UID (end) >= prev_max_uid)
5211 /* Look for a new jump either in FROM_BB block or in newly created JUMP_BB block.
5212 New means having UID at least equal to PREV_MAX_UID. */
5214 find_new_jump (basic_block from, basic_block jump_bb, int prev_max_uid)
5218 /* Return immediately if no new insns were emitted. */
5219 if (get_max_uid () == prev_max_uid)
5222 /* Now check both blocks for new jumps. It will ever be only one. */
5223 if ((jump = check_for_new_jump (from, prev_max_uid)))
5227 && (jump = check_for_new_jump (jump_bb, prev_max_uid)))
5232 /* Splits E and adds the newly created basic block to the current region.
5233 Returns this basic block. */
5235 sel_split_edge (edge e)
5237 basic_block new_bb, src, other_bb = NULL;
5242 prev_max_uid = get_max_uid ();
5243 new_bb = split_edge (e);
5245 if (flag_sel_sched_pipelining_outer_loops
5246 && current_loop_nest)
5251 /* Some of the basic blocks might not have been added to the loop.
5252 Add them here, until this is fixed in force_fallthru. */
5254 VEC_iterate (basic_block, last_added_blocks, i, bb); i++)
5255 if (!bb->loop_father)
5257 add_bb_to_loop (bb, e->dest->loop_father);
5259 gcc_assert (!other_bb && (new_bb->index != bb->index));
5264 /* Add all last_added_blocks to the region. */
5267 jump = find_new_jump (src, new_bb, prev_max_uid);
5269 sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP);
5271 /* Put the correct lv set on this block. */
5272 if (other_bb && !sel_bb_empty_p (other_bb))
5273 compute_live (sel_bb_head (other_bb));
5278 /* Implement sched_create_empty_bb (). */
5280 sel_create_empty_bb (basic_block after)
5284 new_bb = sched_create_empty_bb_1 (after);
5286 /* We'll explicitly initialize NEW_BB via sel_init_only_bb () a bit
5288 gcc_assert (VEC_length (basic_block, last_added_blocks) == 1
5289 && VEC_index (basic_block, last_added_blocks, 0) == new_bb);
5291 VEC_free (basic_block, heap, last_added_blocks);
5295 /* Implement sched_create_recovery_block. ORIG_INSN is where block
5296 will be splitted to insert a check. */
5298 sel_create_recovery_block (insn_t orig_insn)
5300 basic_block first_bb, second_bb, recovery_block;
5301 basic_block before_recovery = NULL;
5304 first_bb = BLOCK_FOR_INSN (orig_insn);
5305 if (sel_bb_end_p (orig_insn))
5307 /* Avoid introducing an empty block while splitting. */
5308 gcc_assert (single_succ_p (first_bb));
5309 second_bb = single_succ (first_bb);
5312 second_bb = sched_split_block (first_bb, orig_insn);
5314 recovery_block = sched_create_recovery_block (&before_recovery);
5315 if (before_recovery)
5316 copy_lv_set_from (before_recovery, EXIT_BLOCK_PTR);
5318 gcc_assert (sel_bb_empty_p (recovery_block));
5319 sched_create_recovery_edges (first_bb, recovery_block, second_bb);
5320 if (current_loops != NULL)
5321 add_bb_to_loop (recovery_block, first_bb->loop_father);
5323 sel_add_bb (recovery_block);
5325 jump = BB_END (recovery_block);
5326 gcc_assert (sel_bb_head (recovery_block) == jump);
5327 sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP);
5329 return recovery_block;
5332 /* Merge basic block B into basic block A. */
5334 sel_merge_blocks (basic_block a, basic_block b)
5336 gcc_assert (sel_bb_empty_p (b)
5337 && EDGE_COUNT (b->preds) == 1
5338 && EDGE_PRED (b, 0)->src == b->prev_bb);
5340 move_bb_info (b->prev_bb, b);
5341 remove_empty_bb (b, false);
5342 merge_blocks (a, b);
5343 change_loops_latches (b, a);
5346 /* A wrapper for redirect_edge_and_branch_force, which also initializes
5347 data structures for possibly created bb and insns. Returns the newly
5348 added bb or NULL, when a bb was not needed. */
5350 sel_redirect_edge_and_branch_force (edge e, basic_block to)
5352 basic_block jump_bb, src, orig_dest = e->dest;
5356 /* This function is now used only for bookkeeping code creation, where
5357 we'll never get the single pred of orig_dest block and thus will not
5358 hit unreachable blocks when updating dominator info. */
5359 gcc_assert (!sel_bb_empty_p (e->src)
5360 && !single_pred_p (orig_dest));
5363 prev_max_uid = get_max_uid ();
5364 jump_bb = redirect_edge_and_branch_force (e, to);
5366 if (jump_bb != NULL)
5367 sel_add_bb (jump_bb);
5369 /* This function could not be used to spoil the loop structure by now,
5370 thus we don't care to update anything. But check it to be sure. */
5371 if (current_loop_nest
5373 gcc_assert (loop_latch_edge (current_loop_nest));
5375 jump = find_new_jump (src, jump_bb, prev_max_uid);
5377 sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP);
5378 set_immediate_dominator (CDI_DOMINATORS, to,
5379 recompute_dominator (CDI_DOMINATORS, to));
5380 set_immediate_dominator (CDI_DOMINATORS, orig_dest,
5381 recompute_dominator (CDI_DOMINATORS, orig_dest));
5384 /* A wrapper for redirect_edge_and_branch. Return TRUE if blocks connected by
5385 redirected edge are in reverse topological order. */
5387 sel_redirect_edge_and_branch (edge e, basic_block to)
5390 basic_block src, orig_dest = e->dest;
5394 bool recompute_toporder_p = false;
5395 bool maybe_unreachable = single_pred_p (orig_dest);
5397 latch_edge_p = (pipelining_p
5398 && current_loop_nest
5399 && e == loop_latch_edge (current_loop_nest));
5402 prev_max_uid = get_max_uid ();
5404 redirected = redirect_edge_and_branch (e, to);
5406 gcc_assert (redirected && last_added_blocks == NULL);
5408 /* When we've redirected a latch edge, update the header. */
5411 current_loop_nest->header = to;
5412 gcc_assert (loop_latch_edge (current_loop_nest));
5415 /* In rare situations, the topological relation between the blocks connected
5416 by the redirected edge can change (see PR42245 for an example). Update
5417 block_to_bb/bb_to_block. */
5418 if (CONTAINING_RGN (e->src->index) == CONTAINING_RGN (to->index)
5419 && BLOCK_TO_BB (e->src->index) > BLOCK_TO_BB (to->index))
5420 recompute_toporder_p = true;
5422 jump = find_new_jump (src, NULL, prev_max_uid);
5424 sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP);
5426 /* Only update dominator info when we don't have unreachable blocks.
5427 Otherwise we'll update in maybe_tidy_empty_bb. */
5428 if (!maybe_unreachable)
5430 set_immediate_dominator (CDI_DOMINATORS, to,
5431 recompute_dominator (CDI_DOMINATORS, to));
5432 set_immediate_dominator (CDI_DOMINATORS, orig_dest,
5433 recompute_dominator (CDI_DOMINATORS, orig_dest));
5435 return recompute_toporder_p;
5438 /* This variable holds the cfg hooks used by the selective scheduler. */
5439 static struct cfg_hooks sel_cfg_hooks;
5441 /* Register sel-sched cfg hooks. */
5443 sel_register_cfg_hooks (void)
5445 sched_split_block = sel_split_block;
5447 orig_cfg_hooks = get_cfg_hooks ();
5448 sel_cfg_hooks = orig_cfg_hooks;
5450 sel_cfg_hooks.create_basic_block = sel_create_basic_block;
5452 set_cfg_hooks (sel_cfg_hooks);
5454 sched_init_only_bb = sel_init_only_bb;
5455 sched_split_block = sel_split_block;
5456 sched_create_empty_bb = sel_create_empty_bb;
5459 /* Unregister sel-sched cfg hooks. */
5461 sel_unregister_cfg_hooks (void)
5463 sched_create_empty_bb = NULL;
5464 sched_split_block = NULL;
5465 sched_init_only_bb = NULL;
5467 set_cfg_hooks (orig_cfg_hooks);
5471 /* Emit an insn rtx based on PATTERN. If a jump insn is wanted,
5472 LABEL is where this jump should be directed. */
5474 create_insn_rtx_from_pattern (rtx pattern, rtx label)
5478 gcc_assert (!INSN_P (pattern));
5482 if (label == NULL_RTX)
5483 insn_rtx = emit_insn (pattern);
5486 insn_rtx = emit_jump_insn (pattern);
5487 JUMP_LABEL (insn_rtx) = label;
5488 ++LABEL_NUSES (label);
5493 sched_init_luids (NULL, NULL, NULL, NULL);
5494 sched_extend_target ();
5495 sched_deps_init (false);
5497 /* Initialize INSN_CODE now. */
5498 recog_memoized (insn_rtx);
5502 /* Create a new vinsn for INSN_RTX. FORCE_UNIQUE_P is true when the vinsn
5503 must not be clonable. */
5505 create_vinsn_from_insn_rtx (rtx insn_rtx, bool force_unique_p)
5507 gcc_assert (INSN_P (insn_rtx) && !INSN_IN_STREAM_P (insn_rtx));
5509 /* If VINSN_TYPE is not USE, retain its uniqueness. */
5510 return vinsn_create (insn_rtx, force_unique_p);
5513 /* Create a copy of INSN_RTX. */
5515 create_copy_of_insn_rtx (rtx insn_rtx)
5519 gcc_assert (NONJUMP_INSN_P (insn_rtx));
5521 res = create_insn_rtx_from_pattern (copy_rtx (PATTERN (insn_rtx)),
5526 /* Change vinsn field of EXPR to hold NEW_VINSN. */
5528 change_vinsn_in_expr (expr_t expr, vinsn_t new_vinsn)
5530 vinsn_detach (EXPR_VINSN (expr));
5532 EXPR_VINSN (expr) = new_vinsn;
5533 vinsn_attach (new_vinsn);
5536 /* Helpers for global init. */
5537 /* This structure is used to be able to call existing bundling mechanism
5538 and calculate insn priorities. */
5539 static struct haifa_sched_info sched_sel_haifa_sched_info =
5541 NULL, /* init_ready_list */
5542 NULL, /* can_schedule_ready_p */
5543 NULL, /* schedule_more_p */
5544 NULL, /* new_ready */
5545 NULL, /* rgn_rank */
5546 sel_print_insn, /* rgn_print_insn */
5547 contributes_to_priority,
5553 NULL, /* add_remove_insn */
5554 NULL, /* begin_schedule_ready */
5555 NULL, /* advance_target_bb */
5559 /* Setup special insns used in the scheduler. */
5561 setup_nop_and_exit_insns (void)
5563 gcc_assert (nop_pattern == NULL_RTX
5564 && exit_insn == NULL_RTX);
5566 nop_pattern = gen_nop ();
5569 emit_insn (nop_pattern);
5570 exit_insn = get_insns ();
5572 set_block_for_insn (exit_insn, EXIT_BLOCK_PTR);
5575 /* Free special insns used in the scheduler. */
5577 free_nop_and_exit_insns (void)
5579 exit_insn = NULL_RTX;
5580 nop_pattern = NULL_RTX;
5583 /* Setup a special vinsn used in new insns initialization. */
5585 setup_nop_vinsn (void)
5587 nop_vinsn = vinsn_create (exit_insn, false);
5588 vinsn_attach (nop_vinsn);
5591 /* Free a special vinsn used in new insns initialization. */
5593 free_nop_vinsn (void)
5595 gcc_assert (VINSN_COUNT (nop_vinsn) == 1);
5596 vinsn_detach (nop_vinsn);
5600 /* Call a set_sched_flags hook. */
5602 sel_set_sched_flags (void)
5604 /* ??? This means that set_sched_flags were called, and we decided to
5605 support speculation. However, set_sched_flags also modifies flags
5606 on current_sched_info, doing this only at global init. And we
5607 sometimes change c_s_i later. So put the correct flags again. */
5608 if (spec_info && targetm.sched.set_sched_flags)
5609 targetm.sched.set_sched_flags (spec_info);
5612 /* Setup pointers to global sched info structures. */
5614 sel_setup_sched_infos (void)
5616 rgn_setup_common_sched_info ();
5618 memcpy (&sel_common_sched_info, common_sched_info,
5619 sizeof (sel_common_sched_info));
5621 sel_common_sched_info.fix_recovery_cfg = NULL;
5622 sel_common_sched_info.add_block = NULL;
5623 sel_common_sched_info.estimate_number_of_insns
5624 = sel_estimate_number_of_insns;
5625 sel_common_sched_info.luid_for_non_insn = sel_luid_for_non_insn;
5626 sel_common_sched_info.sched_pass_id = SCHED_SEL_PASS;
5628 common_sched_info = &sel_common_sched_info;
5630 current_sched_info = &sched_sel_haifa_sched_info;
5631 current_sched_info->sched_max_insns_priority =
5632 get_rgn_sched_max_insns_priority ();
5634 sel_set_sched_flags ();
5638 /* Adds basic block BB to region RGN at the position *BB_ORD_INDEX,
5639 *BB_ORD_INDEX after that is increased. */
5641 sel_add_block_to_region (basic_block bb, int *bb_ord_index, int rgn)
5643 RGN_NR_BLOCKS (rgn) += 1;
5644 RGN_DONT_CALC_DEPS (rgn) = 0;
5645 RGN_HAS_REAL_EBB (rgn) = 0;
5646 CONTAINING_RGN (bb->index) = rgn;
5647 BLOCK_TO_BB (bb->index) = *bb_ord_index;
5648 rgn_bb_table[RGN_BLOCKS (rgn) + *bb_ord_index] = bb->index;
5651 /* FIXME: it is true only when not scheduling ebbs. */
5652 RGN_BLOCKS (rgn + 1) = RGN_BLOCKS (rgn) + RGN_NR_BLOCKS (rgn);
5655 /* Functions to support pipelining of outer loops. */
5657 /* Creates a new empty region and returns it's number. */
5659 sel_create_new_region (void)
5661 int new_rgn_number = nr_regions;
5663 RGN_NR_BLOCKS (new_rgn_number) = 0;
5665 /* FIXME: This will work only when EBBs are not created. */
5666 if (new_rgn_number != 0)
5667 RGN_BLOCKS (new_rgn_number) = RGN_BLOCKS (new_rgn_number - 1) +
5668 RGN_NR_BLOCKS (new_rgn_number - 1);
5670 RGN_BLOCKS (new_rgn_number) = 0;
5672 /* Set the blocks of the next region so the other functions may
5673 calculate the number of blocks in the region. */
5674 RGN_BLOCKS (new_rgn_number + 1) = RGN_BLOCKS (new_rgn_number) +
5675 RGN_NR_BLOCKS (new_rgn_number);
5679 return new_rgn_number;
5682 /* If X has a smaller topological sort number than Y, returns -1;
5683 if greater, returns 1. */
5685 bb_top_order_comparator (const void *x, const void *y)
5687 basic_block bb1 = *(const basic_block *) x;
5688 basic_block bb2 = *(const basic_block *) y;
5690 gcc_assert (bb1 == bb2
5691 || rev_top_order_index[bb1->index]
5692 != rev_top_order_index[bb2->index]);
5694 /* It's a reverse topological order in REV_TOP_ORDER_INDEX, so
5695 bbs with greater number should go earlier. */
5696 if (rev_top_order_index[bb1->index] > rev_top_order_index[bb2->index])
5702 /* Create a region for LOOP and return its number. If we don't want
5703 to pipeline LOOP, return -1. */
5705 make_region_from_loop (struct loop *loop)
5708 int new_rgn_number = -1;
5711 /* Basic block index, to be assigned to BLOCK_TO_BB. */
5712 int bb_ord_index = 0;
5713 basic_block *loop_blocks;
5714 basic_block preheader_block;
5717 > (unsigned) PARAM_VALUE (PARAM_MAX_PIPELINE_REGION_BLOCKS))
5720 /* Don't pipeline loops whose latch belongs to some of its inner loops. */
5721 for (inner = loop->inner; inner; inner = inner->inner)
5722 if (flow_bb_inside_loop_p (inner, loop->latch))
5725 loop->ninsns = num_loop_insns (loop);
5726 if ((int) loop->ninsns > PARAM_VALUE (PARAM_MAX_PIPELINE_REGION_INSNS))
5729 loop_blocks = get_loop_body_in_custom_order (loop, bb_top_order_comparator);
5731 for (i = 0; i < loop->num_nodes; i++)
5732 if (loop_blocks[i]->flags & BB_IRREDUCIBLE_LOOP)
5738 preheader_block = loop_preheader_edge (loop)->src;
5739 gcc_assert (preheader_block);
5740 gcc_assert (loop_blocks[0] == loop->header);
5742 new_rgn_number = sel_create_new_region ();
5744 sel_add_block_to_region (preheader_block, &bb_ord_index, new_rgn_number);
5745 SET_BIT (bbs_in_loop_rgns, preheader_block->index);
5747 for (i = 0; i < loop->num_nodes; i++)
5749 /* Add only those blocks that haven't been scheduled in the inner loop.
5750 The exception is the basic blocks with bookkeeping code - they should
5751 be added to the region (and they actually don't belong to the loop
5752 body, but to the region containing that loop body). */
5754 gcc_assert (new_rgn_number >= 0);
5756 if (! TEST_BIT (bbs_in_loop_rgns, loop_blocks[i]->index))
5758 sel_add_block_to_region (loop_blocks[i], &bb_ord_index,
5760 SET_BIT (bbs_in_loop_rgns, loop_blocks[i]->index);
5765 MARK_LOOP_FOR_PIPELINING (loop);
5767 return new_rgn_number;
5770 /* Create a new region from preheader blocks LOOP_BLOCKS. */
5772 make_region_from_loop_preheader (VEC(basic_block, heap) **loop_blocks)
5775 int new_rgn_number = -1;
5778 /* Basic block index, to be assigned to BLOCK_TO_BB. */
5779 int bb_ord_index = 0;
5781 new_rgn_number = sel_create_new_region ();
5783 for (i = 0; VEC_iterate (basic_block, *loop_blocks, i, bb); i++)
5785 gcc_assert (new_rgn_number >= 0);
5787 sel_add_block_to_region (bb, &bb_ord_index, new_rgn_number);
5790 VEC_free (basic_block, heap, *loop_blocks);
5791 gcc_assert (*loop_blocks == NULL);
5795 /* Create region(s) from loop nest LOOP, such that inner loops will be
5796 pipelined before outer loops. Returns true when a region for LOOP
5799 make_regions_from_loop_nest (struct loop *loop)
5801 struct loop *cur_loop;
5804 /* Traverse all inner nodes of the loop. */
5805 for (cur_loop = loop->inner; cur_loop; cur_loop = cur_loop->next)
5806 if (! TEST_BIT (bbs_in_loop_rgns, cur_loop->header->index))
5809 /* At this moment all regular inner loops should have been pipelined.
5810 Try to create a region from this loop. */
5811 rgn_number = make_region_from_loop (loop);
5816 VEC_safe_push (loop_p, heap, loop_nests, loop);
5820 /* Initalize data structures needed. */
5822 sel_init_pipelining (void)
5824 /* Collect loop information to be used in outer loops pipelining. */
5825 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
5826 | LOOPS_HAVE_FALLTHRU_PREHEADERS
5827 | LOOPS_HAVE_RECORDED_EXITS
5828 | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS);
5829 current_loop_nest = NULL;
5831 bbs_in_loop_rgns = sbitmap_alloc (last_basic_block);
5832 sbitmap_zero (bbs_in_loop_rgns);
5834 recompute_rev_top_order ();
5837 /* Returns a struct loop for region RGN. */
5839 get_loop_nest_for_rgn (unsigned int rgn)
5841 /* Regions created with extend_rgns don't have corresponding loop nests,
5842 because they don't represent loops. */
5843 if (rgn < VEC_length (loop_p, loop_nests))
5844 return VEC_index (loop_p, loop_nests, rgn);
5849 /* True when LOOP was included into pipelining regions. */
5851 considered_for_pipelining_p (struct loop *loop)
5853 if (loop_depth (loop) == 0)
5856 /* Now, the loop could be too large or irreducible. Check whether its
5857 region is in LOOP_NESTS.
5858 We determine the region number of LOOP as the region number of its
5859 latch. We can't use header here, because this header could be
5860 just removed preheader and it will give us the wrong region number.
5861 Latch can't be used because it could be in the inner loop too. */
5862 if (LOOP_MARKED_FOR_PIPELINING_P (loop))
5864 int rgn = CONTAINING_RGN (loop->latch->index);
5866 gcc_assert ((unsigned) rgn < VEC_length (loop_p, loop_nests));
5873 /* Makes regions from the rest of the blocks, after loops are chosen
5876 make_regions_from_the_rest (void)
5888 /* Index in rgn_bb_table where to start allocating new regions. */
5889 cur_rgn_blocks = nr_regions ? RGN_BLOCKS (nr_regions) : 0;
5890 new_regions = nr_regions;
5892 /* Make regions from all the rest basic blocks - those that don't belong to
5893 any loop or belong to irreducible loops. Prepare the data structures
5896 /* LOOP_HDR[I] == -1 if I-th bb doesn't belong to any loop,
5897 LOOP_HDR[I] == LOOP_HDR[J] iff basic blocks I and J reside within the same
5899 loop_hdr = XNEWVEC (int, last_basic_block);
5900 degree = XCNEWVEC (int, last_basic_block);
5903 /* For each basic block that belongs to some loop assign the number
5904 of innermost loop it belongs to. */
5905 for (i = 0; i < last_basic_block; i++)
5910 if (bb->loop_father && !bb->loop_father->num == 0
5911 && !(bb->flags & BB_IRREDUCIBLE_LOOP))
5912 loop_hdr[bb->index] = bb->loop_father->num;
5915 /* For each basic block degree is calculated as the number of incoming
5916 edges, that are going out of bbs that are not yet scheduled.
5917 The basic blocks that are scheduled have degree value of zero. */
5920 degree[bb->index] = 0;
5922 if (!TEST_BIT (bbs_in_loop_rgns, bb->index))
5924 FOR_EACH_EDGE (e, ei, bb->preds)
5925 if (!TEST_BIT (bbs_in_loop_rgns, e->src->index))
5926 degree[bb->index]++;
5929 degree[bb->index] = -1;
5932 extend_rgns (degree, &cur_rgn_blocks, bbs_in_loop_rgns, loop_hdr);
5934 /* Any block that did not end up in a region is placed into a region
5937 if (degree[bb->index] >= 0)
5939 rgn_bb_table[cur_rgn_blocks] = bb->index;
5940 RGN_NR_BLOCKS (nr_regions) = 1;
5941 RGN_BLOCKS (nr_regions) = cur_rgn_blocks++;
5942 RGN_DONT_CALC_DEPS (nr_regions) = 0;
5943 RGN_HAS_REAL_EBB (nr_regions) = 0;
5944 CONTAINING_RGN (bb->index) = nr_regions++;
5945 BLOCK_TO_BB (bb->index) = 0;
5952 /* Free data structures used in pipelining of loops. */
5953 void sel_finish_pipelining (void)
5958 /* Release aux fields so we don't free them later by mistake. */
5959 FOR_EACH_LOOP (li, loop, 0)
5962 loop_optimizer_finalize ();
5964 VEC_free (loop_p, heap, loop_nests);
5966 free (rev_top_order_index);
5967 rev_top_order_index = NULL;
5970 /* This function replaces the find_rgns when
5971 FLAG_SEL_SCHED_PIPELINING_OUTER_LOOPS is set. */
5973 sel_find_rgns (void)
5975 sel_init_pipelining ();
5983 FOR_EACH_LOOP (li, loop, (flag_sel_sched_pipelining_outer_loops
5985 : LI_ONLY_INNERMOST))
5986 make_regions_from_loop_nest (loop);
5989 /* Make regions from all the rest basic blocks and schedule them.
5990 These blocks include blocks that don't belong to any loop or belong
5991 to irreducible loops. */
5992 make_regions_from_the_rest ();
5994 /* We don't need bbs_in_loop_rgns anymore. */
5995 sbitmap_free (bbs_in_loop_rgns);
5996 bbs_in_loop_rgns = NULL;
5999 /* Adds the preheader blocks from previous loop to current region taking
6000 it from LOOP_PREHEADER_BLOCKS (current_loop_nest).
6001 This function is only used with -fsel-sched-pipelining-outer-loops. */
6003 sel_add_loop_preheaders (void)
6007 VEC(basic_block, heap) *preheader_blocks
6008 = LOOP_PREHEADER_BLOCKS (current_loop_nest);
6011 VEC_iterate (basic_block, preheader_blocks, i, bb);
6014 VEC_safe_push (basic_block, heap, last_added_blocks, bb);
6018 VEC_free (basic_block, heap, preheader_blocks);
6021 /* While pipelining outer loops, returns TRUE if BB is a loop preheader.
6022 Please note that the function should also work when pipelining_p is
6023 false, because it is used when deciding whether we should or should
6024 not reschedule pipelined code. */
6026 sel_is_loop_preheader_p (basic_block bb)
6028 if (current_loop_nest)
6032 if (preheader_removed)
6035 /* Preheader is the first block in the region. */
6036 if (BLOCK_TO_BB (bb->index) == 0)
6039 /* We used to find a preheader with the topological information.
6040 Check that the above code is equivalent to what we did before. */
6042 if (in_current_region_p (current_loop_nest->header))
6043 gcc_assert (!(BLOCK_TO_BB (bb->index)
6044 < BLOCK_TO_BB (current_loop_nest->header->index)));
6046 /* Support the situation when the latch block of outer loop
6047 could be from here. */
6048 for (outer = loop_outer (current_loop_nest);
6050 outer = loop_outer (outer))
6051 if (considered_for_pipelining_p (outer) && outer->latch == bb)
6058 /* Checks whether JUMP leads to basic block DEST_BB and no other blocks. */
6060 jump_leads_only_to_bb_p (insn_t jump, basic_block dest_bb)
6062 basic_block jump_bb = BLOCK_FOR_INSN (jump);
6064 /* It is not jump, jump with side-effects or jump can lead to several
6066 if (!onlyjump_p (jump)
6067 || !any_uncondjump_p (jump))
6070 /* Several outgoing edges, abnormal edge or destination of jump is
6072 if (EDGE_COUNT (jump_bb->succs) != 1
6073 || EDGE_SUCC (jump_bb, 0)->flags & EDGE_ABNORMAL
6074 || EDGE_SUCC (jump_bb, 0)->dest != dest_bb)
6077 /* If not anything of the upper. */
6081 /* Removes the loop preheader from the current region and saves it in
6082 PREHEADER_BLOCKS of the father loop, so they will be added later to
6083 region that represents an outer loop. */
6085 sel_remove_loop_preheader (void)
6088 int cur_rgn = CONTAINING_RGN (BB_TO_BLOCK (0));
6090 bool all_empty_p = true;
6091 VEC(basic_block, heap) *preheader_blocks
6092 = LOOP_PREHEADER_BLOCKS (loop_outer (current_loop_nest));
6094 gcc_assert (current_loop_nest);
6095 old_len = VEC_length (basic_block, preheader_blocks);
6097 /* Add blocks that aren't within the current loop to PREHEADER_BLOCKS. */
6098 for (i = 0; i < RGN_NR_BLOCKS (cur_rgn); i++)
6100 bb = BASIC_BLOCK (BB_TO_BLOCK (i));
6102 /* If the basic block belongs to region, but doesn't belong to
6103 corresponding loop, then it should be a preheader. */
6104 if (sel_is_loop_preheader_p (bb))
6106 VEC_safe_push (basic_block, heap, preheader_blocks, bb);
6107 if (BB_END (bb) != bb_note (bb))
6108 all_empty_p = false;
6112 /* Remove these blocks only after iterating over the whole region. */
6113 for (i = VEC_length (basic_block, preheader_blocks) - 1;
6117 bb = VEC_index (basic_block, preheader_blocks, i);
6118 sel_remove_bb (bb, false);
6121 if (!considered_for_pipelining_p (loop_outer (current_loop_nest)))
6124 /* Immediately create new region from preheader. */
6125 make_region_from_loop_preheader (&preheader_blocks);
6128 /* If all preheader blocks are empty - dont create new empty region.
6129 Instead, remove them completely. */
6130 for (i = 0; VEC_iterate (basic_block, preheader_blocks, i, bb); i++)
6134 basic_block prev_bb = bb->prev_bb, next_bb = bb->next_bb;
6136 /* Redirect all incoming edges to next basic block. */
6137 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
6139 if (! (e->flags & EDGE_FALLTHRU))
6140 redirect_edge_and_branch (e, bb->next_bb);
6142 redirect_edge_succ (e, bb->next_bb);
6144 gcc_assert (BB_NOTE_LIST (bb) == NULL);
6145 delete_and_free_basic_block (bb);
6147 /* Check if after deleting preheader there is a nonconditional
6148 jump in PREV_BB that leads to the next basic block NEXT_BB.
6149 If it is so - delete this jump and clear data sets of its
6150 basic block if it becomes empty. */
6151 if (next_bb->prev_bb == prev_bb
6152 && prev_bb != ENTRY_BLOCK_PTR
6153 && jump_leads_only_to_bb_p (BB_END (prev_bb), next_bb))
6155 redirect_edge_and_branch (EDGE_SUCC (prev_bb, 0), next_bb);
6156 if (BB_END (prev_bb) == bb_note (prev_bb))
6157 free_data_sets (prev_bb);
6160 set_immediate_dominator (CDI_DOMINATORS, next_bb,
6161 recompute_dominator (CDI_DOMINATORS,
6165 VEC_free (basic_block, heap, preheader_blocks);
6168 /* Store preheader within the father's loop structure. */
6169 SET_LOOP_PREHEADER_BLOCKS (loop_outer (current_loop_nest),