1 /* Instruction scheduling pass. Selective scheduler and pipeliner.
2 Copyright (C) 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
24 #include "diagnostic-core.h"
27 #include "hard-reg-set.h"
31 #include "insn-config.h"
32 #include "insn-attr.h"
38 #include "tree-pass.h"
39 #include "sched-int.h"
43 #include "langhooks.h"
44 #include "rtlhooks-def.h"
45 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.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 free_av_set (basic_block);
162 static void invalidate_av_set (basic_block);
163 static void extend_insn_data (void);
164 static void sel_init_new_insn (insn_t, int);
165 static void finish_insns (void);
167 /* Various list functions. */
169 /* Copy an instruction list L. */
171 ilist_copy (ilist_t l)
173 ilist_t head = NULL, *tailp = &head;
177 ilist_add (tailp, ILIST_INSN (l));
178 tailp = &ILIST_NEXT (*tailp);
185 /* Invert an instruction list L. */
187 ilist_invert (ilist_t l)
193 ilist_add (&res, ILIST_INSN (l));
200 /* Add a new boundary to the LP list with parameters TO, PTR, and DC. */
202 blist_add (blist_t *lp, insn_t to, ilist_t ptr, deps_t dc)
207 bnd = BLIST_BND (*lp);
212 BND_AV1 (bnd) = NULL;
216 /* Remove the list note pointed to by LP. */
218 blist_remove (blist_t *lp)
220 bnd_t b = BLIST_BND (*lp);
222 av_set_clear (&BND_AV (b));
223 av_set_clear (&BND_AV1 (b));
224 ilist_clear (&BND_PTR (b));
229 /* Init a fence tail L. */
231 flist_tail_init (flist_tail_t l)
233 FLIST_TAIL_HEAD (l) = NULL;
234 FLIST_TAIL_TAILP (l) = &FLIST_TAIL_HEAD (l);
237 /* Try to find fence corresponding to INSN in L. */
239 flist_lookup (flist_t l, insn_t insn)
243 if (FENCE_INSN (FLIST_FENCE (l)) == insn)
244 return FLIST_FENCE (l);
252 /* Init the fields of F before running fill_insns. */
254 init_fence_for_scheduling (fence_t f)
256 FENCE_BNDS (f) = NULL;
257 FENCE_PROCESSED_P (f) = false;
258 FENCE_SCHEDULED_P (f) = false;
261 /* Add new fence consisting of INSN and STATE to the list pointed to by LP. */
263 flist_add (flist_t *lp, insn_t insn, state_t state, deps_t dc, void *tc,
264 insn_t last_scheduled_insn, VEC(rtx,gc) *executing_insns,
265 int *ready_ticks, int ready_ticks_size, insn_t sched_next,
266 int cycle, int cycle_issued_insns, int issue_more,
267 bool starts_cycle_p, bool after_stall_p)
272 f = FLIST_FENCE (*lp);
274 FENCE_INSN (f) = insn;
276 gcc_assert (state != NULL);
277 FENCE_STATE (f) = state;
279 FENCE_CYCLE (f) = cycle;
280 FENCE_ISSUED_INSNS (f) = cycle_issued_insns;
281 FENCE_STARTS_CYCLE_P (f) = starts_cycle_p;
282 FENCE_AFTER_STALL_P (f) = after_stall_p;
284 gcc_assert (dc != NULL);
287 gcc_assert (tc != NULL || targetm.sched.alloc_sched_context == NULL);
290 FENCE_LAST_SCHEDULED_INSN (f) = last_scheduled_insn;
291 FENCE_ISSUE_MORE (f) = issue_more;
292 FENCE_EXECUTING_INSNS (f) = executing_insns;
293 FENCE_READY_TICKS (f) = ready_ticks;
294 FENCE_READY_TICKS_SIZE (f) = ready_ticks_size;
295 FENCE_SCHED_NEXT (f) = sched_next;
297 init_fence_for_scheduling (f);
300 /* Remove the head node of the list pointed to by LP. */
302 flist_remove (flist_t *lp)
304 if (FENCE_INSN (FLIST_FENCE (*lp)))
305 fence_clear (FLIST_FENCE (*lp));
309 /* Clear the fence list pointed to by LP. */
311 flist_clear (flist_t *lp)
317 /* Add ORIGINAL_INSN the def list DL honoring CROSSES_CALL. */
319 def_list_add (def_list_t *dl, insn_t original_insn, bool crosses_call)
324 d = DEF_LIST_DEF (*dl);
326 d->orig_insn = original_insn;
327 d->crosses_call = crosses_call;
331 /* Functions to work with target contexts. */
333 /* Bulk target context. It is convenient for debugging purposes to ensure
334 that there are no uninitialized (null) target contexts. */
335 static tc_t bulk_tc = (tc_t) 1;
337 /* Target hooks wrappers. In the future we can provide some default
338 implementations for them. */
340 /* Allocate a store for the target context. */
342 alloc_target_context (void)
344 return (targetm.sched.alloc_sched_context
345 ? targetm.sched.alloc_sched_context () : bulk_tc);
348 /* Init target context TC.
349 If CLEAN_P is true, then make TC as it is beginning of the scheduler.
350 Overwise, copy current backend context to TC. */
352 init_target_context (tc_t tc, bool clean_p)
354 if (targetm.sched.init_sched_context)
355 targetm.sched.init_sched_context (tc, clean_p);
358 /* Allocate and initialize a target context. Meaning of CLEAN_P is the same as
359 int init_target_context (). */
361 create_target_context (bool clean_p)
363 tc_t tc = alloc_target_context ();
365 init_target_context (tc, clean_p);
369 /* Copy TC to the current backend context. */
371 set_target_context (tc_t tc)
373 if (targetm.sched.set_sched_context)
374 targetm.sched.set_sched_context (tc);
377 /* TC is about to be destroyed. Free any internal data. */
379 clear_target_context (tc_t tc)
381 if (targetm.sched.clear_sched_context)
382 targetm.sched.clear_sched_context (tc);
385 /* Clear and free it. */
387 delete_target_context (tc_t tc)
389 clear_target_context (tc);
391 if (targetm.sched.free_sched_context)
392 targetm.sched.free_sched_context (tc);
395 /* Make a copy of FROM in TO.
396 NB: May be this should be a hook. */
398 copy_target_context (tc_t to, tc_t from)
400 tc_t tmp = create_target_context (false);
402 set_target_context (from);
403 init_target_context (to, false);
405 set_target_context (tmp);
406 delete_target_context (tmp);
409 /* Create a copy of TC. */
411 create_copy_of_target_context (tc_t tc)
413 tc_t copy = alloc_target_context ();
415 copy_target_context (copy, tc);
420 /* Clear TC and initialize it according to CLEAN_P. The meaning of CLEAN_P
421 is the same as in init_target_context (). */
423 reset_target_context (tc_t tc, bool clean_p)
425 clear_target_context (tc);
426 init_target_context (tc, clean_p);
429 /* Functions to work with dependence contexts.
430 Dc (aka deps context, aka deps_t, aka struct deps_desc *) is short for dependence
431 context. It accumulates information about processed insns to decide if
432 current insn is dependent on the processed ones. */
434 /* Make a copy of FROM in TO. */
436 copy_deps_context (deps_t to, deps_t from)
438 init_deps (to, false);
439 deps_join (to, from);
442 /* Allocate store for dep context. */
444 alloc_deps_context (void)
446 return XNEW (struct deps_desc);
449 /* Allocate and initialize dep context. */
451 create_deps_context (void)
453 deps_t dc = alloc_deps_context ();
455 init_deps (dc, false);
459 /* Create a copy of FROM. */
461 create_copy_of_deps_context (deps_t from)
463 deps_t to = alloc_deps_context ();
465 copy_deps_context (to, from);
469 /* Clean up internal data of DC. */
471 clear_deps_context (deps_t dc)
476 /* Clear and free DC. */
478 delete_deps_context (deps_t dc)
480 clear_deps_context (dc);
484 /* Clear and init DC. */
486 reset_deps_context (deps_t dc)
488 clear_deps_context (dc);
489 init_deps (dc, false);
492 /* This structure describes the dependence analysis hooks for advancing
493 dependence context. */
494 static struct sched_deps_info_def advance_deps_context_sched_deps_info =
498 NULL, /* start_insn */
499 NULL, /* finish_insn */
500 NULL, /* start_lhs */
501 NULL, /* finish_lhs */
502 NULL, /* start_rhs */
503 NULL, /* finish_rhs */
505 haifa_note_reg_clobber,
507 NULL, /* note_mem_dep */
513 /* Process INSN and add its impact on DC. */
515 advance_deps_context (deps_t dc, insn_t insn)
517 sched_deps_info = &advance_deps_context_sched_deps_info;
518 deps_analyze_insn (dc, insn);
522 /* Functions to work with DFA states. */
524 /* Allocate store for a DFA state. */
528 return xmalloc (dfa_state_size);
531 /* Allocate and initialize DFA state. */
535 state_t state = state_alloc ();
538 advance_state (state);
542 /* Free DFA state. */
544 state_free (state_t state)
549 /* Make a copy of FROM in TO. */
551 state_copy (state_t to, state_t from)
553 memcpy (to, from, dfa_state_size);
556 /* Create a copy of FROM. */
558 state_create_copy (state_t from)
560 state_t to = state_alloc ();
562 state_copy (to, from);
567 /* Functions to work with fences. */
569 /* Clear the fence. */
571 fence_clear (fence_t f)
573 state_t s = FENCE_STATE (f);
574 deps_t dc = FENCE_DC (f);
575 void *tc = FENCE_TC (f);
577 ilist_clear (&FENCE_BNDS (f));
579 gcc_assert ((s != NULL && dc != NULL && tc != NULL)
580 || (s == NULL && dc == NULL && tc == NULL));
586 delete_deps_context (dc);
589 delete_target_context (tc);
590 VEC_free (rtx, gc, FENCE_EXECUTING_INSNS (f));
591 free (FENCE_READY_TICKS (f));
592 FENCE_READY_TICKS (f) = NULL;
595 /* Init a list of fences with successors of OLD_FENCE. */
597 init_fences (insn_t old_fence)
602 int ready_ticks_size = get_max_uid () + 1;
604 FOR_EACH_SUCC_1 (succ, si, old_fence,
605 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
611 gcc_assert (flag_sel_sched_pipelining_outer_loops);
613 flist_add (&fences, succ,
615 create_deps_context () /* dc */,
616 create_target_context (true) /* tc */,
617 NULL_RTX /* last_scheduled_insn */,
618 NULL, /* executing_insns */
619 XCNEWVEC (int, ready_ticks_size), /* ready_ticks */
621 NULL_RTX /* sched_next */,
622 1 /* cycle */, 0 /* cycle_issued_insns */,
623 issue_rate, /* issue_more */
624 1 /* starts_cycle_p */, 0 /* after_stall_p */);
628 /* Merges two fences (filling fields of fence F with resulting values) by
629 following rules: 1) state, target context and last scheduled insn are
630 propagated from fallthrough edge if it is available;
631 2) deps context and cycle is propagated from more probable edge;
632 3) all other fields are set to corresponding constant values.
634 INSN, STATE, DC, TC, LAST_SCHEDULED_INSN, EXECUTING_INSNS,
635 READY_TICKS, READY_TICKS_SIZE, SCHED_NEXT, CYCLE, ISSUE_MORE
636 and AFTER_STALL_P are the corresponding fields of the second fence. */
638 merge_fences (fence_t f, insn_t insn,
639 state_t state, deps_t dc, void *tc,
640 rtx last_scheduled_insn, VEC(rtx, gc) *executing_insns,
641 int *ready_ticks, int ready_ticks_size,
642 rtx sched_next, int cycle, int issue_more, bool after_stall_p)
644 insn_t last_scheduled_insn_old = FENCE_LAST_SCHEDULED_INSN (f);
646 gcc_assert (sel_bb_head_p (FENCE_INSN (f))
647 && !sched_next && !FENCE_SCHED_NEXT (f));
649 /* Check if we can decide which path fences came.
650 If we can't (or don't want to) - reset all. */
651 if (last_scheduled_insn == NULL
652 || last_scheduled_insn_old == NULL
653 /* This is a case when INSN is reachable on several paths from
654 one insn (this can happen when pipelining of outer loops is on and
655 there are two edges: one going around of inner loop and the other -
656 right through it; in such case just reset everything). */
657 || last_scheduled_insn == last_scheduled_insn_old)
659 state_reset (FENCE_STATE (f));
662 reset_deps_context (FENCE_DC (f));
663 delete_deps_context (dc);
665 reset_target_context (FENCE_TC (f), true);
666 delete_target_context (tc);
668 if (cycle > FENCE_CYCLE (f))
669 FENCE_CYCLE (f) = cycle;
671 FENCE_LAST_SCHEDULED_INSN (f) = NULL;
672 FENCE_ISSUE_MORE (f) = issue_rate;
673 VEC_free (rtx, gc, executing_insns);
675 if (FENCE_EXECUTING_INSNS (f))
676 VEC_block_remove (rtx, FENCE_EXECUTING_INSNS (f), 0,
677 VEC_length (rtx, FENCE_EXECUTING_INSNS (f)));
678 if (FENCE_READY_TICKS (f))
679 memset (FENCE_READY_TICKS (f), 0, FENCE_READY_TICKS_SIZE (f));
683 edge edge_old = NULL, edge_new = NULL;
688 /* Find fallthrough edge. */
689 gcc_assert (BLOCK_FOR_INSN (insn)->prev_bb);
690 candidate = find_fallthru_edge_from (BLOCK_FOR_INSN (insn)->prev_bb);
693 || (candidate->src != BLOCK_FOR_INSN (last_scheduled_insn)
694 && candidate->src != BLOCK_FOR_INSN (last_scheduled_insn_old)))
696 /* No fallthrough edge leading to basic block of INSN. */
697 state_reset (FENCE_STATE (f));
700 reset_target_context (FENCE_TC (f), true);
701 delete_target_context (tc);
703 FENCE_LAST_SCHEDULED_INSN (f) = NULL;
704 FENCE_ISSUE_MORE (f) = issue_rate;
707 if (candidate->src == BLOCK_FOR_INSN (last_scheduled_insn))
709 /* Would be weird if same insn is successor of several fallthrough
711 gcc_assert (BLOCK_FOR_INSN (insn)->prev_bb
712 != BLOCK_FOR_INSN (last_scheduled_insn_old));
714 state_free (FENCE_STATE (f));
715 FENCE_STATE (f) = state;
717 delete_target_context (FENCE_TC (f));
720 FENCE_LAST_SCHEDULED_INSN (f) = last_scheduled_insn;
721 FENCE_ISSUE_MORE (f) = issue_more;
725 /* Leave STATE, TC and LAST_SCHEDULED_INSN fields untouched. */
727 delete_target_context (tc);
729 gcc_assert (BLOCK_FOR_INSN (insn)->prev_bb
730 != BLOCK_FOR_INSN (last_scheduled_insn));
733 /* Find edge of first predecessor (last_scheduled_insn_old->insn). */
734 FOR_EACH_SUCC_1 (succ, si, last_scheduled_insn_old,
735 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
739 /* No same successor allowed from several edges. */
740 gcc_assert (!edge_old);
744 /* Find edge of second predecessor (last_scheduled_insn->insn). */
745 FOR_EACH_SUCC_1 (succ, si, last_scheduled_insn,
746 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
750 /* No same successor allowed from several edges. */
751 gcc_assert (!edge_new);
756 /* Check if we can choose most probable predecessor. */
757 if (edge_old == NULL || edge_new == NULL)
759 reset_deps_context (FENCE_DC (f));
760 delete_deps_context (dc);
761 VEC_free (rtx, gc, executing_insns);
764 FENCE_CYCLE (f) = MAX (FENCE_CYCLE (f), cycle);
765 if (FENCE_EXECUTING_INSNS (f))
766 VEC_block_remove (rtx, FENCE_EXECUTING_INSNS (f), 0,
767 VEC_length (rtx, FENCE_EXECUTING_INSNS (f)));
768 if (FENCE_READY_TICKS (f))
769 memset (FENCE_READY_TICKS (f), 0, FENCE_READY_TICKS_SIZE (f));
772 if (edge_new->probability > edge_old->probability)
774 delete_deps_context (FENCE_DC (f));
776 VEC_free (rtx, gc, FENCE_EXECUTING_INSNS (f));
777 FENCE_EXECUTING_INSNS (f) = executing_insns;
778 free (FENCE_READY_TICKS (f));
779 FENCE_READY_TICKS (f) = ready_ticks;
780 FENCE_READY_TICKS_SIZE (f) = ready_ticks_size;
781 FENCE_CYCLE (f) = cycle;
785 /* Leave DC and CYCLE untouched. */
786 delete_deps_context (dc);
787 VEC_free (rtx, gc, executing_insns);
792 /* Fill remaining invariant fields. */
794 FENCE_AFTER_STALL_P (f) = 1;
796 FENCE_ISSUED_INSNS (f) = 0;
797 FENCE_STARTS_CYCLE_P (f) = 1;
798 FENCE_SCHED_NEXT (f) = NULL;
801 /* Add a new fence to NEW_FENCES list, initializing it from all
804 add_to_fences (flist_tail_t new_fences, insn_t insn,
805 state_t state, deps_t dc, void *tc, rtx last_scheduled_insn,
806 VEC(rtx, gc) *executing_insns, int *ready_ticks,
807 int ready_ticks_size, rtx sched_next, int cycle,
808 int cycle_issued_insns, int issue_rate,
809 bool starts_cycle_p, bool after_stall_p)
811 fence_t f = flist_lookup (FLIST_TAIL_HEAD (new_fences), insn);
815 flist_add (FLIST_TAIL_TAILP (new_fences), insn, state, dc, tc,
816 last_scheduled_insn, executing_insns, ready_ticks,
817 ready_ticks_size, sched_next, cycle, cycle_issued_insns,
818 issue_rate, starts_cycle_p, after_stall_p);
820 FLIST_TAIL_TAILP (new_fences)
821 = &FLIST_NEXT (*FLIST_TAIL_TAILP (new_fences));
825 merge_fences (f, insn, state, dc, tc, last_scheduled_insn,
826 executing_insns, ready_ticks, ready_ticks_size,
827 sched_next, cycle, issue_rate, after_stall_p);
831 /* Move the first fence in the OLD_FENCES list to NEW_FENCES. */
833 move_fence_to_fences (flist_t old_fences, flist_tail_t new_fences)
836 flist_t *tailp = FLIST_TAIL_TAILP (new_fences);
838 old = FLIST_FENCE (old_fences);
839 f = flist_lookup (FLIST_TAIL_HEAD (new_fences),
840 FENCE_INSN (FLIST_FENCE (old_fences)));
843 merge_fences (f, old->insn, old->state, old->dc, old->tc,
844 old->last_scheduled_insn, old->executing_insns,
845 old->ready_ticks, old->ready_ticks_size,
846 old->sched_next, old->cycle, old->issue_more,
852 FLIST_TAIL_TAILP (new_fences) = &FLIST_NEXT (*tailp);
853 *FLIST_FENCE (*tailp) = *old;
854 init_fence_for_scheduling (FLIST_FENCE (*tailp));
856 FENCE_INSN (old) = NULL;
859 /* Add a new fence to NEW_FENCES list and initialize most of its data
862 add_clean_fence_to_fences (flist_tail_t new_fences, insn_t succ, fence_t fence)
864 int ready_ticks_size = get_max_uid () + 1;
866 add_to_fences (new_fences,
867 succ, state_create (), create_deps_context (),
868 create_target_context (true),
870 XCNEWVEC (int, ready_ticks_size), ready_ticks_size,
871 NULL_RTX, FENCE_CYCLE (fence) + 1,
872 0, issue_rate, 1, FENCE_AFTER_STALL_P (fence));
875 /* Add a new fence to NEW_FENCES list and initialize all of its data
876 from FENCE and SUCC. */
878 add_dirty_fence_to_fences (flist_tail_t new_fences, insn_t succ, fence_t fence)
880 int * new_ready_ticks
881 = XNEWVEC (int, FENCE_READY_TICKS_SIZE (fence));
883 memcpy (new_ready_ticks, FENCE_READY_TICKS (fence),
884 FENCE_READY_TICKS_SIZE (fence) * sizeof (int));
885 add_to_fences (new_fences,
886 succ, state_create_copy (FENCE_STATE (fence)),
887 create_copy_of_deps_context (FENCE_DC (fence)),
888 create_copy_of_target_context (FENCE_TC (fence)),
889 FENCE_LAST_SCHEDULED_INSN (fence),
890 VEC_copy (rtx, gc, FENCE_EXECUTING_INSNS (fence)),
892 FENCE_READY_TICKS_SIZE (fence),
893 FENCE_SCHED_NEXT (fence),
895 FENCE_ISSUED_INSNS (fence),
896 FENCE_ISSUE_MORE (fence),
897 FENCE_STARTS_CYCLE_P (fence),
898 FENCE_AFTER_STALL_P (fence));
902 /* Functions to work with regset and nop pools. */
904 /* Returns the new regset from pool. It might have some of the bits set
905 from the previous usage. */
907 get_regset_from_pool (void)
911 if (regset_pool.n != 0)
912 rs = regset_pool.v[--regset_pool.n];
914 /* We need to create the regset. */
916 rs = ALLOC_REG_SET (®_obstack);
918 if (regset_pool.nn == regset_pool.ss)
919 regset_pool.vv = XRESIZEVEC (regset, regset_pool.vv,
920 (regset_pool.ss = 2 * regset_pool.ss + 1));
921 regset_pool.vv[regset_pool.nn++] = rs;
929 /* Same as above, but returns the empty regset. */
931 get_clear_regset_from_pool (void)
933 regset rs = get_regset_from_pool ();
939 /* Return regset RS to the pool for future use. */
941 return_regset_to_pool (regset rs)
946 if (regset_pool.n == regset_pool.s)
947 regset_pool.v = XRESIZEVEC (regset, regset_pool.v,
948 (regset_pool.s = 2 * regset_pool.s + 1));
949 regset_pool.v[regset_pool.n++] = rs;
952 #ifdef ENABLE_CHECKING
953 /* This is used as a qsort callback for sorting regset pool stacks.
954 X and XX are addresses of two regsets. They are never equal. */
956 cmp_v_in_regset_pool (const void *x, const void *xx)
958 return *((const regset *) x) - *((const regset *) xx);
962 /* Free the regset pool possibly checking for memory leaks. */
964 free_regset_pool (void)
966 #ifdef ENABLE_CHECKING
968 regset *v = regset_pool.v;
970 int n = regset_pool.n;
972 regset *vv = regset_pool.vv;
974 int nn = regset_pool.nn;
978 gcc_assert (n <= nn);
980 /* Sort both vectors so it will be possible to compare them. */
981 qsort (v, n, sizeof (*v), cmp_v_in_regset_pool);
982 qsort (vv, nn, sizeof (*vv), cmp_v_in_regset_pool);
989 /* VV[II] was lost. */
995 gcc_assert (diff == regset_pool.diff);
999 /* If not true - we have a memory leak. */
1000 gcc_assert (regset_pool.diff == 0);
1002 while (regset_pool.n)
1005 FREE_REG_SET (regset_pool.v[regset_pool.n]);
1008 free (regset_pool.v);
1009 regset_pool.v = NULL;
1012 free (regset_pool.vv);
1013 regset_pool.vv = NULL;
1017 regset_pool.diff = 0;
1021 /* Functions to work with nop pools. NOP insns are used as temporary
1022 placeholders of the insns being scheduled to allow correct update of
1023 the data sets. When update is finished, NOPs are deleted. */
1025 /* A vinsn that is used to represent a nop. This vinsn is shared among all
1026 nops sel-sched generates. */
1027 static vinsn_t nop_vinsn = NULL;
1029 /* Emit a nop before INSN, taking it from pool. */
1031 get_nop_from_pool (insn_t insn)
1034 bool old_p = nop_pool.n != 0;
1038 nop = nop_pool.v[--nop_pool.n];
1042 nop = emit_insn_before (nop, insn);
1045 flags = INSN_INIT_TODO_SSID;
1047 flags = INSN_INIT_TODO_LUID | INSN_INIT_TODO_SSID;
1049 set_insn_init (INSN_EXPR (insn), nop_vinsn, INSN_SEQNO (insn));
1050 sel_init_new_insn (nop, flags);
1055 /* Remove NOP from the instruction stream and return it to the pool. */
1057 return_nop_to_pool (insn_t nop, bool full_tidying)
1059 gcc_assert (INSN_IN_STREAM_P (nop));
1060 sel_remove_insn (nop, false, full_tidying);
1062 if (nop_pool.n == nop_pool.s)
1063 nop_pool.v = XRESIZEVEC (rtx, nop_pool.v,
1064 (nop_pool.s = 2 * nop_pool.s + 1));
1065 nop_pool.v[nop_pool.n++] = nop;
1068 /* Free the nop pool. */
1070 free_nop_pool (void)
1079 /* Skip unspec to support ia64 speculation. Called from rtx_equal_p_cb.
1080 The callback is given two rtxes XX and YY and writes the new rtxes
1081 to NX and NY in case some needs to be skipped. */
1083 skip_unspecs_callback (const_rtx *xx, const_rtx *yy, rtx *nx, rtx* ny)
1088 if (GET_CODE (x) == UNSPEC
1089 && (targetm.sched.skip_rtx_p == NULL
1090 || targetm.sched.skip_rtx_p (x)))
1092 *nx = XVECEXP (x, 0, 0);
1093 *ny = CONST_CAST_RTX (y);
1097 if (GET_CODE (y) == UNSPEC
1098 && (targetm.sched.skip_rtx_p == NULL
1099 || targetm.sched.skip_rtx_p (y)))
1101 *nx = CONST_CAST_RTX (x);
1102 *ny = XVECEXP (y, 0, 0);
1109 /* Callback, called from hash_rtx_cb. Helps to hash UNSPEC rtx X in a correct way
1110 to support ia64 speculation. When changes are needed, new rtx X and new mode
1111 NMODE are written, and the callback returns true. */
1113 hash_with_unspec_callback (const_rtx x, enum machine_mode mode ATTRIBUTE_UNUSED,
1114 rtx *nx, enum machine_mode* nmode)
1116 if (GET_CODE (x) == UNSPEC
1117 && targetm.sched.skip_rtx_p
1118 && targetm.sched.skip_rtx_p (x))
1120 *nx = XVECEXP (x, 0 ,0);
1128 /* Returns LHS and RHS are ok to be scheduled separately. */
1130 lhs_and_rhs_separable_p (rtx lhs, rtx rhs)
1132 if (lhs == NULL || rhs == NULL)
1135 /* Do not schedule CONST, CONST_INT and CONST_DOUBLE etc as rhs: no point
1136 to use reg, if const can be used. Moreover, scheduling const as rhs may
1137 lead to mode mismatch cause consts don't have modes but they could be
1138 merged from branches where the same const used in different modes. */
1139 if (CONSTANT_P (rhs))
1142 /* ??? Do not rename predicate registers to avoid ICEs in bundling. */
1143 if (COMPARISON_P (rhs))
1146 /* Do not allow single REG to be an rhs. */
1150 /* See comment at find_used_regs_1 (*1) for explanation of this
1152 /* FIXME: remove this later. */
1156 /* This will filter all tricky things like ZERO_EXTRACT etc.
1157 For now we don't handle it. */
1158 if (!REG_P (lhs) && !MEM_P (lhs))
1164 /* Initialize vinsn VI for INSN. Only for use from vinsn_create (). When
1165 FORCE_UNIQUE_P is true, the resulting vinsn will not be clonable. This is
1166 used e.g. for insns from recovery blocks. */
1168 vinsn_init (vinsn_t vi, insn_t insn, bool force_unique_p)
1170 hash_rtx_callback_function hrcf;
1173 VINSN_INSN_RTX (vi) = insn;
1174 VINSN_COUNT (vi) = 0;
1177 if (INSN_NOP_P (insn))
1180 if (DF_INSN_UID_SAFE_GET (INSN_UID (insn)) != NULL)
1181 init_id_from_df (VINSN_ID (vi), insn, force_unique_p);
1183 deps_init_id (VINSN_ID (vi), insn, force_unique_p);
1185 /* Hash vinsn depending on whether it is separable or not. */
1186 hrcf = targetm.sched.skip_rtx_p ? hash_with_unspec_callback : NULL;
1187 if (VINSN_SEPARABLE_P (vi))
1189 rtx rhs = VINSN_RHS (vi);
1191 VINSN_HASH (vi) = hash_rtx_cb (rhs, GET_MODE (rhs),
1192 NULL, NULL, false, hrcf);
1193 VINSN_HASH_RTX (vi) = hash_rtx_cb (VINSN_PATTERN (vi),
1194 VOIDmode, NULL, NULL,
1199 VINSN_HASH (vi) = hash_rtx_cb (VINSN_PATTERN (vi), VOIDmode,
1200 NULL, NULL, false, hrcf);
1201 VINSN_HASH_RTX (vi) = VINSN_HASH (vi);
1204 insn_class = haifa_classify_insn (insn);
1206 && (!targetm.sched.get_insn_spec_ds
1207 || ((targetm.sched.get_insn_spec_ds (insn) & BEGIN_CONTROL)
1209 VINSN_MAY_TRAP_P (vi) = true;
1211 VINSN_MAY_TRAP_P (vi) = false;
1214 /* Indicate that VI has become the part of an rtx object. */
1216 vinsn_attach (vinsn_t vi)
1218 /* Assert that VI is not pending for deletion. */
1219 gcc_assert (VINSN_INSN_RTX (vi));
1224 /* Create and init VI from the INSN. Use UNIQUE_P for determining the correct
1227 vinsn_create (insn_t insn, bool force_unique_p)
1229 vinsn_t vi = XCNEW (struct vinsn_def);
1231 vinsn_init (vi, insn, force_unique_p);
1235 /* Return a copy of VI. When REATTACH_P is true, detach VI and attach
1238 vinsn_copy (vinsn_t vi, bool reattach_p)
1241 bool unique = VINSN_UNIQUE_P (vi);
1244 copy = create_copy_of_insn_rtx (VINSN_INSN_RTX (vi));
1245 new_vi = create_vinsn_from_insn_rtx (copy, unique);
1249 vinsn_attach (new_vi);
1255 /* Delete the VI vinsn and free its data. */
1257 vinsn_delete (vinsn_t vi)
1259 gcc_assert (VINSN_COUNT (vi) == 0);
1261 if (!INSN_NOP_P (VINSN_INSN_RTX (vi)))
1263 return_regset_to_pool (VINSN_REG_SETS (vi));
1264 return_regset_to_pool (VINSN_REG_USES (vi));
1265 return_regset_to_pool (VINSN_REG_CLOBBERS (vi));
1271 /* Indicate that VI is no longer a part of some rtx object.
1272 Remove VI if it is no longer needed. */
1274 vinsn_detach (vinsn_t vi)
1276 gcc_assert (VINSN_COUNT (vi) > 0);
1278 if (--VINSN_COUNT (vi) == 0)
1282 /* Returns TRUE if VI is a branch. */
1284 vinsn_cond_branch_p (vinsn_t vi)
1288 if (!VINSN_UNIQUE_P (vi))
1291 insn = VINSN_INSN_RTX (vi);
1292 if (BB_END (BLOCK_FOR_INSN (insn)) != insn)
1295 return control_flow_insn_p (insn);
1298 /* Return latency of INSN. */
1300 sel_insn_rtx_cost (rtx insn)
1304 /* A USE insn, or something else we don't need to
1305 understand. We can't pass these directly to
1306 result_ready_cost or insn_default_latency because it will
1307 trigger a fatal error for unrecognizable insns. */
1308 if (recog_memoized (insn) < 0)
1312 cost = insn_default_latency (insn);
1321 /* Return the cost of the VI.
1322 !!! FIXME: Unify with haifa-sched.c: insn_cost (). */
1324 sel_vinsn_cost (vinsn_t vi)
1326 int cost = vi->cost;
1330 cost = sel_insn_rtx_cost (VINSN_INSN_RTX (vi));
1338 /* Functions for insn emitting. */
1340 /* Emit new insn after AFTER based on PATTERN and initialize its data from
1343 sel_gen_insn_from_rtx_after (rtx pattern, expr_t expr, int seqno, insn_t after)
1347 gcc_assert (EXPR_TARGET_AVAILABLE (expr) == true);
1349 new_insn = emit_insn_after (pattern, after);
1350 set_insn_init (expr, NULL, seqno);
1351 sel_init_new_insn (new_insn, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SSID);
1356 /* Force newly generated vinsns to be unique. */
1357 static bool init_insn_force_unique_p = false;
1359 /* Emit new speculation recovery insn after AFTER based on PATTERN and
1360 initialize its data from EXPR and SEQNO. */
1362 sel_gen_recovery_insn_from_rtx_after (rtx pattern, expr_t expr, int seqno,
1367 gcc_assert (!init_insn_force_unique_p);
1369 init_insn_force_unique_p = true;
1370 insn = sel_gen_insn_from_rtx_after (pattern, expr, seqno, after);
1371 CANT_MOVE (insn) = 1;
1372 init_insn_force_unique_p = false;
1377 /* Emit new insn after AFTER based on EXPR and SEQNO. If VINSN is not NULL,
1378 take it as a new vinsn instead of EXPR's vinsn.
1379 We simplify insns later, after scheduling region in
1380 simplify_changed_insns. */
1382 sel_gen_insn_from_expr_after (expr_t expr, vinsn_t vinsn, int seqno,
1389 emit_expr = set_insn_init (expr, vinsn ? vinsn : EXPR_VINSN (expr),
1391 insn = EXPR_INSN_RTX (emit_expr);
1392 add_insn_after (insn, after, BLOCK_FOR_INSN (insn));
1394 flags = INSN_INIT_TODO_SSID;
1395 if (INSN_LUID (insn) == 0)
1396 flags |= INSN_INIT_TODO_LUID;
1397 sel_init_new_insn (insn, flags);
1402 /* Move insn from EXPR after AFTER. */
1404 sel_move_insn (expr_t expr, int seqno, insn_t after)
1406 insn_t insn = EXPR_INSN_RTX (expr);
1407 basic_block bb = BLOCK_FOR_INSN (after);
1408 insn_t next = NEXT_INSN (after);
1410 /* Assert that in move_op we disconnected this insn properly. */
1411 gcc_assert (EXPR_VINSN (INSN_EXPR (insn)) != NULL);
1412 PREV_INSN (insn) = after;
1413 NEXT_INSN (insn) = next;
1415 NEXT_INSN (after) = insn;
1416 PREV_INSN (next) = insn;
1418 /* Update links from insn to bb and vice versa. */
1419 df_insn_change_bb (insn, bb);
1420 if (BB_END (bb) == after)
1423 prepare_insn_expr (insn, seqno);
1428 /* Functions to work with right-hand sides. */
1430 /* Search for a hash value determined by UID/NEW_VINSN in a sorted vector
1431 VECT and return true when found. Use NEW_VINSN for comparison only when
1432 COMPARE_VINSNS is true. Write to INDP the index on which
1433 the search has stopped, such that inserting the new element at INDP will
1434 retain VECT's sort order. */
1436 find_in_history_vect_1 (VEC(expr_history_def, heap) *vect,
1437 unsigned uid, vinsn_t new_vinsn,
1438 bool compare_vinsns, int *indp)
1440 expr_history_def *arr;
1441 int i, j, len = VEC_length (expr_history_def, vect);
1449 arr = VEC_address (expr_history_def, vect);
1454 unsigned auid = arr[i].uid;
1455 vinsn_t avinsn = arr[i].new_expr_vinsn;
1458 /* When undoing transformation on a bookkeeping copy, the new vinsn
1459 may not be exactly equal to the one that is saved in the vector.
1460 This is because the insn whose copy we're checking was possibly
1461 substituted itself. */
1462 && (! compare_vinsns
1463 || vinsn_equal_p (avinsn, new_vinsn)))
1468 else if (auid > uid)
1477 /* Search for a uid of INSN and NEW_VINSN in a sorted vector VECT. Return
1478 the position found or -1, if no such value is in vector.
1479 Search also for UIDs of insn's originators, if ORIGINATORS_P is true. */
1481 find_in_history_vect (VEC(expr_history_def, heap) *vect, rtx insn,
1482 vinsn_t new_vinsn, bool originators_p)
1486 if (find_in_history_vect_1 (vect, INSN_UID (insn), new_vinsn,
1490 if (INSN_ORIGINATORS (insn) && originators_p)
1495 EXECUTE_IF_SET_IN_BITMAP (INSN_ORIGINATORS (insn), 0, uid, bi)
1496 if (find_in_history_vect_1 (vect, uid, new_vinsn, false, &ind))
1503 /* Insert new element in a sorted history vector pointed to by PVECT,
1504 if it is not there already. The element is searched using
1505 UID/NEW_EXPR_VINSN pair. TYPE, OLD_EXPR_VINSN and SPEC_DS save
1506 the history of a transformation. */
1508 insert_in_history_vect (VEC (expr_history_def, heap) **pvect,
1509 unsigned uid, enum local_trans_type type,
1510 vinsn_t old_expr_vinsn, vinsn_t new_expr_vinsn,
1513 VEC(expr_history_def, heap) *vect = *pvect;
1514 expr_history_def temp;
1518 res = find_in_history_vect_1 (vect, uid, new_expr_vinsn, true, &ind);
1522 expr_history_def *phist = VEC_index (expr_history_def, vect, ind);
1524 /* It is possible that speculation types of expressions that were
1525 propagated through different paths will be different here. In this
1526 case, merge the status to get the correct check later. */
1527 if (phist->spec_ds != spec_ds)
1528 phist->spec_ds = ds_max_merge (phist->spec_ds, spec_ds);
1533 temp.old_expr_vinsn = old_expr_vinsn;
1534 temp.new_expr_vinsn = new_expr_vinsn;
1535 temp.spec_ds = spec_ds;
1538 vinsn_attach (old_expr_vinsn);
1539 vinsn_attach (new_expr_vinsn);
1540 VEC_safe_insert (expr_history_def, heap, vect, ind, &temp);
1544 /* Free history vector PVECT. */
1546 free_history_vect (VEC (expr_history_def, heap) **pvect)
1549 expr_history_def *phist;
1555 VEC_iterate (expr_history_def, *pvect, i, phist);
1558 vinsn_detach (phist->old_expr_vinsn);
1559 vinsn_detach (phist->new_expr_vinsn);
1562 VEC_free (expr_history_def, heap, *pvect);
1567 /* Compare two vinsns as rhses if possible and as vinsns otherwise. */
1569 vinsn_equal_p (vinsn_t x, vinsn_t y)
1571 rtx_equal_p_callback_function repcf;
1576 if (VINSN_TYPE (x) != VINSN_TYPE (y))
1579 if (VINSN_HASH (x) != VINSN_HASH (y))
1582 repcf = targetm.sched.skip_rtx_p ? skip_unspecs_callback : NULL;
1583 if (VINSN_SEPARABLE_P (x))
1585 /* Compare RHSes of VINSNs. */
1586 gcc_assert (VINSN_RHS (x));
1587 gcc_assert (VINSN_RHS (y));
1589 return rtx_equal_p_cb (VINSN_RHS (x), VINSN_RHS (y), repcf);
1592 return rtx_equal_p_cb (VINSN_PATTERN (x), VINSN_PATTERN (y), repcf);
1596 /* Functions for working with expressions. */
1598 /* Initialize EXPR. */
1600 init_expr (expr_t expr, vinsn_t vi, int spec, int use, int priority,
1601 int sched_times, int orig_bb_index, ds_t spec_done_ds,
1602 ds_t spec_to_check_ds, int orig_sched_cycle,
1603 VEC(expr_history_def, heap) *history, signed char target_available,
1604 bool was_substituted, bool was_renamed, bool needs_spec_check_p,
1609 EXPR_VINSN (expr) = vi;
1610 EXPR_SPEC (expr) = spec;
1611 EXPR_USEFULNESS (expr) = use;
1612 EXPR_PRIORITY (expr) = priority;
1613 EXPR_PRIORITY_ADJ (expr) = 0;
1614 EXPR_SCHED_TIMES (expr) = sched_times;
1615 EXPR_ORIG_BB_INDEX (expr) = orig_bb_index;
1616 EXPR_ORIG_SCHED_CYCLE (expr) = orig_sched_cycle;
1617 EXPR_SPEC_DONE_DS (expr) = spec_done_ds;
1618 EXPR_SPEC_TO_CHECK_DS (expr) = spec_to_check_ds;
1621 EXPR_HISTORY_OF_CHANGES (expr) = history;
1623 EXPR_HISTORY_OF_CHANGES (expr) = NULL;
1625 EXPR_TARGET_AVAILABLE (expr) = target_available;
1626 EXPR_WAS_SUBSTITUTED (expr) = was_substituted;
1627 EXPR_WAS_RENAMED (expr) = was_renamed;
1628 EXPR_NEEDS_SPEC_CHECK_P (expr) = needs_spec_check_p;
1629 EXPR_CANT_MOVE (expr) = cant_move;
1632 /* Make a copy of the expr FROM into the expr TO. */
1634 copy_expr (expr_t to, expr_t from)
1636 VEC(expr_history_def, heap) *temp = NULL;
1638 if (EXPR_HISTORY_OF_CHANGES (from))
1641 expr_history_def *phist;
1643 temp = VEC_copy (expr_history_def, heap, EXPR_HISTORY_OF_CHANGES (from));
1645 VEC_iterate (expr_history_def, temp, i, phist);
1648 vinsn_attach (phist->old_expr_vinsn);
1649 vinsn_attach (phist->new_expr_vinsn);
1653 init_expr (to, EXPR_VINSN (from), EXPR_SPEC (from),
1654 EXPR_USEFULNESS (from), EXPR_PRIORITY (from),
1655 EXPR_SCHED_TIMES (from), EXPR_ORIG_BB_INDEX (from),
1656 EXPR_SPEC_DONE_DS (from), EXPR_SPEC_TO_CHECK_DS (from),
1657 EXPR_ORIG_SCHED_CYCLE (from), temp,
1658 EXPR_TARGET_AVAILABLE (from), EXPR_WAS_SUBSTITUTED (from),
1659 EXPR_WAS_RENAMED (from), EXPR_NEEDS_SPEC_CHECK_P (from),
1660 EXPR_CANT_MOVE (from));
1663 /* Same, but the final expr will not ever be in av sets, so don't copy
1664 "uninteresting" data such as bitmap cache. */
1666 copy_expr_onside (expr_t to, expr_t from)
1668 init_expr (to, EXPR_VINSN (from), EXPR_SPEC (from), EXPR_USEFULNESS (from),
1669 EXPR_PRIORITY (from), EXPR_SCHED_TIMES (from), 0,
1670 EXPR_SPEC_DONE_DS (from), EXPR_SPEC_TO_CHECK_DS (from), 0, NULL,
1671 EXPR_TARGET_AVAILABLE (from), EXPR_WAS_SUBSTITUTED (from),
1672 EXPR_WAS_RENAMED (from), EXPR_NEEDS_SPEC_CHECK_P (from),
1673 EXPR_CANT_MOVE (from));
1676 /* Prepare the expr of INSN for scheduling. Used when moving insn and when
1677 initializing new insns. */
1679 prepare_insn_expr (insn_t insn, int seqno)
1681 expr_t expr = INSN_EXPR (insn);
1684 INSN_SEQNO (insn) = seqno;
1685 EXPR_ORIG_BB_INDEX (expr) = BLOCK_NUM (insn);
1686 EXPR_SPEC (expr) = 0;
1687 EXPR_ORIG_SCHED_CYCLE (expr) = 0;
1688 EXPR_WAS_SUBSTITUTED (expr) = 0;
1689 EXPR_WAS_RENAMED (expr) = 0;
1690 EXPR_TARGET_AVAILABLE (expr) = 1;
1691 INSN_LIVE_VALID_P (insn) = false;
1693 /* ??? If this expression is speculative, make its dependence
1694 as weak as possible. We can filter this expression later
1695 in process_spec_exprs, because we do not distinguish
1696 between the status we got during compute_av_set and the
1697 existing status. To be fixed. */
1698 ds = EXPR_SPEC_DONE_DS (expr);
1700 EXPR_SPEC_DONE_DS (expr) = ds_get_max_dep_weak (ds);
1702 free_history_vect (&EXPR_HISTORY_OF_CHANGES (expr));
1705 /* Update target_available bits when merging exprs TO and FROM. SPLIT_POINT
1706 is non-null when expressions are merged from different successors at
1709 update_target_availability (expr_t to, expr_t from, insn_t split_point)
1711 if (EXPR_TARGET_AVAILABLE (to) < 0
1712 || EXPR_TARGET_AVAILABLE (from) < 0)
1713 EXPR_TARGET_AVAILABLE (to) = -1;
1716 /* We try to detect the case when one of the expressions
1717 can only be reached through another one. In this case,
1718 we can do better. */
1719 if (split_point == NULL)
1723 toind = EXPR_ORIG_BB_INDEX (to);
1724 fromind = EXPR_ORIG_BB_INDEX (from);
1726 if (toind && toind == fromind)
1727 /* Do nothing -- everything is done in
1728 merge_with_other_exprs. */
1731 EXPR_TARGET_AVAILABLE (to) = -1;
1734 EXPR_TARGET_AVAILABLE (to) &= EXPR_TARGET_AVAILABLE (from);
1738 /* Update speculation bits when merging exprs TO and FROM. SPLIT_POINT
1739 is non-null when expressions are merged from different successors at
1742 update_speculative_bits (expr_t to, expr_t from, insn_t split_point)
1744 ds_t old_to_ds, old_from_ds;
1746 old_to_ds = EXPR_SPEC_DONE_DS (to);
1747 old_from_ds = EXPR_SPEC_DONE_DS (from);
1749 EXPR_SPEC_DONE_DS (to) = ds_max_merge (old_to_ds, old_from_ds);
1750 EXPR_SPEC_TO_CHECK_DS (to) |= EXPR_SPEC_TO_CHECK_DS (from);
1751 EXPR_NEEDS_SPEC_CHECK_P (to) |= EXPR_NEEDS_SPEC_CHECK_P (from);
1753 /* When merging e.g. control & data speculative exprs, or a control
1754 speculative with a control&data speculative one, we really have
1755 to change vinsn too. Also, when speculative status is changed,
1756 we also need to record this as a transformation in expr's history. */
1757 if ((old_to_ds & SPECULATIVE) || (old_from_ds & SPECULATIVE))
1759 old_to_ds = ds_get_speculation_types (old_to_ds);
1760 old_from_ds = ds_get_speculation_types (old_from_ds);
1762 if (old_to_ds != old_from_ds)
1766 /* When both expressions are speculative, we need to change
1768 if ((old_to_ds & SPECULATIVE) && (old_from_ds & SPECULATIVE))
1772 res = speculate_expr (to, EXPR_SPEC_DONE_DS (to));
1773 gcc_assert (res >= 0);
1776 if (split_point != NULL)
1778 /* Record the change with proper status. */
1779 record_ds = EXPR_SPEC_DONE_DS (to) & SPECULATIVE;
1780 record_ds &= ~(old_to_ds & SPECULATIVE);
1781 record_ds &= ~(old_from_ds & SPECULATIVE);
1783 insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (to),
1784 INSN_UID (split_point), TRANS_SPECULATION,
1785 EXPR_VINSN (from), EXPR_VINSN (to),
1793 /* Merge bits of FROM expr to TO expr. When SPLIT_POINT is not NULL,
1794 this is done along different paths. */
1796 merge_expr_data (expr_t to, expr_t from, insn_t split_point)
1799 expr_history_def *phist;
1801 /* For now, we just set the spec of resulting expr to be minimum of the specs
1803 if (EXPR_SPEC (to) > EXPR_SPEC (from))
1804 EXPR_SPEC (to) = EXPR_SPEC (from);
1807 EXPR_USEFULNESS (to) += EXPR_USEFULNESS (from);
1809 EXPR_USEFULNESS (to) = MAX (EXPR_USEFULNESS (to),
1810 EXPR_USEFULNESS (from));
1812 if (EXPR_PRIORITY (to) < EXPR_PRIORITY (from))
1813 EXPR_PRIORITY (to) = EXPR_PRIORITY (from);
1815 if (EXPR_SCHED_TIMES (to) > EXPR_SCHED_TIMES (from))
1816 EXPR_SCHED_TIMES (to) = EXPR_SCHED_TIMES (from);
1818 if (EXPR_ORIG_BB_INDEX (to) != EXPR_ORIG_BB_INDEX (from))
1819 EXPR_ORIG_BB_INDEX (to) = 0;
1821 EXPR_ORIG_SCHED_CYCLE (to) = MIN (EXPR_ORIG_SCHED_CYCLE (to),
1822 EXPR_ORIG_SCHED_CYCLE (from));
1824 /* We keep this vector sorted. */
1826 VEC_iterate (expr_history_def, EXPR_HISTORY_OF_CHANGES (from),
1829 insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (to),
1830 phist->uid, phist->type,
1831 phist->old_expr_vinsn, phist->new_expr_vinsn,
1834 EXPR_WAS_SUBSTITUTED (to) |= EXPR_WAS_SUBSTITUTED (from);
1835 EXPR_WAS_RENAMED (to) |= EXPR_WAS_RENAMED (from);
1836 EXPR_CANT_MOVE (to) |= EXPR_CANT_MOVE (from);
1838 update_target_availability (to, from, split_point);
1839 update_speculative_bits (to, from, split_point);
1842 /* Merge bits of FROM expr to TO expr. Vinsns in the exprs should be equal
1843 in terms of vinsn_equal_p. SPLIT_POINT is non-null when expressions
1844 are merged from different successors at a split point. */
1846 merge_expr (expr_t to, expr_t from, insn_t split_point)
1848 vinsn_t to_vi = EXPR_VINSN (to);
1849 vinsn_t from_vi = EXPR_VINSN (from);
1851 gcc_assert (vinsn_equal_p (to_vi, from_vi));
1853 /* Make sure that speculative pattern is propagated into exprs that
1854 have non-speculative one. This will provide us with consistent
1855 speculative bits and speculative patterns inside expr. */
1856 if (EXPR_SPEC_DONE_DS (to) == 0
1857 && EXPR_SPEC_DONE_DS (from) != 0)
1858 change_vinsn_in_expr (to, EXPR_VINSN (from));
1860 merge_expr_data (to, from, split_point);
1861 gcc_assert (EXPR_USEFULNESS (to) <= REG_BR_PROB_BASE);
1864 /* Clear the information of this EXPR. */
1866 clear_expr (expr_t expr)
1869 vinsn_detach (EXPR_VINSN (expr));
1870 EXPR_VINSN (expr) = NULL;
1872 free_history_vect (&EXPR_HISTORY_OF_CHANGES (expr));
1875 /* For a given LV_SET, mark EXPR having unavailable target register. */
1877 set_unavailable_target_for_expr (expr_t expr, regset lv_set)
1879 if (EXPR_SEPARABLE_P (expr))
1881 if (REG_P (EXPR_LHS (expr))
1882 && bitmap_bit_p (lv_set, REGNO (EXPR_LHS (expr))))
1884 /* If it's an insn like r1 = use (r1, ...), and it exists in
1885 different forms in each of the av_sets being merged, we can't say
1886 whether original destination register is available or not.
1887 However, this still works if destination register is not used
1888 in the original expression: if the branch at which LV_SET we're
1889 looking here is not actually 'other branch' in sense that same
1890 expression is available through it (but it can't be determined
1891 at computation stage because of transformations on one of the
1892 branches), it still won't affect the availability.
1893 Liveness of a register somewhere on a code motion path means
1894 it's either read somewhere on a codemotion path, live on
1895 'other' branch, live at the point immediately following
1896 the original operation, or is read by the original operation.
1897 The latter case is filtered out in the condition below.
1898 It still doesn't cover the case when register is defined and used
1899 somewhere within the code motion path, and in this case we could
1900 miss a unifying code motion along both branches using a renamed
1901 register, but it won't affect a code correctness since upon
1902 an actual code motion a bookkeeping code would be generated. */
1903 if (bitmap_bit_p (VINSN_REG_USES (EXPR_VINSN (expr)),
1904 REGNO (EXPR_LHS (expr))))
1905 EXPR_TARGET_AVAILABLE (expr) = -1;
1907 EXPR_TARGET_AVAILABLE (expr) = false;
1913 reg_set_iterator rsi;
1915 EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_SETS (EXPR_VINSN (expr)),
1917 if (bitmap_bit_p (lv_set, regno))
1919 EXPR_TARGET_AVAILABLE (expr) = false;
1923 EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_CLOBBERS (EXPR_VINSN (expr)),
1925 if (bitmap_bit_p (lv_set, regno))
1927 EXPR_TARGET_AVAILABLE (expr) = false;
1933 /* Try to make EXPR speculative. Return 1 when EXPR's pattern
1934 or dependence status have changed, 2 when also the target register
1935 became unavailable, 0 if nothing had to be changed. */
1937 speculate_expr (expr_t expr, ds_t ds)
1942 ds_t target_ds, current_ds;
1944 /* Obtain the status we need to put on EXPR. */
1945 target_ds = (ds & SPECULATIVE);
1946 current_ds = EXPR_SPEC_DONE_DS (expr);
1947 ds = ds_full_merge (current_ds, target_ds, NULL_RTX, NULL_RTX);
1949 orig_insn_rtx = EXPR_INSN_RTX (expr);
1951 res = sched_speculate_insn (orig_insn_rtx, ds, &spec_pat);
1956 EXPR_SPEC_DONE_DS (expr) = ds;
1957 return current_ds != ds ? 1 : 0;
1961 rtx spec_insn_rtx = create_insn_rtx_from_pattern (spec_pat, NULL_RTX);
1962 vinsn_t spec_vinsn = create_vinsn_from_insn_rtx (spec_insn_rtx, false);
1964 change_vinsn_in_expr (expr, spec_vinsn);
1965 EXPR_SPEC_DONE_DS (expr) = ds;
1966 EXPR_NEEDS_SPEC_CHECK_P (expr) = true;
1968 /* Do not allow clobbering the address register of speculative
1970 if (bitmap_bit_p (VINSN_REG_USES (EXPR_VINSN (expr)),
1971 expr_dest_regno (expr)))
1973 EXPR_TARGET_AVAILABLE (expr) = false;
1989 /* Return a destination register, if any, of EXPR. */
1991 expr_dest_reg (expr_t expr)
1993 rtx dest = VINSN_LHS (EXPR_VINSN (expr));
1995 if (dest != NULL_RTX && REG_P (dest))
2001 /* Returns the REGNO of the R's destination. */
2003 expr_dest_regno (expr_t expr)
2005 rtx dest = expr_dest_reg (expr);
2007 gcc_assert (dest != NULL_RTX);
2008 return REGNO (dest);
2011 /* For a given LV_SET, mark all expressions in JOIN_SET, but not present in
2012 AV_SET having unavailable target register. */
2014 mark_unavailable_targets (av_set_t join_set, av_set_t av_set, regset lv_set)
2017 av_set_iterator avi;
2019 FOR_EACH_EXPR (expr, avi, join_set)
2020 if (av_set_lookup (av_set, EXPR_VINSN (expr)) == NULL)
2021 set_unavailable_target_for_expr (expr, lv_set);
2025 /* Av set functions. */
2027 /* Add a new element to av set SETP.
2028 Return the element added. */
2030 av_set_add_element (av_set_t *setp)
2032 /* Insert at the beginning of the list. */
2037 /* Add EXPR to SETP. */
2039 av_set_add (av_set_t *setp, expr_t expr)
2043 gcc_assert (!INSN_NOP_P (EXPR_INSN_RTX (expr)));
2044 elem = av_set_add_element (setp);
2045 copy_expr (_AV_SET_EXPR (elem), expr);
2048 /* Same, but do not copy EXPR. */
2050 av_set_add_nocopy (av_set_t *setp, expr_t expr)
2054 elem = av_set_add_element (setp);
2055 *_AV_SET_EXPR (elem) = *expr;
2058 /* Remove expr pointed to by IP from the av_set. */
2060 av_set_iter_remove (av_set_iterator *ip)
2062 clear_expr (_AV_SET_EXPR (*ip->lp));
2063 _list_iter_remove (ip);
2066 /* Search for an expr in SET, such that it's equivalent to SOUGHT_VINSN in the
2067 sense of vinsn_equal_p function. Return NULL if no such expr is
2068 in SET was found. */
2070 av_set_lookup (av_set_t set, vinsn_t sought_vinsn)
2075 FOR_EACH_EXPR (expr, i, set)
2076 if (vinsn_equal_p (EXPR_VINSN (expr), sought_vinsn))
2081 /* Same, but also remove the EXPR found. */
2083 av_set_lookup_and_remove (av_set_t *setp, vinsn_t sought_vinsn)
2088 FOR_EACH_EXPR_1 (expr, i, setp)
2089 if (vinsn_equal_p (EXPR_VINSN (expr), sought_vinsn))
2091 _list_iter_remove_nofree (&i);
2097 /* Search for an expr in SET, such that it's equivalent to EXPR in the
2098 sense of vinsn_equal_p function of their vinsns, but not EXPR itself.
2099 Returns NULL if no such expr is in SET was found. */
2101 av_set_lookup_other_equiv_expr (av_set_t set, expr_t expr)
2106 FOR_EACH_EXPR (cur_expr, i, set)
2108 if (cur_expr == expr)
2110 if (vinsn_equal_p (EXPR_VINSN (cur_expr), EXPR_VINSN (expr)))
2117 /* If other expression is already in AVP, remove one of them. */
2119 merge_with_other_exprs (av_set_t *avp, av_set_iterator *ip, expr_t expr)
2123 expr2 = av_set_lookup_other_equiv_expr (*avp, expr);
2126 /* Reset target availability on merge, since taking it only from one
2127 of the exprs would be controversial for different code. */
2128 EXPR_TARGET_AVAILABLE (expr2) = -1;
2129 EXPR_USEFULNESS (expr2) = 0;
2131 merge_expr (expr2, expr, NULL);
2133 /* Fix usefulness as it should be now REG_BR_PROB_BASE. */
2134 EXPR_USEFULNESS (expr2) = REG_BR_PROB_BASE;
2136 av_set_iter_remove (ip);
2143 /* Return true if there is an expr that correlates to VI in SET. */
2145 av_set_is_in_p (av_set_t set, vinsn_t vi)
2147 return av_set_lookup (set, vi) != NULL;
2150 /* Return a copy of SET. */
2152 av_set_copy (av_set_t set)
2156 av_set_t res = NULL;
2158 FOR_EACH_EXPR (expr, i, set)
2159 av_set_add (&res, expr);
2164 /* Join two av sets that do not have common elements by attaching second set
2165 (pointed to by FROMP) to the end of first set (TO_TAILP must point to
2166 _AV_SET_NEXT of first set's last element). */
2168 join_distinct_sets (av_set_t *to_tailp, av_set_t *fromp)
2170 gcc_assert (*to_tailp == NULL);
2175 /* Makes set pointed to by TO to be the union of TO and FROM. Clear av_set
2176 pointed to by FROMP afterwards. */
2178 av_set_union_and_clear (av_set_t *top, av_set_t *fromp, insn_t insn)
2183 /* Delete from TOP all exprs, that present in FROMP. */
2184 FOR_EACH_EXPR_1 (expr1, i, top)
2186 expr_t expr2 = av_set_lookup (*fromp, EXPR_VINSN (expr1));
2190 merge_expr (expr2, expr1, insn);
2191 av_set_iter_remove (&i);
2195 join_distinct_sets (i.lp, fromp);
2198 /* Same as above, but also update availability of target register in
2199 TOP judging by TO_LV_SET and FROM_LV_SET. */
2201 av_set_union_and_live (av_set_t *top, av_set_t *fromp, regset to_lv_set,
2202 regset from_lv_set, insn_t insn)
2206 av_set_t *to_tailp, in_both_set = NULL;
2208 /* Delete from TOP all expres, that present in FROMP. */
2209 FOR_EACH_EXPR_1 (expr1, i, top)
2211 expr_t expr2 = av_set_lookup_and_remove (fromp, EXPR_VINSN (expr1));
2215 /* It may be that the expressions have different destination
2216 registers, in which case we need to check liveness here. */
2217 if (EXPR_SEPARABLE_P (expr1))
2219 int regno1 = (REG_P (EXPR_LHS (expr1))
2220 ? (int) expr_dest_regno (expr1) : -1);
2221 int regno2 = (REG_P (EXPR_LHS (expr2))
2222 ? (int) expr_dest_regno (expr2) : -1);
2224 /* ??? We don't have a way to check restrictions for
2225 *other* register on the current path, we did it only
2226 for the current target register. Give up. */
2227 if (regno1 != regno2)
2228 EXPR_TARGET_AVAILABLE (expr2) = -1;
2230 else if (EXPR_INSN_RTX (expr1) != EXPR_INSN_RTX (expr2))
2231 EXPR_TARGET_AVAILABLE (expr2) = -1;
2233 merge_expr (expr2, expr1, insn);
2234 av_set_add_nocopy (&in_both_set, expr2);
2235 av_set_iter_remove (&i);
2238 /* EXPR1 is present in TOP, but not in FROMP. Check it on
2240 set_unavailable_target_for_expr (expr1, from_lv_set);
2244 /* These expressions are not present in TOP. Check liveness
2245 restrictions on TO_LV_SET. */
2246 FOR_EACH_EXPR (expr1, i, *fromp)
2247 set_unavailable_target_for_expr (expr1, to_lv_set);
2249 join_distinct_sets (i.lp, &in_both_set);
2250 join_distinct_sets (to_tailp, fromp);
2253 /* Clear av_set pointed to by SETP. */
2255 av_set_clear (av_set_t *setp)
2260 FOR_EACH_EXPR_1 (expr, i, setp)
2261 av_set_iter_remove (&i);
2263 gcc_assert (*setp == NULL);
2266 /* Leave only one non-speculative element in the SETP. */
2268 av_set_leave_one_nonspec (av_set_t *setp)
2272 bool has_one_nonspec = false;
2274 /* Keep all speculative exprs, and leave one non-speculative
2276 FOR_EACH_EXPR_1 (expr, i, setp)
2278 if (!EXPR_SPEC_DONE_DS (expr))
2280 if (has_one_nonspec)
2281 av_set_iter_remove (&i);
2283 has_one_nonspec = true;
2288 /* Return the N'th element of the SET. */
2290 av_set_element (av_set_t set, int n)
2295 FOR_EACH_EXPR (expr, i, set)
2303 /* Deletes all expressions from AVP that are conditional branches (IFs). */
2305 av_set_substract_cond_branches (av_set_t *avp)
2310 FOR_EACH_EXPR_1 (expr, i, avp)
2311 if (vinsn_cond_branch_p (EXPR_VINSN (expr)))
2312 av_set_iter_remove (&i);
2315 /* Multiplies usefulness attribute of each member of av-set *AVP by
2316 value PROB / ALL_PROB. */
2318 av_set_split_usefulness (av_set_t av, int prob, int all_prob)
2323 FOR_EACH_EXPR (expr, i, av)
2324 EXPR_USEFULNESS (expr) = (all_prob
2325 ? (EXPR_USEFULNESS (expr) * prob) / all_prob
2329 /* Leave in AVP only those expressions, which are present in AV,
2332 av_set_intersect (av_set_t *avp, av_set_t av)
2337 FOR_EACH_EXPR_1 (expr, i, avp)
2338 if (av_set_lookup (av, EXPR_VINSN (expr)) == NULL)
2339 av_set_iter_remove (&i);
2344 /* Dependence hooks to initialize insn data. */
2346 /* This is used in hooks callable from dependence analysis when initializing
2347 instruction's data. */
2350 /* Where the dependence was found (lhs/rhs). */
2353 /* The actual data object to initialize. */
2356 /* True when the insn should not be made clonable. */
2357 bool force_unique_p;
2359 /* True when insn should be treated as of type USE, i.e. never renamed. */
2361 } deps_init_id_data;
2364 /* Setup ID for INSN. FORCE_UNIQUE_P is true when INSN should not be
2367 setup_id_for_insn (idata_t id, insn_t insn, bool force_unique_p)
2371 /* Determine whether INSN could be cloned and return appropriate vinsn type.
2372 That clonable insns which can be separated into lhs and rhs have type SET.
2373 Other clonable insns have type USE. */
2374 type = GET_CODE (insn);
2376 /* Only regular insns could be cloned. */
2377 if (type == INSN && !force_unique_p)
2379 else if (type == JUMP_INSN && simplejump_p (insn))
2381 else if (type == DEBUG_INSN)
2382 type = !force_unique_p ? USE : INSN;
2384 IDATA_TYPE (id) = type;
2385 IDATA_REG_SETS (id) = get_clear_regset_from_pool ();
2386 IDATA_REG_USES (id) = get_clear_regset_from_pool ();
2387 IDATA_REG_CLOBBERS (id) = get_clear_regset_from_pool ();
2390 /* Start initializing insn data. */
2392 deps_init_id_start_insn (insn_t insn)
2394 gcc_assert (deps_init_id_data.where == DEPS_IN_NOWHERE);
2396 setup_id_for_insn (deps_init_id_data.id, insn,
2397 deps_init_id_data.force_unique_p);
2398 deps_init_id_data.where = DEPS_IN_INSN;
2401 /* Start initializing lhs data. */
2403 deps_init_id_start_lhs (rtx lhs)
2405 gcc_assert (deps_init_id_data.where == DEPS_IN_INSN);
2406 gcc_assert (IDATA_LHS (deps_init_id_data.id) == NULL);
2408 if (IDATA_TYPE (deps_init_id_data.id) == SET)
2410 IDATA_LHS (deps_init_id_data.id) = lhs;
2411 deps_init_id_data.where = DEPS_IN_LHS;
2415 /* Finish initializing lhs data. */
2417 deps_init_id_finish_lhs (void)
2419 deps_init_id_data.where = DEPS_IN_INSN;
2422 /* Note a set of REGNO. */
2424 deps_init_id_note_reg_set (int regno)
2426 haifa_note_reg_set (regno);
2428 if (deps_init_id_data.where == DEPS_IN_RHS)
2429 deps_init_id_data.force_use_p = true;
2431 if (IDATA_TYPE (deps_init_id_data.id) != PC)
2432 SET_REGNO_REG_SET (IDATA_REG_SETS (deps_init_id_data.id), regno);
2435 /* Make instructions that set stack registers to be ineligible for
2436 renaming to avoid issues with find_used_regs. */
2437 if (IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG))
2438 deps_init_id_data.force_use_p = true;
2442 /* Note a clobber of REGNO. */
2444 deps_init_id_note_reg_clobber (int regno)
2446 haifa_note_reg_clobber (regno);
2448 if (deps_init_id_data.where == DEPS_IN_RHS)
2449 deps_init_id_data.force_use_p = true;
2451 if (IDATA_TYPE (deps_init_id_data.id) != PC)
2452 SET_REGNO_REG_SET (IDATA_REG_CLOBBERS (deps_init_id_data.id), regno);
2455 /* Note a use of REGNO. */
2457 deps_init_id_note_reg_use (int regno)
2459 haifa_note_reg_use (regno);
2461 if (IDATA_TYPE (deps_init_id_data.id) != PC)
2462 SET_REGNO_REG_SET (IDATA_REG_USES (deps_init_id_data.id), regno);
2465 /* Start initializing rhs data. */
2467 deps_init_id_start_rhs (rtx rhs)
2469 gcc_assert (deps_init_id_data.where == DEPS_IN_INSN);
2471 /* And there was no sel_deps_reset_to_insn (). */
2472 if (IDATA_LHS (deps_init_id_data.id) != NULL)
2474 IDATA_RHS (deps_init_id_data.id) = rhs;
2475 deps_init_id_data.where = DEPS_IN_RHS;
2479 /* Finish initializing rhs data. */
2481 deps_init_id_finish_rhs (void)
2483 gcc_assert (deps_init_id_data.where == DEPS_IN_RHS
2484 || deps_init_id_data.where == DEPS_IN_INSN);
2485 deps_init_id_data.where = DEPS_IN_INSN;
2488 /* Finish initializing insn data. */
2490 deps_init_id_finish_insn (void)
2492 gcc_assert (deps_init_id_data.where == DEPS_IN_INSN);
2494 if (IDATA_TYPE (deps_init_id_data.id) == SET)
2496 rtx lhs = IDATA_LHS (deps_init_id_data.id);
2497 rtx rhs = IDATA_RHS (deps_init_id_data.id);
2499 if (lhs == NULL || rhs == NULL || !lhs_and_rhs_separable_p (lhs, rhs)
2500 || deps_init_id_data.force_use_p)
2502 /* This should be a USE, as we don't want to schedule its RHS
2503 separately. However, we still want to have them recorded
2504 for the purposes of substitution. That's why we don't
2505 simply call downgrade_to_use () here. */
2506 gcc_assert (IDATA_TYPE (deps_init_id_data.id) == SET);
2507 gcc_assert (!lhs == !rhs);
2509 IDATA_TYPE (deps_init_id_data.id) = USE;
2513 deps_init_id_data.where = DEPS_IN_NOWHERE;
2516 /* This is dependence info used for initializing insn's data. */
2517 static struct sched_deps_info_def deps_init_id_sched_deps_info;
2519 /* This initializes most of the static part of the above structure. */
2520 static const struct sched_deps_info_def const_deps_init_id_sched_deps_info =
2524 deps_init_id_start_insn,
2525 deps_init_id_finish_insn,
2526 deps_init_id_start_lhs,
2527 deps_init_id_finish_lhs,
2528 deps_init_id_start_rhs,
2529 deps_init_id_finish_rhs,
2530 deps_init_id_note_reg_set,
2531 deps_init_id_note_reg_clobber,
2532 deps_init_id_note_reg_use,
2533 NULL, /* note_mem_dep */
2534 NULL, /* note_dep */
2537 0, /* use_deps_list */
2538 0 /* generate_spec_deps */
2541 /* Initialize INSN's lhs and rhs in ID. When FORCE_UNIQUE_P is true,
2542 we don't actually need information about lhs and rhs. */
2544 setup_id_lhs_rhs (idata_t id, insn_t insn, bool force_unique_p)
2546 rtx pat = PATTERN (insn);
2548 if (NONJUMP_INSN_P (insn)
2549 && GET_CODE (pat) == SET
2552 IDATA_RHS (id) = SET_SRC (pat);
2553 IDATA_LHS (id) = SET_DEST (pat);
2556 IDATA_LHS (id) = IDATA_RHS (id) = NULL;
2559 /* Possibly downgrade INSN to USE. */
2561 maybe_downgrade_id_to_use (idata_t id, insn_t insn)
2563 bool must_be_use = false;
2564 unsigned uid = INSN_UID (insn);
2566 rtx lhs = IDATA_LHS (id);
2567 rtx rhs = IDATA_RHS (id);
2569 /* We downgrade only SETs. */
2570 if (IDATA_TYPE (id) != SET)
2573 if (!lhs || !lhs_and_rhs_separable_p (lhs, rhs))
2575 IDATA_TYPE (id) = USE;
2579 for (rec = DF_INSN_UID_DEFS (uid); *rec; rec++)
2583 if (DF_REF_INSN (def)
2584 && DF_REF_FLAGS_IS_SET (def, DF_REF_PRE_POST_MODIFY)
2585 && loc_mentioned_in_p (DF_REF_LOC (def), IDATA_RHS (id)))
2592 /* Make instructions that set stack registers to be ineligible for
2593 renaming to avoid issues with find_used_regs. */
2594 if (IN_RANGE (DF_REF_REGNO (def), FIRST_STACK_REG, LAST_STACK_REG))
2603 IDATA_TYPE (id) = USE;
2606 /* Setup register sets describing INSN in ID. */
2608 setup_id_reg_sets (idata_t id, insn_t insn)
2610 unsigned uid = INSN_UID (insn);
2612 regset tmp = get_clear_regset_from_pool ();
2614 for (rec = DF_INSN_UID_DEFS (uid); *rec; rec++)
2617 unsigned int regno = DF_REF_REGNO (def);
2619 /* Post modifies are treated like clobbers by sched-deps.c. */
2620 if (DF_REF_FLAGS_IS_SET (def, (DF_REF_MUST_CLOBBER
2621 | DF_REF_PRE_POST_MODIFY)))
2622 SET_REGNO_REG_SET (IDATA_REG_CLOBBERS (id), regno);
2623 else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
2625 SET_REGNO_REG_SET (IDATA_REG_SETS (id), regno);
2628 /* For stack registers, treat writes to them as writes
2629 to the first one to be consistent with sched-deps.c. */
2630 if (IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG))
2631 SET_REGNO_REG_SET (IDATA_REG_SETS (id), FIRST_STACK_REG);
2634 /* Mark special refs that generate read/write def pair. */
2635 if (DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL)
2636 || regno == STACK_POINTER_REGNUM)
2637 bitmap_set_bit (tmp, regno);
2640 for (rec = DF_INSN_UID_USES (uid); *rec; rec++)
2643 unsigned int regno = DF_REF_REGNO (use);
2645 /* When these refs are met for the first time, skip them, as
2646 these uses are just counterparts of some defs. */
2647 if (bitmap_bit_p (tmp, regno))
2648 bitmap_clear_bit (tmp, regno);
2649 else if (! DF_REF_FLAGS_IS_SET (use, DF_REF_CALL_STACK_USAGE))
2651 SET_REGNO_REG_SET (IDATA_REG_USES (id), regno);
2654 /* For stack registers, treat reads from them as reads from
2655 the first one to be consistent with sched-deps.c. */
2656 if (IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG))
2657 SET_REGNO_REG_SET (IDATA_REG_USES (id), FIRST_STACK_REG);
2662 return_regset_to_pool (tmp);
2665 /* Initialize instruction data for INSN in ID using DF's data. */
2667 init_id_from_df (idata_t id, insn_t insn, bool force_unique_p)
2669 gcc_assert (DF_INSN_UID_SAFE_GET (INSN_UID (insn)) != NULL);
2671 setup_id_for_insn (id, insn, force_unique_p);
2672 setup_id_lhs_rhs (id, insn, force_unique_p);
2674 if (INSN_NOP_P (insn))
2677 maybe_downgrade_id_to_use (id, insn);
2678 setup_id_reg_sets (id, insn);
2681 /* Initialize instruction data for INSN in ID. */
2683 deps_init_id (idata_t id, insn_t insn, bool force_unique_p)
2685 struct deps_desc _dc, *dc = &_dc;
2687 deps_init_id_data.where = DEPS_IN_NOWHERE;
2688 deps_init_id_data.id = id;
2689 deps_init_id_data.force_unique_p = force_unique_p;
2690 deps_init_id_data.force_use_p = false;
2692 init_deps (dc, false);
2694 memcpy (&deps_init_id_sched_deps_info,
2695 &const_deps_init_id_sched_deps_info,
2696 sizeof (deps_init_id_sched_deps_info));
2698 if (spec_info != NULL)
2699 deps_init_id_sched_deps_info.generate_spec_deps = 1;
2701 sched_deps_info = &deps_init_id_sched_deps_info;
2703 deps_analyze_insn (dc, insn);
2707 deps_init_id_data.id = NULL;
2712 /* Implement hooks for collecting fundamental insn properties like if insn is
2713 an ASM or is within a SCHED_GROUP. */
2715 /* True when a "one-time init" data for INSN was already inited. */
2717 first_time_insn_init (insn_t insn)
2719 return INSN_LIVE (insn) == NULL;
2722 /* Hash an entry in a transformed_insns hashtable. */
2724 hash_transformed_insns (const void *p)
2726 return VINSN_HASH_RTX (((const struct transformed_insns *) p)->vinsn_old);
2729 /* Compare the entries in a transformed_insns hashtable. */
2731 eq_transformed_insns (const void *p, const void *q)
2733 rtx i1 = VINSN_INSN_RTX (((const struct transformed_insns *) p)->vinsn_old);
2734 rtx i2 = VINSN_INSN_RTX (((const struct transformed_insns *) q)->vinsn_old);
2736 if (INSN_UID (i1) == INSN_UID (i2))
2738 return rtx_equal_p (PATTERN (i1), PATTERN (i2));
2741 /* Free an entry in a transformed_insns hashtable. */
2743 free_transformed_insns (void *p)
2745 struct transformed_insns *pti = (struct transformed_insns *) p;
2747 vinsn_detach (pti->vinsn_old);
2748 vinsn_detach (pti->vinsn_new);
2752 /* Init the s_i_d data for INSN which should be inited just once, when
2753 we first see the insn. */
2755 init_first_time_insn_data (insn_t insn)
2757 /* This should not be set if this is the first time we init data for
2759 gcc_assert (first_time_insn_init (insn));
2761 /* These are needed for nops too. */
2762 INSN_LIVE (insn) = get_regset_from_pool ();
2763 INSN_LIVE_VALID_P (insn) = false;
2765 if (!INSN_NOP_P (insn))
2767 INSN_ANALYZED_DEPS (insn) = BITMAP_ALLOC (NULL);
2768 INSN_FOUND_DEPS (insn) = BITMAP_ALLOC (NULL);
2769 INSN_TRANSFORMED_INSNS (insn)
2770 = htab_create (16, hash_transformed_insns,
2771 eq_transformed_insns, free_transformed_insns);
2772 init_deps (&INSN_DEPS_CONTEXT (insn), true);
2776 /* Free almost all above data for INSN that is scheduled already.
2777 Used for extra-large basic blocks. */
2779 free_data_for_scheduled_insn (insn_t insn)
2781 gcc_assert (! first_time_insn_init (insn));
2783 if (! INSN_ANALYZED_DEPS (insn))
2786 BITMAP_FREE (INSN_ANALYZED_DEPS (insn));
2787 BITMAP_FREE (INSN_FOUND_DEPS (insn));
2788 htab_delete (INSN_TRANSFORMED_INSNS (insn));
2790 /* This is allocated only for bookkeeping insns. */
2791 if (INSN_ORIGINATORS (insn))
2792 BITMAP_FREE (INSN_ORIGINATORS (insn));
2793 free_deps (&INSN_DEPS_CONTEXT (insn));
2795 INSN_ANALYZED_DEPS (insn) = NULL;
2797 /* Clear the readonly flag so we would ICE when trying to recalculate
2798 the deps context (as we believe that it should not happen). */
2799 (&INSN_DEPS_CONTEXT (insn))->readonly = 0;
2802 /* Free the same data as above for INSN. */
2804 free_first_time_insn_data (insn_t insn)
2806 gcc_assert (! first_time_insn_init (insn));
2808 free_data_for_scheduled_insn (insn);
2809 return_regset_to_pool (INSN_LIVE (insn));
2810 INSN_LIVE (insn) = NULL;
2811 INSN_LIVE_VALID_P (insn) = false;
2814 /* Initialize region-scope data structures for basic blocks. */
2816 init_global_and_expr_for_bb (basic_block bb)
2818 if (sel_bb_empty_p (bb))
2821 invalidate_av_set (bb);
2824 /* Data for global dependency analysis (to initialize CANT_MOVE and
2828 /* Previous insn. */
2832 /* Determine if INSN is in the sched_group, is an asm or should not be
2833 cloned. After that initialize its expr. */
2835 init_global_and_expr_for_insn (insn_t insn)
2840 if (NOTE_INSN_BASIC_BLOCK_P (insn))
2842 init_global_data.prev_insn = NULL_RTX;
2846 gcc_assert (INSN_P (insn));
2848 if (SCHED_GROUP_P (insn))
2849 /* Setup a sched_group. */
2851 insn_t prev_insn = init_global_data.prev_insn;
2854 INSN_SCHED_NEXT (prev_insn) = insn;
2856 init_global_data.prev_insn = insn;
2859 init_global_data.prev_insn = NULL_RTX;
2861 if (GET_CODE (PATTERN (insn)) == ASM_INPUT
2862 || asm_noperands (PATTERN (insn)) >= 0)
2863 /* Mark INSN as an asm. */
2864 INSN_ASM_P (insn) = true;
2867 bool force_unique_p;
2870 /* Certain instructions cannot be cloned, and frame related insns and
2871 the insn adjacent to NOTE_INSN_EPILOGUE_BEG cannot be moved out of
2873 if (prologue_epilogue_contains (insn))
2875 if (RTX_FRAME_RELATED_P (insn))
2876 CANT_MOVE (insn) = 1;
2880 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
2881 if (REG_NOTE_KIND (note) == REG_SAVE_NOTE
2882 && ((enum insn_note) INTVAL (XEXP (note, 0))
2883 == NOTE_INSN_EPILOGUE_BEG))
2885 CANT_MOVE (insn) = 1;
2889 force_unique_p = true;
2892 if (CANT_MOVE (insn)
2893 || INSN_ASM_P (insn)
2894 || SCHED_GROUP_P (insn)
2895 /* Exception handling insns are always unique. */
2896 || (cfun->can_throw_non_call_exceptions && can_throw_internal (insn))
2897 /* TRAP_IF though have an INSN code is control_flow_insn_p (). */
2898 || control_flow_insn_p (insn))
2899 force_unique_p = true;
2901 force_unique_p = false;
2903 if (targetm.sched.get_insn_spec_ds)
2905 spec_done_ds = targetm.sched.get_insn_spec_ds (insn);
2906 spec_done_ds = ds_get_max_dep_weak (spec_done_ds);
2911 /* Initialize INSN's expr. */
2912 init_expr (INSN_EXPR (insn), vinsn_create (insn, force_unique_p), 0,
2913 REG_BR_PROB_BASE, INSN_PRIORITY (insn), 0, BLOCK_NUM (insn),
2914 spec_done_ds, 0, 0, NULL, true, false, false, false,
2918 init_first_time_insn_data (insn);
2921 /* Scan the region and initialize instruction data for basic blocks BBS. */
2923 sel_init_global_and_expr (bb_vec_t bbs)
2925 /* ??? It would be nice to implement push / pop scheme for sched_infos. */
2926 const struct sched_scan_info_def ssi =
2928 NULL, /* extend_bb */
2929 init_global_and_expr_for_bb, /* init_bb */
2930 extend_insn_data, /* extend_insn */
2931 init_global_and_expr_for_insn /* init_insn */
2934 sched_scan (&ssi, bbs, NULL, NULL, NULL);
2937 /* Finalize region-scope data structures for basic blocks. */
2939 finish_global_and_expr_for_bb (basic_block bb)
2941 av_set_clear (&BB_AV_SET (bb));
2942 BB_AV_LEVEL (bb) = 0;
2945 /* Finalize INSN's data. */
2947 finish_global_and_expr_insn (insn_t insn)
2949 if (LABEL_P (insn) || NOTE_INSN_BASIC_BLOCK_P (insn))
2952 gcc_assert (INSN_P (insn));
2954 if (INSN_LUID (insn) > 0)
2956 free_first_time_insn_data (insn);
2957 INSN_WS_LEVEL (insn) = 0;
2958 CANT_MOVE (insn) = 0;
2960 /* We can no longer assert this, as vinsns of this insn could be
2961 easily live in other insn's caches. This should be changed to
2962 a counter-like approach among all vinsns. */
2963 gcc_assert (true || VINSN_COUNT (INSN_VINSN (insn)) == 1);
2964 clear_expr (INSN_EXPR (insn));
2968 /* Finalize per instruction data for the whole region. */
2970 sel_finish_global_and_expr (void)
2976 bbs = VEC_alloc (basic_block, heap, current_nr_blocks);
2978 for (i = 0; i < current_nr_blocks; i++)
2979 VEC_quick_push (basic_block, bbs, BASIC_BLOCK (BB_TO_BLOCK (i)));
2981 /* Clear AV_SETs and INSN_EXPRs. */
2983 const struct sched_scan_info_def ssi =
2985 NULL, /* extend_bb */
2986 finish_global_and_expr_for_bb, /* init_bb */
2987 NULL, /* extend_insn */
2988 finish_global_and_expr_insn /* init_insn */
2991 sched_scan (&ssi, bbs, NULL, NULL, NULL);
2994 VEC_free (basic_block, heap, bbs);
3001 /* In the below hooks, we merely calculate whether or not a dependence
3002 exists, and in what part of insn. However, we will need more data
3003 when we'll start caching dependence requests. */
3005 /* Container to hold information for dependency analysis. */
3010 /* A variable to track which part of rtx we are scanning in
3011 sched-deps.c: sched_analyze_insn (). */
3014 /* Current producer. */
3017 /* Current consumer. */
3020 /* Is SEL_DEPS_HAS_DEP_P[DEPS_IN_X] is true, then X has a dependence.
3021 X is from { INSN, LHS, RHS }. */
3022 ds_t has_dep_p[DEPS_IN_NOWHERE];
3023 } has_dependence_data;
3025 /* Start analyzing dependencies of INSN. */
3027 has_dependence_start_insn (insn_t insn ATTRIBUTE_UNUSED)
3029 gcc_assert (has_dependence_data.where == DEPS_IN_NOWHERE);
3031 has_dependence_data.where = DEPS_IN_INSN;
3034 /* Finish analyzing dependencies of an insn. */
3036 has_dependence_finish_insn (void)
3038 gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
3040 has_dependence_data.where = DEPS_IN_NOWHERE;
3043 /* Start analyzing dependencies of LHS. */
3045 has_dependence_start_lhs (rtx lhs ATTRIBUTE_UNUSED)
3047 gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
3049 if (VINSN_LHS (has_dependence_data.con) != NULL)
3050 has_dependence_data.where = DEPS_IN_LHS;
3053 /* Finish analyzing dependencies of an lhs. */
3055 has_dependence_finish_lhs (void)
3057 has_dependence_data.where = DEPS_IN_INSN;
3060 /* Start analyzing dependencies of RHS. */
3062 has_dependence_start_rhs (rtx rhs ATTRIBUTE_UNUSED)
3064 gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
3066 if (VINSN_RHS (has_dependence_data.con) != NULL)
3067 has_dependence_data.where = DEPS_IN_RHS;
3070 /* Start analyzing dependencies of an rhs. */
3072 has_dependence_finish_rhs (void)
3074 gcc_assert (has_dependence_data.where == DEPS_IN_RHS
3075 || has_dependence_data.where == DEPS_IN_INSN);
3077 has_dependence_data.where = DEPS_IN_INSN;
3080 /* Note a set of REGNO. */
3082 has_dependence_note_reg_set (int regno)
3084 struct deps_reg *reg_last = &has_dependence_data.dc->reg_last[regno];
3086 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3088 (has_dependence_data.con)))
3090 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3092 if (reg_last->sets != NULL
3093 || reg_last->clobbers != NULL)
3094 *dsp = (*dsp & ~SPECULATIVE) | DEP_OUTPUT;
3097 *dsp = (*dsp & ~SPECULATIVE) | DEP_ANTI;
3101 /* Note a clobber of REGNO. */
3103 has_dependence_note_reg_clobber (int regno)
3105 struct deps_reg *reg_last = &has_dependence_data.dc->reg_last[regno];
3107 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3109 (has_dependence_data.con)))
3111 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3114 *dsp = (*dsp & ~SPECULATIVE) | DEP_OUTPUT;
3117 *dsp = (*dsp & ~SPECULATIVE) | DEP_ANTI;
3121 /* Note a use of REGNO. */
3123 has_dependence_note_reg_use (int regno)
3125 struct deps_reg *reg_last = &has_dependence_data.dc->reg_last[regno];
3127 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3129 (has_dependence_data.con)))
3131 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3134 *dsp = (*dsp & ~SPECULATIVE) | DEP_TRUE;
3136 if (reg_last->clobbers)
3137 *dsp = (*dsp & ~SPECULATIVE) | DEP_ANTI;
3139 /* Handle BE_IN_SPEC. */
3142 ds_t pro_spec_checked_ds;
3144 pro_spec_checked_ds = INSN_SPEC_CHECKED_DS (has_dependence_data.pro);
3145 pro_spec_checked_ds = ds_get_max_dep_weak (pro_spec_checked_ds);
3147 if (pro_spec_checked_ds != 0)
3148 /* Merge BE_IN_SPEC bits into *DSP. */
3149 *dsp = ds_full_merge (*dsp, pro_spec_checked_ds,
3150 NULL_RTX, NULL_RTX);
3155 /* Note a memory dependence. */
3157 has_dependence_note_mem_dep (rtx mem ATTRIBUTE_UNUSED,
3158 rtx pending_mem ATTRIBUTE_UNUSED,
3159 insn_t pending_insn ATTRIBUTE_UNUSED,
3160 ds_t ds ATTRIBUTE_UNUSED)
3162 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3163 VINSN_INSN_RTX (has_dependence_data.con)))
3165 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3167 *dsp = ds_full_merge (ds, *dsp, pending_mem, mem);
3171 /* Note a dependence. */
3173 has_dependence_note_dep (insn_t pro ATTRIBUTE_UNUSED,
3174 ds_t ds ATTRIBUTE_UNUSED)
3176 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3177 VINSN_INSN_RTX (has_dependence_data.con)))
3179 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3181 *dsp = ds_full_merge (ds, *dsp, NULL_RTX, NULL_RTX);
3185 /* Mark the insn as having a hard dependence that prevents speculation. */
3187 sel_mark_hard_insn (rtx insn)
3191 /* Only work when we're in has_dependence_p mode.
3192 ??? This is a hack, this should actually be a hook. */
3193 if (!has_dependence_data.dc || !has_dependence_data.pro)
3196 gcc_assert (insn == VINSN_INSN_RTX (has_dependence_data.con));
3197 gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
3199 for (i = 0; i < DEPS_IN_NOWHERE; i++)
3200 has_dependence_data.has_dep_p[i] &= ~SPECULATIVE;
3203 /* This structure holds the hooks for the dependency analysis used when
3204 actually processing dependencies in the scheduler. */
3205 static struct sched_deps_info_def has_dependence_sched_deps_info;
3207 /* This initializes most of the fields of the above structure. */
3208 static const struct sched_deps_info_def const_has_dependence_sched_deps_info =
3212 has_dependence_start_insn,
3213 has_dependence_finish_insn,
3214 has_dependence_start_lhs,
3215 has_dependence_finish_lhs,
3216 has_dependence_start_rhs,
3217 has_dependence_finish_rhs,
3218 has_dependence_note_reg_set,
3219 has_dependence_note_reg_clobber,
3220 has_dependence_note_reg_use,
3221 has_dependence_note_mem_dep,
3222 has_dependence_note_dep,
3225 0, /* use_deps_list */
3226 0 /* generate_spec_deps */
3229 /* Initialize has_dependence_sched_deps_info with extra spec field. */
3231 setup_has_dependence_sched_deps_info (void)
3233 memcpy (&has_dependence_sched_deps_info,
3234 &const_has_dependence_sched_deps_info,
3235 sizeof (has_dependence_sched_deps_info));
3237 if (spec_info != NULL)
3238 has_dependence_sched_deps_info.generate_spec_deps = 1;
3240 sched_deps_info = &has_dependence_sched_deps_info;
3243 /* Remove all dependences found and recorded in has_dependence_data array. */
3245 sel_clear_has_dependence (void)
3249 for (i = 0; i < DEPS_IN_NOWHERE; i++)
3250 has_dependence_data.has_dep_p[i] = 0;
3253 /* Return nonzero if EXPR has is dependent upon PRED. Return the pointer
3254 to the dependence information array in HAS_DEP_PP. */
3256 has_dependence_p (expr_t expr, insn_t pred, ds_t **has_dep_pp)
3260 struct deps_desc *dc;
3262 if (INSN_SIMPLEJUMP_P (pred))
3263 /* Unconditional jump is just a transfer of control flow.
3267 dc = &INSN_DEPS_CONTEXT (pred);
3269 /* We init this field lazily. */
3270 if (dc->reg_last == NULL)
3271 init_deps_reg_last (dc);
3275 has_dependence_data.pro = NULL;
3276 /* Initialize empty dep context with information about PRED. */
3277 advance_deps_context (dc, pred);
3281 has_dependence_data.where = DEPS_IN_NOWHERE;
3282 has_dependence_data.pro = pred;
3283 has_dependence_data.con = EXPR_VINSN (expr);
3284 has_dependence_data.dc = dc;
3286 sel_clear_has_dependence ();
3288 /* Now catch all dependencies that would be generated between PRED and
3290 setup_has_dependence_sched_deps_info ();
3291 deps_analyze_insn (dc, EXPR_INSN_RTX (expr));
3292 has_dependence_data.dc = NULL;
3294 /* When a barrier was found, set DEPS_IN_INSN bits. */
3295 if (dc->last_reg_pending_barrier == TRUE_BARRIER)
3296 has_dependence_data.has_dep_p[DEPS_IN_INSN] = DEP_TRUE;
3297 else if (dc->last_reg_pending_barrier == MOVE_BARRIER)
3298 has_dependence_data.has_dep_p[DEPS_IN_INSN] = DEP_ANTI;
3300 /* Do not allow stores to memory to move through checks. Currently
3301 we don't move this to sched-deps.c as the check doesn't have
3302 obvious places to which this dependence can be attached.
3303 FIMXE: this should go to a hook. */
3305 && MEM_P (EXPR_LHS (expr))
3306 && sel_insn_is_speculation_check (pred))
3307 has_dependence_data.has_dep_p[DEPS_IN_INSN] = DEP_ANTI;
3309 *has_dep_pp = has_dependence_data.has_dep_p;
3311 for (i = 0; i < DEPS_IN_NOWHERE; i++)
3312 ds = ds_full_merge (ds, has_dependence_data.has_dep_p[i],
3313 NULL_RTX, NULL_RTX);
3319 /* Dependence hooks implementation that checks dependence latency constraints
3320 on the insns being scheduled. The entry point for these routines is
3321 tick_check_p predicate. */
3325 /* An expr we are currently checking. */
3328 /* A minimal cycle for its scheduling. */
3331 /* Whether we have seen a true dependence while checking. */
3332 bool seen_true_dep_p;
3335 /* Update minimal scheduling cycle for tick_check_insn given that it depends
3336 on PRO with status DS and weight DW. */
3338 tick_check_dep_with_dw (insn_t pro_insn, ds_t ds, dw_t dw)
3340 expr_t con_expr = tick_check_data.expr;
3341 insn_t con_insn = EXPR_INSN_RTX (con_expr);
3343 if (con_insn != pro_insn)
3348 if (/* PROducer was removed from above due to pipelining. */
3349 !INSN_IN_STREAM_P (pro_insn)
3350 /* Or PROducer was originally on the next iteration regarding the
3352 || (INSN_SCHED_TIMES (pro_insn)
3353 - EXPR_SCHED_TIMES (con_expr)) > 1)
3354 /* Don't count this dependence. */
3358 if (dt == REG_DEP_TRUE)
3359 tick_check_data.seen_true_dep_p = true;
3361 gcc_assert (INSN_SCHED_CYCLE (pro_insn) > 0);
3364 dep_def _dep, *dep = &_dep;
3366 init_dep (dep, pro_insn, con_insn, dt);
3368 tick = INSN_SCHED_CYCLE (pro_insn) + dep_cost_1 (dep, dw);
3371 /* When there are several kinds of dependencies between pro and con,
3372 only REG_DEP_TRUE should be taken into account. */
3373 if (tick > tick_check_data.cycle
3374 && (dt == REG_DEP_TRUE || !tick_check_data.seen_true_dep_p))
3375 tick_check_data.cycle = tick;
3379 /* An implementation of note_dep hook. */
3381 tick_check_note_dep (insn_t pro, ds_t ds)
3383 tick_check_dep_with_dw (pro, ds, 0);
3386 /* An implementation of note_mem_dep hook. */
3388 tick_check_note_mem_dep (rtx mem1, rtx mem2, insn_t pro, ds_t ds)
3392 dw = (ds_to_dt (ds) == REG_DEP_TRUE
3393 ? estimate_dep_weak (mem1, mem2)
3396 tick_check_dep_with_dw (pro, ds, dw);
3399 /* This structure contains hooks for dependence analysis used when determining
3400 whether an insn is ready for scheduling. */
3401 static struct sched_deps_info_def tick_check_sched_deps_info =
3412 haifa_note_reg_clobber,
3414 tick_check_note_mem_dep,
3415 tick_check_note_dep,
3420 /* Estimate number of cycles from the current cycle of FENCE until EXPR can be
3421 scheduled. Return 0 if all data from producers in DC is ready. */
3423 tick_check_p (expr_t expr, deps_t dc, fence_t fence)
3426 /* Initialize variables. */
3427 tick_check_data.expr = expr;
3428 tick_check_data.cycle = 0;
3429 tick_check_data.seen_true_dep_p = false;
3430 sched_deps_info = &tick_check_sched_deps_info;
3432 gcc_assert (!dc->readonly);
3434 deps_analyze_insn (dc, EXPR_INSN_RTX (expr));
3437 cycles_left = tick_check_data.cycle - FENCE_CYCLE (fence);
3439 return cycles_left >= 0 ? cycles_left : 0;
3443 /* Functions to work with insns. */
3445 /* Returns true if LHS of INSN is the same as DEST of an insn
3448 lhs_of_insn_equals_to_dest_p (insn_t insn, rtx dest)
3450 rtx lhs = INSN_LHS (insn);
3452 if (lhs == NULL || dest == NULL)
3455 return rtx_equal_p (lhs, dest);
3458 /* Return s_i_d entry of INSN. Callable from debugger. */
3460 insn_sid (insn_t insn)
3465 /* True when INSN is a speculative check. We can tell this by looking
3466 at the data structures of the selective scheduler, not by examining
3469 sel_insn_is_speculation_check (rtx insn)
3471 return s_i_d && !! INSN_SPEC_CHECKED_DS (insn);
3474 /* Extracts machine mode MODE and destination location DST_LOC
3477 get_dest_and_mode (rtx insn, rtx *dst_loc, enum machine_mode *mode)
3479 rtx pat = PATTERN (insn);
3481 gcc_assert (dst_loc);
3482 gcc_assert (GET_CODE (pat) == SET);
3484 *dst_loc = SET_DEST (pat);
3486 gcc_assert (*dst_loc);
3487 gcc_assert (MEM_P (*dst_loc) || REG_P (*dst_loc));
3490 *mode = GET_MODE (*dst_loc);
3493 /* Returns true when moving through JUMP will result in bookkeeping
3496 bookkeeping_can_be_created_if_moved_through_p (insn_t jump)
3501 FOR_EACH_SUCC (succ, si, jump)
3502 if (sel_num_cfg_preds_gt_1 (succ))
3508 /* Return 'true' if INSN is the only one in its basic block. */
3510 insn_is_the_only_one_in_bb_p (insn_t insn)
3512 return sel_bb_head_p (insn) && sel_bb_end_p (insn);
3515 #ifdef ENABLE_CHECKING
3516 /* Check that the region we're scheduling still has at most one
3519 verify_backedges (void)
3527 for (i = 0; i < current_nr_blocks; i++)
3528 FOR_EACH_EDGE (e, ei, BASIC_BLOCK (BB_TO_BLOCK (i))->succs)
3529 if (in_current_region_p (e->dest)
3530 && BLOCK_TO_BB (e->dest->index) < i)
3533 gcc_assert (n <= 1);
3539 /* Functions to work with control flow. */
3541 /* Recompute BLOCK_TO_BB and BB_FOR_BLOCK for current region so that blocks
3542 are sorted in topological order (it might have been invalidated by
3543 redirecting an edge). */
3545 sel_recompute_toporder (void)
3548 int *postorder, n_blocks;
3550 postorder = XALLOCAVEC (int, n_basic_blocks);
3551 n_blocks = post_order_compute (postorder, false, false);
3553 rgn = CONTAINING_RGN (BB_TO_BLOCK (0));
3554 for (n = 0, i = n_blocks - 1; i >= 0; i--)
3555 if (CONTAINING_RGN (postorder[i]) == rgn)
3557 BLOCK_TO_BB (postorder[i]) = n;
3558 BB_TO_BLOCK (n) = postorder[i];
3562 /* Assert that we updated info for all blocks. We may miss some blocks if
3563 this function is called when redirecting an edge made a block
3564 unreachable, but that block is not deleted yet. */
3565 gcc_assert (n == RGN_NR_BLOCKS (rgn));
3568 /* Tidy the possibly empty block BB. */
3570 maybe_tidy_empty_bb (basic_block bb)
3572 basic_block succ_bb, pred_bb;
3577 /* Keep empty bb only if this block immediately precedes EXIT and
3578 has incoming non-fallthrough edge, or it has no predecessors or
3579 successors. Otherwise remove it. */
3580 if (!sel_bb_empty_p (bb)
3581 || (single_succ_p (bb)
3582 && single_succ (bb) == EXIT_BLOCK_PTR
3583 && (!single_pred_p (bb)
3584 || !(single_pred_edge (bb)->flags & EDGE_FALLTHRU)))
3585 || EDGE_COUNT (bb->preds) == 0
3586 || EDGE_COUNT (bb->succs) == 0)
3589 /* Do not attempt to redirect complex edges. */
3590 FOR_EACH_EDGE (e, ei, bb->preds)
3591 if (e->flags & EDGE_COMPLEX)
3594 free_data_sets (bb);
3596 /* Do not delete BB if it has more than one successor.
3597 That can occur when we moving a jump. */
3598 if (!single_succ_p (bb))
3600 gcc_assert (can_merge_blocks_p (bb->prev_bb, bb));
3601 sel_merge_blocks (bb->prev_bb, bb);
3605 succ_bb = single_succ (bb);
3609 /* Redirect all non-fallthru edges to the next bb. */
3614 FOR_EACH_EDGE (e, ei, bb->preds)
3618 if (!(e->flags & EDGE_FALLTHRU))
3620 /* We can not invalidate computed topological order by moving
3621 the edge destination block (E->SUCC) along a fallthru edge. */
3622 sel_redirect_edge_and_branch (e, succ_bb);
3626 /* If the edge is fallthru, but PRED_BB ends in a conditional jump
3627 to BB (so there is no non-fallthru edge from PRED_BB to BB), we
3628 still have to adjust it. */
3629 else if (single_succ_p (pred_bb) && any_condjump_p (BB_END (pred_bb)))
3631 /* If possible, try to remove the unneeded conditional jump. */
3632 if (INSN_SCHED_TIMES (BB_END (pred_bb)) == 0
3633 && !IN_CURRENT_FENCE_P (BB_END (pred_bb)))
3635 if (!sel_remove_insn (BB_END (pred_bb), false, false))
3636 tidy_fallthru_edge (e);
3639 sel_redirect_edge_and_branch (e, succ_bb);
3646 if (can_merge_blocks_p (bb->prev_bb, bb))
3647 sel_merge_blocks (bb->prev_bb, bb);
3650 /* This is a block without fallthru predecessor. Just delete it. */
3651 gcc_assert (pred_bb != NULL);
3653 if (in_current_region_p (pred_bb))
3654 move_bb_info (pred_bb, bb);
3655 remove_empty_bb (bb, true);
3661 /* Tidy the control flow after we have removed original insn from
3662 XBB. Return true if we have removed some blocks. When FULL_TIDYING
3663 is true, also try to optimize control flow on non-empty blocks. */
3665 tidy_control_flow (basic_block xbb, bool full_tidying)
3667 bool changed = true;
3670 /* First check whether XBB is empty. */
3671 changed = maybe_tidy_empty_bb (xbb);
3672 if (changed || !full_tidying)
3675 /* Check if there is a unnecessary jump after insn left. */
3676 if (jump_leads_only_to_bb_p (BB_END (xbb), xbb->next_bb)
3677 && INSN_SCHED_TIMES (BB_END (xbb)) == 0
3678 && !IN_CURRENT_FENCE_P (BB_END (xbb)))
3680 if (sel_remove_insn (BB_END (xbb), false, false))
3682 tidy_fallthru_edge (EDGE_SUCC (xbb, 0));
3685 first = sel_bb_head (xbb);
3686 last = sel_bb_end (xbb);
3687 if (MAY_HAVE_DEBUG_INSNS)
3689 if (first != last && DEBUG_INSN_P (first))
3691 first = NEXT_INSN (first);
3692 while (first != last && (DEBUG_INSN_P (first) || NOTE_P (first)));
3694 if (first != last && DEBUG_INSN_P (last))
3696 last = PREV_INSN (last);
3697 while (first != last && (DEBUG_INSN_P (last) || NOTE_P (last)));
3699 /* Check if there is an unnecessary jump in previous basic block leading
3700 to next basic block left after removing INSN from stream.
3701 If it is so, remove that jump and redirect edge to current
3702 basic block (where there was INSN before deletion). This way
3703 when NOP will be deleted several instructions later with its
3704 basic block we will not get a jump to next instruction, which
3707 && !sel_bb_empty_p (xbb)
3708 && INSN_NOP_P (last)
3709 /* Flow goes fallthru from current block to the next. */
3710 && EDGE_COUNT (xbb->succs) == 1
3711 && (EDGE_SUCC (xbb, 0)->flags & EDGE_FALLTHRU)
3712 /* When successor is an EXIT block, it may not be the next block. */
3713 && single_succ (xbb) != EXIT_BLOCK_PTR
3714 /* And unconditional jump in previous basic block leads to
3715 next basic block of XBB and this jump can be safely removed. */
3716 && in_current_region_p (xbb->prev_bb)
3717 && jump_leads_only_to_bb_p (BB_END (xbb->prev_bb), xbb->next_bb)
3718 && INSN_SCHED_TIMES (BB_END (xbb->prev_bb)) == 0
3719 /* Also this jump is not at the scheduling boundary. */
3720 && !IN_CURRENT_FENCE_P (BB_END (xbb->prev_bb)))
3722 bool recompute_toporder_p;
3723 /* Clear data structures of jump - jump itself will be removed
3724 by sel_redirect_edge_and_branch. */
3725 clear_expr (INSN_EXPR (BB_END (xbb->prev_bb)));
3726 recompute_toporder_p
3727 = sel_redirect_edge_and_branch (EDGE_SUCC (xbb->prev_bb, 0), xbb);
3729 gcc_assert (EDGE_SUCC (xbb->prev_bb, 0)->flags & EDGE_FALLTHRU);
3731 /* It can turn out that after removing unused jump, basic block
3732 that contained that jump, becomes empty too. In such case
3734 if (sel_bb_empty_p (xbb->prev_bb))
3735 changed = maybe_tidy_empty_bb (xbb->prev_bb);
3736 if (recompute_toporder_p)
3737 sel_recompute_toporder ();
3740 #ifdef ENABLE_CHECKING
3741 verify_backedges ();
3747 /* Purge meaningless empty blocks in the middle of a region. */
3749 purge_empty_blocks (void)
3751 /* Do not attempt to delete preheader. */
3752 int i = sel_is_loop_preheader_p (BASIC_BLOCK (BB_TO_BLOCK (0))) ? 1 : 0;
3754 while (i < current_nr_blocks)
3756 basic_block b = BASIC_BLOCK (BB_TO_BLOCK (i));
3758 if (maybe_tidy_empty_bb (b))
3765 /* Rip-off INSN from the insn stream. When ONLY_DISCONNECT is true,
3766 do not delete insn's data, because it will be later re-emitted.
3767 Return true if we have removed some blocks afterwards. */
3769 sel_remove_insn (insn_t insn, bool only_disconnect, bool full_tidying)
3771 basic_block bb = BLOCK_FOR_INSN (insn);
3773 gcc_assert (INSN_IN_STREAM_P (insn));
3775 if (DEBUG_INSN_P (insn) && BB_AV_SET_VALID_P (bb))
3780 /* When we remove a debug insn that is head of a BB, it remains
3781 in the AV_SET of the block, but it shouldn't. */
3782 FOR_EACH_EXPR_1 (expr, i, &BB_AV_SET (bb))
3783 if (EXPR_INSN_RTX (expr) == insn)
3785 av_set_iter_remove (&i);
3790 if (only_disconnect)
3792 insn_t prev = PREV_INSN (insn);
3793 insn_t next = NEXT_INSN (insn);
3794 basic_block bb = BLOCK_FOR_INSN (insn);
3796 NEXT_INSN (prev) = next;
3797 PREV_INSN (next) = prev;
3799 if (BB_HEAD (bb) == insn)
3801 gcc_assert (BLOCK_FOR_INSN (prev) == bb);
3802 BB_HEAD (bb) = prev;
3804 if (BB_END (bb) == insn)
3810 clear_expr (INSN_EXPR (insn));
3813 /* It is necessary to null this fields before calling add_insn (). */
3814 PREV_INSN (insn) = NULL_RTX;
3815 NEXT_INSN (insn) = NULL_RTX;
3817 return tidy_control_flow (bb, full_tidying);
3820 /* Estimate number of the insns in BB. */
3822 sel_estimate_number_of_insns (basic_block bb)
3825 insn_t insn = NEXT_INSN (BB_HEAD (bb)), next_tail = NEXT_INSN (BB_END (bb));
3827 for (; insn != next_tail; insn = NEXT_INSN (insn))
3828 if (NONDEBUG_INSN_P (insn))
3834 /* We don't need separate luids for notes or labels. */
3836 sel_luid_for_non_insn (rtx x)
3838 gcc_assert (NOTE_P (x) || LABEL_P (x));
3843 /* Return seqno of the only predecessor of INSN. */
3845 get_seqno_of_a_pred (insn_t insn)
3849 gcc_assert (INSN_SIMPLEJUMP_P (insn));
3851 if (!sel_bb_head_p (insn))
3852 seqno = INSN_SEQNO (PREV_INSN (insn));
3855 basic_block bb = BLOCK_FOR_INSN (insn);
3857 if (single_pred_p (bb)
3858 && !in_current_region_p (single_pred (bb)))
3860 /* We can have preds outside a region when splitting edges
3861 for pipelining of an outer loop. Use succ instead.
3862 There should be only one of them. */
3867 gcc_assert (flag_sel_sched_pipelining_outer_loops
3868 && current_loop_nest);
3869 FOR_EACH_SUCC_1 (succ, si, insn,
3870 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
3876 gcc_assert (succ != NULL);
3877 seqno = INSN_SEQNO (succ);
3884 cfg_preds (BLOCK_FOR_INSN (insn), &preds, &n);
3885 gcc_assert (n == 1);
3887 seqno = INSN_SEQNO (preds[0]);
3896 /* Find the proper seqno for inserting at INSN. Returns -1 if no predecessors
3897 with positive seqno exist. */
3899 get_seqno_by_preds (rtx insn)
3901 basic_block bb = BLOCK_FOR_INSN (insn);
3902 rtx tmp = insn, head = BB_HEAD (bb);
3908 return INSN_SEQNO (tmp);
3910 tmp = PREV_INSN (tmp);
3912 cfg_preds (bb, &preds, &n);
3913 for (i = 0, seqno = -1; i < n; i++)
3914 seqno = MAX (seqno, INSN_SEQNO (preds[i]));
3921 /* Extend pass-scope data structures for basic blocks. */
3923 sel_extend_global_bb_info (void)
3925 VEC_safe_grow_cleared (sel_global_bb_info_def, heap, sel_global_bb_info,
3929 /* Extend region-scope data structures for basic blocks. */
3931 extend_region_bb_info (void)
3933 VEC_safe_grow_cleared (sel_region_bb_info_def, heap, sel_region_bb_info,
3937 /* Extend all data structures to fit for all basic blocks. */
3939 extend_bb_info (void)
3941 sel_extend_global_bb_info ();
3942 extend_region_bb_info ();
3945 /* Finalize pass-scope data structures for basic blocks. */
3947 sel_finish_global_bb_info (void)
3949 VEC_free (sel_global_bb_info_def, heap, sel_global_bb_info);
3952 /* Finalize region-scope data structures for basic blocks. */
3954 finish_region_bb_info (void)
3956 VEC_free (sel_region_bb_info_def, heap, sel_region_bb_info);
3960 /* Data for each insn in current region. */
3961 VEC (sel_insn_data_def, heap) *s_i_d = NULL;
3963 /* A vector for the insns we've emitted. */
3964 static insn_vec_t new_insns = NULL;
3966 /* Extend data structures for insns from current region. */
3968 extend_insn_data (void)
3972 sched_extend_target ();
3973 sched_deps_init (false);
3975 /* Extend data structures for insns from current region. */
3976 reserve = (sched_max_luid + 1
3977 - VEC_length (sel_insn_data_def, s_i_d));
3979 && ! VEC_space (sel_insn_data_def, s_i_d, reserve))
3983 if (sched_max_luid / 2 > 1024)
3984 size = sched_max_luid + 1024;
3986 size = 3 * sched_max_luid / 2;
3989 VEC_safe_grow_cleared (sel_insn_data_def, heap, s_i_d, size);
3993 /* Finalize data structures for insns from current region. */
3999 /* Clear here all dependence contexts that may have left from insns that were
4000 removed during the scheduling. */
4001 for (i = 0; i < VEC_length (sel_insn_data_def, s_i_d); i++)
4003 sel_insn_data_def *sid_entry = VEC_index (sel_insn_data_def, s_i_d, i);
4005 if (sid_entry->live)
4006 return_regset_to_pool (sid_entry->live);
4007 if (sid_entry->analyzed_deps)
4009 BITMAP_FREE (sid_entry->analyzed_deps);
4010 BITMAP_FREE (sid_entry->found_deps);
4011 htab_delete (sid_entry->transformed_insns);
4012 free_deps (&sid_entry->deps_context);
4014 if (EXPR_VINSN (&sid_entry->expr))
4016 clear_expr (&sid_entry->expr);
4018 /* Also, clear CANT_MOVE bit here, because we really don't want it
4019 to be passed to the next region. */
4020 CANT_MOVE_BY_LUID (i) = 0;
4024 VEC_free (sel_insn_data_def, heap, s_i_d);
4027 /* A proxy to pass initialization data to init_insn (). */
4028 static sel_insn_data_def _insn_init_ssid;
4029 static sel_insn_data_t insn_init_ssid = &_insn_init_ssid;
4031 /* If true create a new vinsn. Otherwise use the one from EXPR. */
4032 static bool insn_init_create_new_vinsn_p;
4034 /* Set all necessary data for initialization of the new insn[s]. */
4036 set_insn_init (expr_t expr, vinsn_t vi, int seqno)
4038 expr_t x = &insn_init_ssid->expr;
4040 copy_expr_onside (x, expr);
4043 insn_init_create_new_vinsn_p = false;
4044 change_vinsn_in_expr (x, vi);
4047 insn_init_create_new_vinsn_p = true;
4049 insn_init_ssid->seqno = seqno;
4053 /* Init data for INSN. */
4055 init_insn_data (insn_t insn)
4058 sel_insn_data_t ssid = insn_init_ssid;
4060 /* The fields mentioned below are special and hence are not being
4061 propagated to the new insns. */
4062 gcc_assert (!ssid->asm_p && ssid->sched_next == NULL
4063 && !ssid->after_stall_p && ssid->sched_cycle == 0);
4064 gcc_assert (INSN_P (insn) && INSN_LUID (insn) > 0);
4066 expr = INSN_EXPR (insn);
4067 copy_expr (expr, &ssid->expr);
4068 prepare_insn_expr (insn, ssid->seqno);
4070 if (insn_init_create_new_vinsn_p)
4071 change_vinsn_in_expr (expr, vinsn_create (insn, init_insn_force_unique_p));
4073 if (first_time_insn_init (insn))
4074 init_first_time_insn_data (insn);
4077 /* This is used to initialize spurious jumps generated by
4078 sel_redirect_edge (). */
4080 init_simplejump_data (insn_t insn)
4082 init_expr (INSN_EXPR (insn), vinsn_create (insn, false), 0,
4083 REG_BR_PROB_BASE, 0, 0, 0, 0, 0, 0, NULL, true, false, false,
4085 INSN_SEQNO (insn) = get_seqno_of_a_pred (insn);
4086 init_first_time_insn_data (insn);
4089 /* Perform deferred initialization of insns. This is used to process
4090 a new jump that may be created by redirect_edge. */
4092 sel_init_new_insn (insn_t insn, int flags)
4094 /* We create data structures for bb when the first insn is emitted in it. */
4096 && INSN_IN_STREAM_P (insn)
4097 && insn_is_the_only_one_in_bb_p (insn))
4100 create_initial_data_sets (BLOCK_FOR_INSN (insn));
4103 if (flags & INSN_INIT_TODO_LUID)
4104 sched_init_luids (NULL, NULL, NULL, insn);
4106 if (flags & INSN_INIT_TODO_SSID)
4108 extend_insn_data ();
4109 init_insn_data (insn);
4110 clear_expr (&insn_init_ssid->expr);
4113 if (flags & INSN_INIT_TODO_SIMPLEJUMP)
4115 extend_insn_data ();
4116 init_simplejump_data (insn);
4119 gcc_assert (CONTAINING_RGN (BLOCK_NUM (insn))
4120 == CONTAINING_RGN (BB_TO_BLOCK (0)));
4124 /* Functions to init/finish work with lv sets. */
4126 /* Init BB_LV_SET of BB from DF_LR_IN set of BB. */
4128 init_lv_set (basic_block bb)
4130 gcc_assert (!BB_LV_SET_VALID_P (bb));
4132 BB_LV_SET (bb) = get_regset_from_pool ();
4133 COPY_REG_SET (BB_LV_SET (bb), DF_LR_IN (bb));
4134 BB_LV_SET_VALID_P (bb) = true;
4137 /* Copy liveness information to BB from FROM_BB. */
4139 copy_lv_set_from (basic_block bb, basic_block from_bb)
4141 gcc_assert (!BB_LV_SET_VALID_P (bb));
4143 COPY_REG_SET (BB_LV_SET (bb), BB_LV_SET (from_bb));
4144 BB_LV_SET_VALID_P (bb) = true;
4147 /* Initialize lv set of all bb headers. */
4153 /* Initialize of LV sets. */
4157 /* Don't forget EXIT_BLOCK. */
4158 init_lv_set (EXIT_BLOCK_PTR);
4161 /* Release lv set of HEAD. */
4163 free_lv_set (basic_block bb)
4165 gcc_assert (BB_LV_SET (bb) != NULL);
4167 return_regset_to_pool (BB_LV_SET (bb));
4168 BB_LV_SET (bb) = NULL;
4169 BB_LV_SET_VALID_P (bb) = false;
4172 /* Finalize lv sets of all bb headers. */
4178 /* Don't forget EXIT_BLOCK. */
4179 free_lv_set (EXIT_BLOCK_PTR);
4187 /* Initialize an invalid AV_SET for BB.
4188 This set will be updated next time compute_av () process BB. */
4190 invalidate_av_set (basic_block bb)
4192 gcc_assert (BB_AV_LEVEL (bb) <= 0
4193 && BB_AV_SET (bb) == NULL);
4195 BB_AV_LEVEL (bb) = -1;
4198 /* Create initial data sets for BB (they will be invalid). */
4200 create_initial_data_sets (basic_block bb)
4203 BB_LV_SET_VALID_P (bb) = false;
4205 BB_LV_SET (bb) = get_regset_from_pool ();
4206 invalidate_av_set (bb);
4209 /* Free av set of BB. */
4211 free_av_set (basic_block bb)
4213 av_set_clear (&BB_AV_SET (bb));
4214 BB_AV_LEVEL (bb) = 0;
4217 /* Free data sets of BB. */
4219 free_data_sets (basic_block bb)
4225 /* Exchange lv sets of TO and FROM. */
4227 exchange_lv_sets (basic_block to, basic_block from)
4230 regset to_lv_set = BB_LV_SET (to);
4232 BB_LV_SET (to) = BB_LV_SET (from);
4233 BB_LV_SET (from) = to_lv_set;
4237 bool to_lv_set_valid_p = BB_LV_SET_VALID_P (to);
4239 BB_LV_SET_VALID_P (to) = BB_LV_SET_VALID_P (from);
4240 BB_LV_SET_VALID_P (from) = to_lv_set_valid_p;
4245 /* Exchange av sets of TO and FROM. */
4247 exchange_av_sets (basic_block to, basic_block from)
4250 av_set_t to_av_set = BB_AV_SET (to);
4252 BB_AV_SET (to) = BB_AV_SET (from);
4253 BB_AV_SET (from) = to_av_set;
4257 int to_av_level = BB_AV_LEVEL (to);
4259 BB_AV_LEVEL (to) = BB_AV_LEVEL (from);
4260 BB_AV_LEVEL (from) = to_av_level;
4264 /* Exchange data sets of TO and FROM. */
4266 exchange_data_sets (basic_block to, basic_block from)
4268 exchange_lv_sets (to, from);
4269 exchange_av_sets (to, from);
4272 /* Copy data sets of FROM to TO. */
4274 copy_data_sets (basic_block to, basic_block from)
4276 gcc_assert (!BB_LV_SET_VALID_P (to) && !BB_AV_SET_VALID_P (to));
4277 gcc_assert (BB_AV_SET (to) == NULL);
4279 BB_AV_LEVEL (to) = BB_AV_LEVEL (from);
4280 BB_LV_SET_VALID_P (to) = BB_LV_SET_VALID_P (from);
4282 if (BB_AV_SET_VALID_P (from))
4284 BB_AV_SET (to) = av_set_copy (BB_AV_SET (from));
4286 if (BB_LV_SET_VALID_P (from))
4288 gcc_assert (BB_LV_SET (to) != NULL);
4289 COPY_REG_SET (BB_LV_SET (to), BB_LV_SET (from));
4293 /* Return an av set for INSN, if any. */
4295 get_av_set (insn_t insn)
4299 gcc_assert (AV_SET_VALID_P (insn));
4301 if (sel_bb_head_p (insn))
4302 av_set = BB_AV_SET (BLOCK_FOR_INSN (insn));
4309 /* Implementation of AV_LEVEL () macro. Return AV_LEVEL () of INSN. */
4311 get_av_level (insn_t insn)
4315 gcc_assert (INSN_P (insn));
4317 if (sel_bb_head_p (insn))
4318 av_level = BB_AV_LEVEL (BLOCK_FOR_INSN (insn));
4320 av_level = INSN_WS_LEVEL (insn);
4327 /* Variables to work with control-flow graph. */
4329 /* The basic block that already has been processed by the sched_data_update (),
4330 but hasn't been in sel_add_bb () yet. */
4331 static VEC (basic_block, heap) *last_added_blocks = NULL;
4333 /* A pool for allocating successor infos. */
4336 /* A stack for saving succs_info structures. */
4337 struct succs_info *stack;
4342 /* Top of the stack. */
4345 /* Maximal value of the top. */
4349 /* Functions to work with control-flow graph. */
4351 /* Return basic block note of BB. */
4353 sel_bb_head (basic_block bb)
4357 if (bb == EXIT_BLOCK_PTR)
4359 gcc_assert (exit_insn != NULL_RTX);
4366 note = bb_note (bb);
4367 head = next_nonnote_insn (note);
4369 if (head && (BARRIER_P (head) || BLOCK_FOR_INSN (head) != bb))
4376 /* Return true if INSN is a basic block header. */
4378 sel_bb_head_p (insn_t insn)
4380 return sel_bb_head (BLOCK_FOR_INSN (insn)) == insn;
4383 /* Return last insn of BB. */
4385 sel_bb_end (basic_block bb)
4387 if (sel_bb_empty_p (bb))
4390 gcc_assert (bb != EXIT_BLOCK_PTR);
4395 /* Return true if INSN is the last insn in its basic block. */
4397 sel_bb_end_p (insn_t insn)
4399 return insn == sel_bb_end (BLOCK_FOR_INSN (insn));
4402 /* Return true if BB consist of single NOTE_INSN_BASIC_BLOCK. */
4404 sel_bb_empty_p (basic_block bb)
4406 return sel_bb_head (bb) == NULL;
4409 /* True when BB belongs to the current scheduling region. */
4411 in_current_region_p (basic_block bb)
4413 if (bb->index < NUM_FIXED_BLOCKS)
4416 return CONTAINING_RGN (bb->index) == CONTAINING_RGN (BB_TO_BLOCK (0));
4419 /* Return the block which is a fallthru bb of a conditional jump JUMP. */
4421 fallthru_bb_of_jump (rtx jump)
4426 if (any_uncondjump_p (jump))
4427 return single_succ (BLOCK_FOR_INSN (jump));
4429 if (!any_condjump_p (jump))
4432 /* A basic block that ends with a conditional jump may still have one successor
4433 (and be followed by a barrier), we are not interested. */
4434 if (single_succ_p (BLOCK_FOR_INSN (jump)))
4437 return FALLTHRU_EDGE (BLOCK_FOR_INSN (jump))->dest;
4440 /* Remove all notes from BB. */
4442 init_bb (basic_block bb)
4444 remove_notes (bb_note (bb), BB_END (bb));
4445 BB_NOTE_LIST (bb) = note_list;
4449 sel_init_bbs (bb_vec_t bbs, basic_block bb)
4451 const struct sched_scan_info_def ssi =
4453 extend_bb_info, /* extend_bb */
4454 init_bb, /* init_bb */
4455 NULL, /* extend_insn */
4456 NULL /* init_insn */
4459 sched_scan (&ssi, bbs, bb, new_insns, NULL);
4462 /* Restore notes for the whole region. */
4464 sel_restore_notes (void)
4469 for (bb = 0; bb < current_nr_blocks; bb++)
4471 basic_block first, last;
4473 first = EBB_FIRST_BB (bb);
4474 last = EBB_LAST_BB (bb)->next_bb;
4478 note_list = BB_NOTE_LIST (first);
4479 restore_other_notes (NULL, first);
4480 BB_NOTE_LIST (first) = NULL_RTX;
4482 FOR_BB_INSNS (first, insn)
4483 if (NONDEBUG_INSN_P (insn))
4484 reemit_notes (insn);
4486 first = first->next_bb;
4488 while (first != last);
4492 /* Free per-bb data structures. */
4494 sel_finish_bbs (void)
4496 sel_restore_notes ();
4498 /* Remove current loop preheader from this loop. */
4499 if (current_loop_nest)
4500 sel_remove_loop_preheader ();
4502 finish_region_bb_info ();
4505 /* Return true if INSN has a single successor of type FLAGS. */
4507 sel_insn_has_single_succ_p (insn_t insn, int flags)
4511 bool first_p = true;
4513 FOR_EACH_SUCC_1 (succ, si, insn, flags)
4524 /* Allocate successor's info. */
4525 static struct succs_info *
4526 alloc_succs_info (void)
4528 if (succs_info_pool.top == succs_info_pool.max_top)
4532 if (++succs_info_pool.max_top >= succs_info_pool.size)
4535 i = ++succs_info_pool.top;
4536 succs_info_pool.stack[i].succs_ok = VEC_alloc (rtx, heap, 10);
4537 succs_info_pool.stack[i].succs_other = VEC_alloc (rtx, heap, 10);
4538 succs_info_pool.stack[i].probs_ok = VEC_alloc (int, heap, 10);
4541 succs_info_pool.top++;
4543 return &succs_info_pool.stack[succs_info_pool.top];
4546 /* Free successor's info. */
4548 free_succs_info (struct succs_info * sinfo)
4550 gcc_assert (succs_info_pool.top >= 0
4551 && &succs_info_pool.stack[succs_info_pool.top] == sinfo);
4552 succs_info_pool.top--;
4554 /* Clear stale info. */
4555 VEC_block_remove (rtx, sinfo->succs_ok,
4556 0, VEC_length (rtx, sinfo->succs_ok));
4557 VEC_block_remove (rtx, sinfo->succs_other,
4558 0, VEC_length (rtx, sinfo->succs_other));
4559 VEC_block_remove (int, sinfo->probs_ok,
4560 0, VEC_length (int, sinfo->probs_ok));
4561 sinfo->all_prob = 0;
4562 sinfo->succs_ok_n = 0;
4563 sinfo->all_succs_n = 0;
4566 /* Compute successor info for INSN. FLAGS are the flags passed
4567 to the FOR_EACH_SUCC_1 iterator. */
4569 compute_succs_info (insn_t insn, short flags)
4573 struct succs_info *sinfo = alloc_succs_info ();
4575 /* Traverse *all* successors and decide what to do with each. */
4576 FOR_EACH_SUCC_1 (succ, si, insn, SUCCS_ALL)
4578 /* FIXME: this doesn't work for skipping to loop exits, as we don't
4579 perform code motion through inner loops. */
4580 short current_flags = si.current_flags & ~SUCCS_SKIP_TO_LOOP_EXITS;
4582 if (current_flags & flags)
4584 VEC_safe_push (rtx, heap, sinfo->succs_ok, succ);
4585 VEC_safe_push (int, heap, sinfo->probs_ok,
4586 /* FIXME: Improve calculation when skipping
4587 inner loop to exits. */
4589 ? si.e1->probability
4590 : REG_BR_PROB_BASE));
4591 sinfo->succs_ok_n++;
4594 VEC_safe_push (rtx, heap, sinfo->succs_other, succ);
4596 /* Compute all_prob. */
4598 sinfo->all_prob = REG_BR_PROB_BASE;
4600 sinfo->all_prob += si.e1->probability;
4602 sinfo->all_succs_n++;
4608 /* Return the predecessors of BB in PREDS and their number in N.
4609 Empty blocks are skipped. SIZE is used to allocate PREDS. */
4611 cfg_preds_1 (basic_block bb, insn_t **preds, int *n, int *size)
4616 gcc_assert (BLOCK_TO_BB (bb->index) != 0);
4618 FOR_EACH_EDGE (e, ei, bb->preds)
4620 basic_block pred_bb = e->src;
4621 insn_t bb_end = BB_END (pred_bb);
4623 if (!in_current_region_p (pred_bb))
4625 gcc_assert (flag_sel_sched_pipelining_outer_loops
4626 && current_loop_nest);
4630 if (sel_bb_empty_p (pred_bb))
4631 cfg_preds_1 (pred_bb, preds, n, size);
4635 *preds = XRESIZEVEC (insn_t, *preds,
4636 (*size = 2 * *size + 1));
4637 (*preds)[(*n)++] = bb_end;
4642 || (flag_sel_sched_pipelining_outer_loops
4643 && current_loop_nest));
4646 /* Find all predecessors of BB and record them in PREDS and their number
4647 in N. Empty blocks are skipped, and only normal (forward in-region)
4648 edges are processed. */
4650 cfg_preds (basic_block bb, insn_t **preds, int *n)
4656 cfg_preds_1 (bb, preds, n, &size);
4659 /* Returns true if we are moving INSN through join point. */
4661 sel_num_cfg_preds_gt_1 (insn_t insn)
4665 if (!sel_bb_head_p (insn) || INSN_BB (insn) == 0)
4668 bb = BLOCK_FOR_INSN (insn);
4672 if (EDGE_COUNT (bb->preds) > 1)
4675 gcc_assert (EDGE_PRED (bb, 0)->dest == bb);
4676 bb = EDGE_PRED (bb, 0)->src;
4678 if (!sel_bb_empty_p (bb))
4685 /* Returns true when BB should be the end of an ebb. Adapted from the
4686 code in sched-ebb.c. */
4688 bb_ends_ebb_p (basic_block bb)
4690 basic_block next_bb = bb_next_bb (bb);
4693 if (next_bb == EXIT_BLOCK_PTR
4694 || bitmap_bit_p (forced_ebb_heads, next_bb->index)
4695 || (LABEL_P (BB_HEAD (next_bb))
4696 /* NB: LABEL_NUSES () is not maintained outside of jump.c.
4697 Work around that. */
4698 && !single_pred_p (next_bb)))
4701 if (!in_current_region_p (next_bb))
4704 e = find_fallthru_edge (bb->succs);
4707 gcc_assert (e->dest == next_bb);
4715 /* Returns true when INSN and SUCC are in the same EBB, given that SUCC is a
4716 successor of INSN. */
4718 in_same_ebb_p (insn_t insn, insn_t succ)
4720 basic_block ptr = BLOCK_FOR_INSN (insn);
4724 if (ptr == BLOCK_FOR_INSN (succ))
4727 if (bb_ends_ebb_p (ptr))
4730 ptr = bb_next_bb (ptr);
4737 /* Recomputes the reverse topological order for the function and
4738 saves it in REV_TOP_ORDER_INDEX. REV_TOP_ORDER_INDEX_LEN is also
4739 modified appropriately. */
4741 recompute_rev_top_order (void)
4746 if (!rev_top_order_index || rev_top_order_index_len < last_basic_block)
4748 rev_top_order_index_len = last_basic_block;
4749 rev_top_order_index = XRESIZEVEC (int, rev_top_order_index,
4750 rev_top_order_index_len);
4753 postorder = XNEWVEC (int, n_basic_blocks);
4755 n_blocks = post_order_compute (postorder, true, false);
4756 gcc_assert (n_basic_blocks == n_blocks);
4758 /* Build reverse function: for each basic block with BB->INDEX == K
4759 rev_top_order_index[K] is it's reverse topological sort number. */
4760 for (i = 0; i < n_blocks; i++)
4762 gcc_assert (postorder[i] < rev_top_order_index_len);
4763 rev_top_order_index[postorder[i]] = i;
4769 /* Clear all flags from insns in BB that could spoil its rescheduling. */
4771 clear_outdated_rtx_info (basic_block bb)
4775 FOR_BB_INSNS (bb, insn)
4778 SCHED_GROUP_P (insn) = 0;
4779 INSN_AFTER_STALL_P (insn) = 0;
4780 INSN_SCHED_TIMES (insn) = 0;
4781 EXPR_PRIORITY_ADJ (INSN_EXPR (insn)) = 0;
4783 /* We cannot use the changed caches, as previously we could ignore
4784 the LHS dependence due to enabled renaming and transform
4785 the expression, and currently we'll be unable to do this. */
4786 htab_empty (INSN_TRANSFORMED_INSNS (insn));
4790 /* Add BB_NOTE to the pool of available basic block notes. */
4792 return_bb_to_pool (basic_block bb)
4794 rtx note = bb_note (bb);
4796 gcc_assert (NOTE_BASIC_BLOCK (note) == bb
4797 && bb->aux == NULL);
4799 /* It turns out that current cfg infrastructure does not support
4800 reuse of basic blocks. Don't bother for now. */
4801 /*VEC_safe_push (rtx, heap, bb_note_pool, note);*/
4804 /* Get a bb_note from pool or return NULL_RTX if pool is empty. */
4806 get_bb_note_from_pool (void)
4808 if (VEC_empty (rtx, bb_note_pool))
4812 rtx note = VEC_pop (rtx, bb_note_pool);
4814 PREV_INSN (note) = NULL_RTX;
4815 NEXT_INSN (note) = NULL_RTX;
4821 /* Free bb_note_pool. */
4823 free_bb_note_pool (void)
4825 VEC_free (rtx, heap, bb_note_pool);
4828 /* Setup scheduler pool and successor structure. */
4830 alloc_sched_pools (void)
4834 succs_size = MAX_WS + 1;
4835 succs_info_pool.stack = XCNEWVEC (struct succs_info, succs_size);
4836 succs_info_pool.size = succs_size;
4837 succs_info_pool.top = -1;
4838 succs_info_pool.max_top = -1;
4840 sched_lists_pool = create_alloc_pool ("sel-sched-lists",
4841 sizeof (struct _list_node), 500);
4844 /* Free the pools. */
4846 free_sched_pools (void)
4850 free_alloc_pool (sched_lists_pool);
4851 gcc_assert (succs_info_pool.top == -1);
4852 for (i = 0; i < succs_info_pool.max_top; i++)
4854 VEC_free (rtx, heap, succs_info_pool.stack[i].succs_ok);
4855 VEC_free (rtx, heap, succs_info_pool.stack[i].succs_other);
4856 VEC_free (int, heap, succs_info_pool.stack[i].probs_ok);
4858 free (succs_info_pool.stack);
4862 /* Returns a position in RGN where BB can be inserted retaining
4863 topological order. */
4865 find_place_to_insert_bb (basic_block bb, int rgn)
4867 bool has_preds_outside_rgn = false;
4871 /* Find whether we have preds outside the region. */
4872 FOR_EACH_EDGE (e, ei, bb->preds)
4873 if (!in_current_region_p (e->src))
4875 has_preds_outside_rgn = true;
4879 /* Recompute the top order -- needed when we have > 1 pred
4880 and in case we don't have preds outside. */
4881 if (flag_sel_sched_pipelining_outer_loops
4882 && (has_preds_outside_rgn || EDGE_COUNT (bb->preds) > 1))
4884 int i, bbi = bb->index, cur_bbi;
4886 recompute_rev_top_order ();
4887 for (i = RGN_NR_BLOCKS (rgn) - 1; i >= 0; i--)
4889 cur_bbi = BB_TO_BLOCK (i);
4890 if (rev_top_order_index[bbi]
4891 < rev_top_order_index[cur_bbi])
4895 /* We skipped the right block, so we increase i. We accomodate
4896 it for increasing by step later, so we decrease i. */
4899 else if (has_preds_outside_rgn)
4901 /* This is the case when we generate an extra empty block
4902 to serve as region head during pipelining. */
4903 e = EDGE_SUCC (bb, 0);
4904 gcc_assert (EDGE_COUNT (bb->succs) == 1
4905 && in_current_region_p (EDGE_SUCC (bb, 0)->dest)
4906 && (BLOCK_TO_BB (e->dest->index) == 0));
4910 /* We don't have preds outside the region. We should have
4911 the only pred, because the multiple preds case comes from
4912 the pipelining of outer loops, and that is handled above.
4913 Just take the bbi of this single pred. */
4914 if (EDGE_COUNT (bb->succs) > 0)
4918 gcc_assert (EDGE_COUNT (bb->preds) == 1);
4920 pred_bbi = EDGE_PRED (bb, 0)->src->index;
4921 return BLOCK_TO_BB (pred_bbi);
4924 /* BB has no successors. It is safe to put it in the end. */
4925 return current_nr_blocks - 1;
4928 /* Deletes an empty basic block freeing its data. */
4930 delete_and_free_basic_block (basic_block bb)
4932 gcc_assert (sel_bb_empty_p (bb));
4937 bitmap_clear_bit (blocks_to_reschedule, bb->index);
4939 /* Can't assert av_set properties because we use sel_aremove_bb
4940 when removing loop preheader from the region. At the point of
4941 removing the preheader we already have deallocated sel_region_bb_info. */
4942 gcc_assert (BB_LV_SET (bb) == NULL
4943 && !BB_LV_SET_VALID_P (bb)
4944 && BB_AV_LEVEL (bb) == 0
4945 && BB_AV_SET (bb) == NULL);
4947 delete_basic_block (bb);
4950 /* Add BB to the current region and update the region data. */
4952 add_block_to_current_region (basic_block bb)
4954 int i, pos, bbi = -2, rgn;
4956 rgn = CONTAINING_RGN (BB_TO_BLOCK (0));
4957 bbi = find_place_to_insert_bb (bb, rgn);
4959 pos = RGN_BLOCKS (rgn) + bbi;
4961 gcc_assert (RGN_HAS_REAL_EBB (rgn) == 0
4962 && ebb_head[bbi] == pos);
4964 /* Make a place for the new block. */
4967 for (i = RGN_BLOCKS (rgn + 1) - 1; i >= pos; i--)
4968 BLOCK_TO_BB (rgn_bb_table[i])++;
4970 memmove (rgn_bb_table + pos + 1,
4972 (RGN_BLOCKS (nr_regions) - pos) * sizeof (*rgn_bb_table));
4974 /* Initialize data for BB. */
4975 rgn_bb_table[pos] = bb->index;
4976 BLOCK_TO_BB (bb->index) = bbi;
4977 CONTAINING_RGN (bb->index) = rgn;
4979 RGN_NR_BLOCKS (rgn)++;
4981 for (i = rgn + 1; i <= nr_regions; i++)
4985 /* Remove BB from the current region and update the region data. */
4987 remove_bb_from_region (basic_block bb)
4989 int i, pos, bbi = -2, rgn;
4991 rgn = CONTAINING_RGN (BB_TO_BLOCK (0));
4992 bbi = BLOCK_TO_BB (bb->index);
4993 pos = RGN_BLOCKS (rgn) + bbi;
4995 gcc_assert (RGN_HAS_REAL_EBB (rgn) == 0
4996 && ebb_head[bbi] == pos);
4998 for (i = RGN_BLOCKS (rgn + 1) - 1; i >= pos; i--)
4999 BLOCK_TO_BB (rgn_bb_table[i])--;
5001 memmove (rgn_bb_table + pos,
5002 rgn_bb_table + pos + 1,
5003 (RGN_BLOCKS (nr_regions) - pos) * sizeof (*rgn_bb_table));
5005 RGN_NR_BLOCKS (rgn)--;
5006 for (i = rgn + 1; i <= nr_regions; i++)
5010 /* Add BB to the current region and update all data. If BB is NULL, add all
5011 blocks from last_added_blocks vector. */
5013 sel_add_bb (basic_block bb)
5015 /* Extend luids so that new notes will receive zero luids. */
5016 sched_init_luids (NULL, NULL, NULL, NULL);
5018 sel_init_bbs (last_added_blocks, NULL);
5020 /* When bb is passed explicitly, the vector should contain
5021 the only element that equals to bb; otherwise, the vector
5022 should not be NULL. */
5023 gcc_assert (last_added_blocks != NULL);
5027 gcc_assert (VEC_length (basic_block, last_added_blocks) == 1
5028 && VEC_index (basic_block,
5029 last_added_blocks, 0) == bb);
5030 add_block_to_current_region (bb);
5032 /* We associate creating/deleting data sets with the first insn
5033 appearing / disappearing in the bb. */
5034 if (!sel_bb_empty_p (bb) && BB_LV_SET (bb) == NULL)
5035 create_initial_data_sets (bb);
5037 VEC_free (basic_block, heap, last_added_blocks);
5040 /* BB is NULL - process LAST_ADDED_BLOCKS instead. */
5043 basic_block temp_bb = NULL;
5046 VEC_iterate (basic_block, last_added_blocks, i, bb); i++)
5048 add_block_to_current_region (bb);
5052 /* We need to fetch at least one bb so we know the region
5054 gcc_assert (temp_bb != NULL);
5057 VEC_free (basic_block, heap, last_added_blocks);
5060 rgn_setup_region (CONTAINING_RGN (bb->index));
5063 /* Remove BB from the current region and update all data.
5064 If REMOVE_FROM_CFG_PBB is true, also remove the block cfom cfg. */
5066 sel_remove_bb (basic_block bb, bool remove_from_cfg_p)
5068 unsigned idx = bb->index;
5070 gcc_assert (bb != NULL && BB_NOTE_LIST (bb) == NULL_RTX);
5072 remove_bb_from_region (bb);
5073 return_bb_to_pool (bb);
5074 bitmap_clear_bit (blocks_to_reschedule, idx);
5076 if (remove_from_cfg_p)
5077 delete_and_free_basic_block (bb);
5079 rgn_setup_region (CONTAINING_RGN (idx));
5082 /* Concatenate info of EMPTY_BB to info of MERGE_BB. */
5084 move_bb_info (basic_block merge_bb, basic_block empty_bb)
5086 gcc_assert (in_current_region_p (merge_bb));
5088 concat_note_lists (BB_NOTE_LIST (empty_bb),
5089 &BB_NOTE_LIST (merge_bb));
5090 BB_NOTE_LIST (empty_bb) = NULL_RTX;
5094 /* Remove EMPTY_BB. If REMOVE_FROM_CFG_P is false, remove EMPTY_BB from
5095 region, but keep it in CFG. */
5097 remove_empty_bb (basic_block empty_bb, bool remove_from_cfg_p)
5099 /* The block should contain just a note or a label.
5100 We try to check whether it is unused below. */
5101 gcc_assert (BB_HEAD (empty_bb) == BB_END (empty_bb)
5102 || LABEL_P (BB_HEAD (empty_bb)));
5104 /* If basic block has predecessors or successors, redirect them. */
5105 if (remove_from_cfg_p
5106 && (EDGE_COUNT (empty_bb->preds) > 0
5107 || EDGE_COUNT (empty_bb->succs) > 0))
5112 /* We need to init PRED and SUCC before redirecting edges. */
5113 if (EDGE_COUNT (empty_bb->preds) > 0)
5117 gcc_assert (EDGE_COUNT (empty_bb->preds) == 1);
5119 e = EDGE_PRED (empty_bb, 0);
5120 gcc_assert (e->src == empty_bb->prev_bb
5121 && (e->flags & EDGE_FALLTHRU));
5123 pred = empty_bb->prev_bb;
5128 if (EDGE_COUNT (empty_bb->succs) > 0)
5130 /* We do not check fallthruness here as above, because
5131 after removing a jump the edge may actually be not fallthru. */
5132 gcc_assert (EDGE_COUNT (empty_bb->succs) == 1);
5133 succ = EDGE_SUCC (empty_bb, 0)->dest;
5138 if (EDGE_COUNT (empty_bb->preds) > 0 && succ != NULL)
5140 edge e = EDGE_PRED (empty_bb, 0);
5142 if (e->flags & EDGE_FALLTHRU)
5143 redirect_edge_succ_nodup (e, succ);
5145 sel_redirect_edge_and_branch (EDGE_PRED (empty_bb, 0), succ);
5148 if (EDGE_COUNT (empty_bb->succs) > 0 && pred != NULL)
5150 edge e = EDGE_SUCC (empty_bb, 0);
5152 if (find_edge (pred, e->dest) == NULL)
5153 redirect_edge_pred (e, pred);
5157 /* Finish removing. */
5158 sel_remove_bb (empty_bb, remove_from_cfg_p);
5161 /* An implementation of create_basic_block hook, which additionally updates
5162 per-bb data structures. */
5164 sel_create_basic_block (void *headp, void *endp, basic_block after)
5169 gcc_assert (flag_sel_sched_pipelining_outer_loops
5170 || last_added_blocks == NULL);
5172 new_bb_note = get_bb_note_from_pool ();
5174 if (new_bb_note == NULL_RTX)
5175 new_bb = orig_cfg_hooks.create_basic_block (headp, endp, after);
5178 new_bb = create_basic_block_structure ((rtx) headp, (rtx) endp,
5179 new_bb_note, after);
5183 VEC_safe_push (basic_block, heap, last_added_blocks, new_bb);
5188 /* Implement sched_init_only_bb (). */
5190 sel_init_only_bb (basic_block bb, basic_block after)
5192 gcc_assert (after == NULL);
5195 rgn_make_new_region_out_of_new_block (bb);
5198 /* Update the latch when we've splitted or merged it from FROM block to TO.
5199 This should be checked for all outer loops, too. */
5201 change_loops_latches (basic_block from, basic_block to)
5203 gcc_assert (from != to);
5205 if (current_loop_nest)
5209 for (loop = current_loop_nest; loop; loop = loop_outer (loop))
5210 if (considered_for_pipelining_p (loop) && loop->latch == from)
5212 gcc_assert (loop == current_loop_nest);
5214 gcc_assert (loop_latch_edge (loop));
5219 /* Splits BB on two basic blocks, adding it to the region and extending
5220 per-bb data structures. Returns the newly created bb. */
5222 sel_split_block (basic_block bb, rtx after)
5227 new_bb = sched_split_block_1 (bb, after);
5228 sel_add_bb (new_bb);
5230 /* This should be called after sel_add_bb, because this uses
5231 CONTAINING_RGN for the new block, which is not yet initialized.
5232 FIXME: this function may be a no-op now. */
5233 change_loops_latches (bb, new_bb);
5235 /* Update ORIG_BB_INDEX for insns moved into the new block. */
5236 FOR_BB_INSNS (new_bb, insn)
5238 EXPR_ORIG_BB_INDEX (INSN_EXPR (insn)) = new_bb->index;
5240 if (sel_bb_empty_p (bb))
5242 gcc_assert (!sel_bb_empty_p (new_bb));
5244 /* NEW_BB has data sets that need to be updated and BB holds
5245 data sets that should be removed. Exchange these data sets
5246 so that we won't lose BB's valid data sets. */
5247 exchange_data_sets (new_bb, bb);
5248 free_data_sets (bb);
5251 if (!sel_bb_empty_p (new_bb)
5252 && bitmap_bit_p (blocks_to_reschedule, bb->index))
5253 bitmap_set_bit (blocks_to_reschedule, new_bb->index);
5258 /* If BB ends with a jump insn whose ID is bigger then PREV_MAX_UID, return it.
5259 Otherwise returns NULL. */
5261 check_for_new_jump (basic_block bb, int prev_max_uid)
5265 end = sel_bb_end (bb);
5266 if (end && INSN_UID (end) >= prev_max_uid)
5271 /* Look for a new jump either in FROM_BB block or in newly created JUMP_BB block.
5272 New means having UID at least equal to PREV_MAX_UID. */
5274 find_new_jump (basic_block from, basic_block jump_bb, int prev_max_uid)
5278 /* Return immediately if no new insns were emitted. */
5279 if (get_max_uid () == prev_max_uid)
5282 /* Now check both blocks for new jumps. It will ever be only one. */
5283 if ((jump = check_for_new_jump (from, prev_max_uid)))
5287 && (jump = check_for_new_jump (jump_bb, prev_max_uid)))
5292 /* Splits E and adds the newly created basic block to the current region.
5293 Returns this basic block. */
5295 sel_split_edge (edge e)
5297 basic_block new_bb, src, other_bb = NULL;
5302 prev_max_uid = get_max_uid ();
5303 new_bb = split_edge (e);
5305 if (flag_sel_sched_pipelining_outer_loops
5306 && current_loop_nest)
5311 /* Some of the basic blocks might not have been added to the loop.
5312 Add them here, until this is fixed in force_fallthru. */
5314 VEC_iterate (basic_block, last_added_blocks, i, bb); i++)
5315 if (!bb->loop_father)
5317 add_bb_to_loop (bb, e->dest->loop_father);
5319 gcc_assert (!other_bb && (new_bb->index != bb->index));
5324 /* Add all last_added_blocks to the region. */
5327 jump = find_new_jump (src, new_bb, prev_max_uid);
5329 sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP);
5331 /* Put the correct lv set on this block. */
5332 if (other_bb && !sel_bb_empty_p (other_bb))
5333 compute_live (sel_bb_head (other_bb));
5338 /* Implement sched_create_empty_bb (). */
5340 sel_create_empty_bb (basic_block after)
5344 new_bb = sched_create_empty_bb_1 (after);
5346 /* We'll explicitly initialize NEW_BB via sel_init_only_bb () a bit
5348 gcc_assert (VEC_length (basic_block, last_added_blocks) == 1
5349 && VEC_index (basic_block, last_added_blocks, 0) == new_bb);
5351 VEC_free (basic_block, heap, last_added_blocks);
5355 /* Implement sched_create_recovery_block. ORIG_INSN is where block
5356 will be splitted to insert a check. */
5358 sel_create_recovery_block (insn_t orig_insn)
5360 basic_block first_bb, second_bb, recovery_block;
5361 basic_block before_recovery = NULL;
5364 first_bb = BLOCK_FOR_INSN (orig_insn);
5365 if (sel_bb_end_p (orig_insn))
5367 /* Avoid introducing an empty block while splitting. */
5368 gcc_assert (single_succ_p (first_bb));
5369 second_bb = single_succ (first_bb);
5372 second_bb = sched_split_block (first_bb, orig_insn);
5374 recovery_block = sched_create_recovery_block (&before_recovery);
5375 if (before_recovery)
5376 copy_lv_set_from (before_recovery, EXIT_BLOCK_PTR);
5378 gcc_assert (sel_bb_empty_p (recovery_block));
5379 sched_create_recovery_edges (first_bb, recovery_block, second_bb);
5380 if (current_loops != NULL)
5381 add_bb_to_loop (recovery_block, first_bb->loop_father);
5383 sel_add_bb (recovery_block);
5385 jump = BB_END (recovery_block);
5386 gcc_assert (sel_bb_head (recovery_block) == jump);
5387 sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP);
5389 return recovery_block;
5392 /* Merge basic block B into basic block A. */
5394 sel_merge_blocks (basic_block a, basic_block b)
5396 gcc_assert (sel_bb_empty_p (b)
5397 && EDGE_COUNT (b->preds) == 1
5398 && EDGE_PRED (b, 0)->src == b->prev_bb);
5400 move_bb_info (b->prev_bb, b);
5401 remove_empty_bb (b, false);
5402 merge_blocks (a, b);
5403 change_loops_latches (b, a);
5406 /* A wrapper for redirect_edge_and_branch_force, which also initializes
5407 data structures for possibly created bb and insns. Returns the newly
5408 added bb or NULL, when a bb was not needed. */
5410 sel_redirect_edge_and_branch_force (edge e, basic_block to)
5412 basic_block jump_bb, src;
5416 gcc_assert (!sel_bb_empty_p (e->src));
5419 prev_max_uid = get_max_uid ();
5420 jump_bb = redirect_edge_and_branch_force (e, to);
5422 if (jump_bb != NULL)
5423 sel_add_bb (jump_bb);
5425 /* This function could not be used to spoil the loop structure by now,
5426 thus we don't care to update anything. But check it to be sure. */
5427 if (current_loop_nest
5429 gcc_assert (loop_latch_edge (current_loop_nest));
5431 jump = find_new_jump (src, jump_bb, prev_max_uid);
5433 sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP);
5436 /* A wrapper for redirect_edge_and_branch. Return TRUE if blocks connected by
5437 redirected edge are in reverse topological order. */
5439 sel_redirect_edge_and_branch (edge e, basic_block to)
5446 bool recompute_toporder_p = false;
5448 latch_edge_p = (pipelining_p
5449 && current_loop_nest
5450 && e == loop_latch_edge (current_loop_nest));
5453 prev_max_uid = get_max_uid ();
5455 redirected = redirect_edge_and_branch (e, to);
5457 gcc_assert (redirected && last_added_blocks == NULL);
5459 /* When we've redirected a latch edge, update the header. */
5462 current_loop_nest->header = to;
5463 gcc_assert (loop_latch_edge (current_loop_nest));
5466 /* In rare situations, the topological relation between the blocks connected
5467 by the redirected edge can change (see PR42245 for an example). Update
5468 block_to_bb/bb_to_block. */
5469 if (CONTAINING_RGN (e->src->index) == CONTAINING_RGN (to->index)
5470 && BLOCK_TO_BB (e->src->index) > BLOCK_TO_BB (to->index))
5471 recompute_toporder_p = true;
5473 jump = find_new_jump (src, NULL, prev_max_uid);
5475 sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP);
5477 return recompute_toporder_p;
5480 /* This variable holds the cfg hooks used by the selective scheduler. */
5481 static struct cfg_hooks sel_cfg_hooks;
5483 /* Register sel-sched cfg hooks. */
5485 sel_register_cfg_hooks (void)
5487 sched_split_block = sel_split_block;
5489 orig_cfg_hooks = get_cfg_hooks ();
5490 sel_cfg_hooks = orig_cfg_hooks;
5492 sel_cfg_hooks.create_basic_block = sel_create_basic_block;
5494 set_cfg_hooks (sel_cfg_hooks);
5496 sched_init_only_bb = sel_init_only_bb;
5497 sched_split_block = sel_split_block;
5498 sched_create_empty_bb = sel_create_empty_bb;
5501 /* Unregister sel-sched cfg hooks. */
5503 sel_unregister_cfg_hooks (void)
5505 sched_create_empty_bb = NULL;
5506 sched_split_block = NULL;
5507 sched_init_only_bb = NULL;
5509 set_cfg_hooks (orig_cfg_hooks);
5513 /* Emit an insn rtx based on PATTERN. If a jump insn is wanted,
5514 LABEL is where this jump should be directed. */
5516 create_insn_rtx_from_pattern (rtx pattern, rtx label)
5520 gcc_assert (!INSN_P (pattern));
5524 if (label == NULL_RTX)
5525 insn_rtx = emit_insn (pattern);
5526 else if (DEBUG_INSN_P (label))
5527 insn_rtx = emit_debug_insn (pattern);
5530 insn_rtx = emit_jump_insn (pattern);
5531 JUMP_LABEL (insn_rtx) = label;
5532 ++LABEL_NUSES (label);
5537 sched_init_luids (NULL, NULL, NULL, NULL);
5538 sched_extend_target ();
5539 sched_deps_init (false);
5541 /* Initialize INSN_CODE now. */
5542 recog_memoized (insn_rtx);
5546 /* Create a new vinsn for INSN_RTX. FORCE_UNIQUE_P is true when the vinsn
5547 must not be clonable. */
5549 create_vinsn_from_insn_rtx (rtx insn_rtx, bool force_unique_p)
5551 gcc_assert (INSN_P (insn_rtx) && !INSN_IN_STREAM_P (insn_rtx));
5553 /* If VINSN_TYPE is not USE, retain its uniqueness. */
5554 return vinsn_create (insn_rtx, force_unique_p);
5557 /* Create a copy of INSN_RTX. */
5559 create_copy_of_insn_rtx (rtx insn_rtx)
5563 if (DEBUG_INSN_P (insn_rtx))
5564 return create_insn_rtx_from_pattern (copy_rtx (PATTERN (insn_rtx)),
5567 gcc_assert (NONJUMP_INSN_P (insn_rtx));
5569 res = create_insn_rtx_from_pattern (copy_rtx (PATTERN (insn_rtx)),
5574 /* Change vinsn field of EXPR to hold NEW_VINSN. */
5576 change_vinsn_in_expr (expr_t expr, vinsn_t new_vinsn)
5578 vinsn_detach (EXPR_VINSN (expr));
5580 EXPR_VINSN (expr) = new_vinsn;
5581 vinsn_attach (new_vinsn);
5584 /* Helpers for global init. */
5585 /* This structure is used to be able to call existing bundling mechanism
5586 and calculate insn priorities. */
5587 static struct haifa_sched_info sched_sel_haifa_sched_info =
5589 NULL, /* init_ready_list */
5590 NULL, /* can_schedule_ready_p */
5591 NULL, /* schedule_more_p */
5592 NULL, /* new_ready */
5593 NULL, /* rgn_rank */
5594 sel_print_insn, /* rgn_print_insn */
5595 contributes_to_priority,
5596 NULL, /* insn_finishes_block_p */
5602 NULL, /* add_remove_insn */
5603 NULL, /* begin_schedule_ready */
5604 NULL, /* advance_target_bb */
5608 /* Setup special insns used in the scheduler. */
5610 setup_nop_and_exit_insns (void)
5612 gcc_assert (nop_pattern == NULL_RTX
5613 && exit_insn == NULL_RTX);
5615 nop_pattern = constm1_rtx;
5618 emit_insn (nop_pattern);
5619 exit_insn = get_insns ();
5621 set_block_for_insn (exit_insn, EXIT_BLOCK_PTR);
5624 /* Free special insns used in the scheduler. */
5626 free_nop_and_exit_insns (void)
5628 exit_insn = NULL_RTX;
5629 nop_pattern = NULL_RTX;
5632 /* Setup a special vinsn used in new insns initialization. */
5634 setup_nop_vinsn (void)
5636 nop_vinsn = vinsn_create (exit_insn, false);
5637 vinsn_attach (nop_vinsn);
5640 /* Free a special vinsn used in new insns initialization. */
5642 free_nop_vinsn (void)
5644 gcc_assert (VINSN_COUNT (nop_vinsn) == 1);
5645 vinsn_detach (nop_vinsn);
5649 /* Call a set_sched_flags hook. */
5651 sel_set_sched_flags (void)
5653 /* ??? This means that set_sched_flags were called, and we decided to
5654 support speculation. However, set_sched_flags also modifies flags
5655 on current_sched_info, doing this only at global init. And we
5656 sometimes change c_s_i later. So put the correct flags again. */
5657 if (spec_info && targetm.sched.set_sched_flags)
5658 targetm.sched.set_sched_flags (spec_info);
5661 /* Setup pointers to global sched info structures. */
5663 sel_setup_sched_infos (void)
5665 rgn_setup_common_sched_info ();
5667 memcpy (&sel_common_sched_info, common_sched_info,
5668 sizeof (sel_common_sched_info));
5670 sel_common_sched_info.fix_recovery_cfg = NULL;
5671 sel_common_sched_info.add_block = NULL;
5672 sel_common_sched_info.estimate_number_of_insns
5673 = sel_estimate_number_of_insns;
5674 sel_common_sched_info.luid_for_non_insn = sel_luid_for_non_insn;
5675 sel_common_sched_info.sched_pass_id = SCHED_SEL_PASS;
5677 common_sched_info = &sel_common_sched_info;
5679 current_sched_info = &sched_sel_haifa_sched_info;
5680 current_sched_info->sched_max_insns_priority =
5681 get_rgn_sched_max_insns_priority ();
5683 sel_set_sched_flags ();
5687 /* Adds basic block BB to region RGN at the position *BB_ORD_INDEX,
5688 *BB_ORD_INDEX after that is increased. */
5690 sel_add_block_to_region (basic_block bb, int *bb_ord_index, int rgn)
5692 RGN_NR_BLOCKS (rgn) += 1;
5693 RGN_DONT_CALC_DEPS (rgn) = 0;
5694 RGN_HAS_REAL_EBB (rgn) = 0;
5695 CONTAINING_RGN (bb->index) = rgn;
5696 BLOCK_TO_BB (bb->index) = *bb_ord_index;
5697 rgn_bb_table[RGN_BLOCKS (rgn) + *bb_ord_index] = bb->index;
5700 /* FIXME: it is true only when not scheduling ebbs. */
5701 RGN_BLOCKS (rgn + 1) = RGN_BLOCKS (rgn) + RGN_NR_BLOCKS (rgn);
5704 /* Functions to support pipelining of outer loops. */
5706 /* Creates a new empty region and returns it's number. */
5708 sel_create_new_region (void)
5710 int new_rgn_number = nr_regions;
5712 RGN_NR_BLOCKS (new_rgn_number) = 0;
5714 /* FIXME: This will work only when EBBs are not created. */
5715 if (new_rgn_number != 0)
5716 RGN_BLOCKS (new_rgn_number) = RGN_BLOCKS (new_rgn_number - 1) +
5717 RGN_NR_BLOCKS (new_rgn_number - 1);
5719 RGN_BLOCKS (new_rgn_number) = 0;
5721 /* Set the blocks of the next region so the other functions may
5722 calculate the number of blocks in the region. */
5723 RGN_BLOCKS (new_rgn_number + 1) = RGN_BLOCKS (new_rgn_number) +
5724 RGN_NR_BLOCKS (new_rgn_number);
5728 return new_rgn_number;
5731 /* If X has a smaller topological sort number than Y, returns -1;
5732 if greater, returns 1. */
5734 bb_top_order_comparator (const void *x, const void *y)
5736 basic_block bb1 = *(const basic_block *) x;
5737 basic_block bb2 = *(const basic_block *) y;
5739 gcc_assert (bb1 == bb2
5740 || rev_top_order_index[bb1->index]
5741 != rev_top_order_index[bb2->index]);
5743 /* It's a reverse topological order in REV_TOP_ORDER_INDEX, so
5744 bbs with greater number should go earlier. */
5745 if (rev_top_order_index[bb1->index] > rev_top_order_index[bb2->index])
5751 /* Create a region for LOOP and return its number. If we don't want
5752 to pipeline LOOP, return -1. */
5754 make_region_from_loop (struct loop *loop)
5757 int new_rgn_number = -1;
5760 /* Basic block index, to be assigned to BLOCK_TO_BB. */
5761 int bb_ord_index = 0;
5762 basic_block *loop_blocks;
5763 basic_block preheader_block;
5766 > (unsigned) PARAM_VALUE (PARAM_MAX_PIPELINE_REGION_BLOCKS))
5769 /* Don't pipeline loops whose latch belongs to some of its inner loops. */
5770 for (inner = loop->inner; inner; inner = inner->inner)
5771 if (flow_bb_inside_loop_p (inner, loop->latch))
5774 loop->ninsns = num_loop_insns (loop);
5775 if ((int) loop->ninsns > PARAM_VALUE (PARAM_MAX_PIPELINE_REGION_INSNS))
5778 loop_blocks = get_loop_body_in_custom_order (loop, bb_top_order_comparator);
5780 for (i = 0; i < loop->num_nodes; i++)
5781 if (loop_blocks[i]->flags & BB_IRREDUCIBLE_LOOP)
5787 preheader_block = loop_preheader_edge (loop)->src;
5788 gcc_assert (preheader_block);
5789 gcc_assert (loop_blocks[0] == loop->header);
5791 new_rgn_number = sel_create_new_region ();
5793 sel_add_block_to_region (preheader_block, &bb_ord_index, new_rgn_number);
5794 SET_BIT (bbs_in_loop_rgns, preheader_block->index);
5796 for (i = 0; i < loop->num_nodes; i++)
5798 /* Add only those blocks that haven't been scheduled in the inner loop.
5799 The exception is the basic blocks with bookkeeping code - they should
5800 be added to the region (and they actually don't belong to the loop
5801 body, but to the region containing that loop body). */
5803 gcc_assert (new_rgn_number >= 0);
5805 if (! TEST_BIT (bbs_in_loop_rgns, loop_blocks[i]->index))
5807 sel_add_block_to_region (loop_blocks[i], &bb_ord_index,
5809 SET_BIT (bbs_in_loop_rgns, loop_blocks[i]->index);
5814 MARK_LOOP_FOR_PIPELINING (loop);
5816 return new_rgn_number;
5819 /* Create a new region from preheader blocks LOOP_BLOCKS. */
5821 make_region_from_loop_preheader (VEC(basic_block, heap) **loop_blocks)
5824 int new_rgn_number = -1;
5827 /* Basic block index, to be assigned to BLOCK_TO_BB. */
5828 int bb_ord_index = 0;
5830 new_rgn_number = sel_create_new_region ();
5832 FOR_EACH_VEC_ELT (basic_block, *loop_blocks, i, bb)
5834 gcc_assert (new_rgn_number >= 0);
5836 sel_add_block_to_region (bb, &bb_ord_index, new_rgn_number);
5839 VEC_free (basic_block, heap, *loop_blocks);
5840 gcc_assert (*loop_blocks == NULL);
5844 /* Create region(s) from loop nest LOOP, such that inner loops will be
5845 pipelined before outer loops. Returns true when a region for LOOP
5848 make_regions_from_loop_nest (struct loop *loop)
5850 struct loop *cur_loop;
5853 /* Traverse all inner nodes of the loop. */
5854 for (cur_loop = loop->inner; cur_loop; cur_loop = cur_loop->next)
5855 if (! TEST_BIT (bbs_in_loop_rgns, cur_loop->header->index))
5858 /* At this moment all regular inner loops should have been pipelined.
5859 Try to create a region from this loop. */
5860 rgn_number = make_region_from_loop (loop);
5865 VEC_safe_push (loop_p, heap, loop_nests, loop);
5869 /* Initalize data structures needed. */
5871 sel_init_pipelining (void)
5873 /* Collect loop information to be used in outer loops pipelining. */
5874 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
5875 | LOOPS_HAVE_FALLTHRU_PREHEADERS
5876 | LOOPS_HAVE_RECORDED_EXITS
5877 | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS);
5878 current_loop_nest = NULL;
5880 bbs_in_loop_rgns = sbitmap_alloc (last_basic_block);
5881 sbitmap_zero (bbs_in_loop_rgns);
5883 recompute_rev_top_order ();
5886 /* Returns a struct loop for region RGN. */
5888 get_loop_nest_for_rgn (unsigned int rgn)
5890 /* Regions created with extend_rgns don't have corresponding loop nests,
5891 because they don't represent loops. */
5892 if (rgn < VEC_length (loop_p, loop_nests))
5893 return VEC_index (loop_p, loop_nests, rgn);
5898 /* True when LOOP was included into pipelining regions. */
5900 considered_for_pipelining_p (struct loop *loop)
5902 if (loop_depth (loop) == 0)
5905 /* Now, the loop could be too large or irreducible. Check whether its
5906 region is in LOOP_NESTS.
5907 We determine the region number of LOOP as the region number of its
5908 latch. We can't use header here, because this header could be
5909 just removed preheader and it will give us the wrong region number.
5910 Latch can't be used because it could be in the inner loop too. */
5911 if (LOOP_MARKED_FOR_PIPELINING_P (loop))
5913 int rgn = CONTAINING_RGN (loop->latch->index);
5915 gcc_assert ((unsigned) rgn < VEC_length (loop_p, loop_nests));
5922 /* Makes regions from the rest of the blocks, after loops are chosen
5925 make_regions_from_the_rest (void)
5936 /* Index in rgn_bb_table where to start allocating new regions. */
5937 cur_rgn_blocks = nr_regions ? RGN_BLOCKS (nr_regions) : 0;
5939 /* Make regions from all the rest basic blocks - those that don't belong to
5940 any loop or belong to irreducible loops. Prepare the data structures
5943 /* LOOP_HDR[I] == -1 if I-th bb doesn't belong to any loop,
5944 LOOP_HDR[I] == LOOP_HDR[J] iff basic blocks I and J reside within the same
5946 loop_hdr = XNEWVEC (int, last_basic_block);
5947 degree = XCNEWVEC (int, last_basic_block);
5950 /* For each basic block that belongs to some loop assign the number
5951 of innermost loop it belongs to. */
5952 for (i = 0; i < last_basic_block; i++)
5957 if (bb->loop_father && !bb->loop_father->num == 0
5958 && !(bb->flags & BB_IRREDUCIBLE_LOOP))
5959 loop_hdr[bb->index] = bb->loop_father->num;
5962 /* For each basic block degree is calculated as the number of incoming
5963 edges, that are going out of bbs that are not yet scheduled.
5964 The basic blocks that are scheduled have degree value of zero. */
5967 degree[bb->index] = 0;
5969 if (!TEST_BIT (bbs_in_loop_rgns, bb->index))
5971 FOR_EACH_EDGE (e, ei, bb->preds)
5972 if (!TEST_BIT (bbs_in_loop_rgns, e->src->index))
5973 degree[bb->index]++;
5976 degree[bb->index] = -1;
5979 extend_rgns (degree, &cur_rgn_blocks, bbs_in_loop_rgns, loop_hdr);
5981 /* Any block that did not end up in a region is placed into a region
5984 if (degree[bb->index] >= 0)
5986 rgn_bb_table[cur_rgn_blocks] = bb->index;
5987 RGN_NR_BLOCKS (nr_regions) = 1;
5988 RGN_BLOCKS (nr_regions) = cur_rgn_blocks++;
5989 RGN_DONT_CALC_DEPS (nr_regions) = 0;
5990 RGN_HAS_REAL_EBB (nr_regions) = 0;
5991 CONTAINING_RGN (bb->index) = nr_regions++;
5992 BLOCK_TO_BB (bb->index) = 0;
5999 /* Free data structures used in pipelining of loops. */
6000 void sel_finish_pipelining (void)
6005 /* Release aux fields so we don't free them later by mistake. */
6006 FOR_EACH_LOOP (li, loop, 0)
6009 loop_optimizer_finalize ();
6011 VEC_free (loop_p, heap, loop_nests);
6013 free (rev_top_order_index);
6014 rev_top_order_index = NULL;
6017 /* This function replaces the find_rgns when
6018 FLAG_SEL_SCHED_PIPELINING_OUTER_LOOPS is set. */
6020 sel_find_rgns (void)
6022 sel_init_pipelining ();
6030 FOR_EACH_LOOP (li, loop, (flag_sel_sched_pipelining_outer_loops
6032 : LI_ONLY_INNERMOST))
6033 make_regions_from_loop_nest (loop);
6036 /* Make regions from all the rest basic blocks and schedule them.
6037 These blocks include blocks that don't belong to any loop or belong
6038 to irreducible loops. */
6039 make_regions_from_the_rest ();
6041 /* We don't need bbs_in_loop_rgns anymore. */
6042 sbitmap_free (bbs_in_loop_rgns);
6043 bbs_in_loop_rgns = NULL;
6046 /* Adds the preheader blocks from previous loop to current region taking
6047 it from LOOP_PREHEADER_BLOCKS (current_loop_nest).
6048 This function is only used with -fsel-sched-pipelining-outer-loops. */
6050 sel_add_loop_preheaders (void)
6054 VEC(basic_block, heap) *preheader_blocks
6055 = LOOP_PREHEADER_BLOCKS (current_loop_nest);
6058 VEC_iterate (basic_block, preheader_blocks, i, bb);
6061 VEC_safe_push (basic_block, heap, last_added_blocks, bb);
6065 VEC_free (basic_block, heap, preheader_blocks);
6068 /* While pipelining outer loops, returns TRUE if BB is a loop preheader.
6069 Please note that the function should also work when pipelining_p is
6070 false, because it is used when deciding whether we should or should
6071 not reschedule pipelined code. */
6073 sel_is_loop_preheader_p (basic_block bb)
6075 if (current_loop_nest)
6079 if (preheader_removed)
6082 /* Preheader is the first block in the region. */
6083 if (BLOCK_TO_BB (bb->index) == 0)
6086 /* We used to find a preheader with the topological information.
6087 Check that the above code is equivalent to what we did before. */
6089 if (in_current_region_p (current_loop_nest->header))
6090 gcc_assert (!(BLOCK_TO_BB (bb->index)
6091 < BLOCK_TO_BB (current_loop_nest->header->index)));
6093 /* Support the situation when the latch block of outer loop
6094 could be from here. */
6095 for (outer = loop_outer (current_loop_nest);
6097 outer = loop_outer (outer))
6098 if (considered_for_pipelining_p (outer) && outer->latch == bb)
6105 /* Checks whether JUMP leads to basic block DEST_BB and no other blocks. */
6107 jump_leads_only_to_bb_p (insn_t jump, basic_block dest_bb)
6109 basic_block jump_bb = BLOCK_FOR_INSN (jump);
6111 /* It is not jump, jump with side-effects or jump can lead to several
6113 if (!onlyjump_p (jump)
6114 || !any_uncondjump_p (jump))
6117 /* Several outgoing edges, abnormal edge or destination of jump is
6119 if (EDGE_COUNT (jump_bb->succs) != 1
6120 || EDGE_SUCC (jump_bb, 0)->flags & EDGE_ABNORMAL
6121 || EDGE_SUCC (jump_bb, 0)->dest != dest_bb)
6124 /* If not anything of the upper. */
6128 /* Removes the loop preheader from the current region and saves it in
6129 PREHEADER_BLOCKS of the father loop, so they will be added later to
6130 region that represents an outer loop. */
6132 sel_remove_loop_preheader (void)
6135 int cur_rgn = CONTAINING_RGN (BB_TO_BLOCK (0));
6137 bool all_empty_p = true;
6138 VEC(basic_block, heap) *preheader_blocks
6139 = LOOP_PREHEADER_BLOCKS (loop_outer (current_loop_nest));
6141 gcc_assert (current_loop_nest);
6142 old_len = VEC_length (basic_block, preheader_blocks);
6144 /* Add blocks that aren't within the current loop to PREHEADER_BLOCKS. */
6145 for (i = 0; i < RGN_NR_BLOCKS (cur_rgn); i++)
6147 bb = BASIC_BLOCK (BB_TO_BLOCK (i));
6149 /* If the basic block belongs to region, but doesn't belong to
6150 corresponding loop, then it should be a preheader. */
6151 if (sel_is_loop_preheader_p (bb))
6153 VEC_safe_push (basic_block, heap, preheader_blocks, bb);
6154 if (BB_END (bb) != bb_note (bb))
6155 all_empty_p = false;
6159 /* Remove these blocks only after iterating over the whole region. */
6160 for (i = VEC_length (basic_block, preheader_blocks) - 1;
6164 bb = VEC_index (basic_block, preheader_blocks, i);
6165 sel_remove_bb (bb, false);
6168 if (!considered_for_pipelining_p (loop_outer (current_loop_nest)))
6171 /* Immediately create new region from preheader. */
6172 make_region_from_loop_preheader (&preheader_blocks);
6175 /* If all preheader blocks are empty - dont create new empty region.
6176 Instead, remove them completely. */
6177 FOR_EACH_VEC_ELT (basic_block, preheader_blocks, i, bb)
6181 basic_block prev_bb = bb->prev_bb, next_bb = bb->next_bb;
6183 /* Redirect all incoming edges to next basic block. */
6184 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
6186 if (! (e->flags & EDGE_FALLTHRU))
6187 redirect_edge_and_branch (e, bb->next_bb);
6189 redirect_edge_succ (e, bb->next_bb);
6191 gcc_assert (BB_NOTE_LIST (bb) == NULL);
6192 delete_and_free_basic_block (bb);
6194 /* Check if after deleting preheader there is a nonconditional
6195 jump in PREV_BB that leads to the next basic block NEXT_BB.
6196 If it is so - delete this jump and clear data sets of its
6197 basic block if it becomes empty. */
6198 if (next_bb->prev_bb == prev_bb
6199 && prev_bb != ENTRY_BLOCK_PTR
6200 && jump_leads_only_to_bb_p (BB_END (prev_bb), next_bb))
6202 redirect_edge_and_branch (EDGE_SUCC (prev_bb, 0), next_bb);
6203 if (BB_END (prev_bb) == bb_note (prev_bb))
6204 free_data_sets (prev_bb);
6208 VEC_free (basic_block, heap, preheader_blocks);
6211 /* Store preheader within the father's loop structure. */
6212 SET_LOOP_PREHEADER_BLOCKS (loop_outer (current_loop_nest),