1 /* Instruction scheduling pass. Selective scheduler and pipeliner.
2 Copyright (C) 2006, 2007, 2008 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
27 #include "hard-reg-set.h"
31 #include "insn-config.h"
32 #include "insn-attr.h"
39 #include "tree-pass.h"
40 #include "sched-int.h"
44 #include "langhooks.h"
45 #include "rtlhooks-def.h"
47 #ifdef INSN_SCHEDULING
48 #include "sel-sched-ir.h"
49 /* We don't have to use it except for sel_print_insn. */
50 #include "sel-sched-dump.h"
52 /* A vector holding bb info for whole scheduling pass. */
53 VEC(sel_global_bb_info_def, heap) *sel_global_bb_info = NULL;
55 /* A vector holding bb info. */
56 VEC(sel_region_bb_info_def, heap) *sel_region_bb_info = NULL;
58 /* A pool for allocating all lists. */
59 alloc_pool sched_lists_pool;
61 /* This contains information about successors for compute_av_set. */
62 struct succs_info current_succs;
64 /* Data structure to describe interaction with the generic scheduler utils. */
65 static struct common_sched_info_def sel_common_sched_info;
67 /* The loop nest being pipelined. */
68 struct loop *current_loop_nest;
70 /* LOOP_NESTS is a vector containing the corresponding loop nest for
72 static VEC(loop_p, heap) *loop_nests = NULL;
74 /* Saves blocks already in loop regions, indexed by bb->index. */
75 static sbitmap bbs_in_loop_rgns = NULL;
77 /* CFG hooks that are saved before changing create_basic_block hook. */
78 static struct cfg_hooks orig_cfg_hooks;
81 /* Array containing reverse topological index of function basic blocks,
82 indexed by BB->INDEX. */
83 static int *rev_top_order_index = NULL;
85 /* Length of the above array. */
86 static int rev_top_order_index_len = -1;
88 /* A regset pool structure. */
91 /* The stack to which regsets are returned. */
100 /* In VV we save all generated regsets so that, when destructing the
101 pool, we can compare it with V and check that every regset was returned
105 /* The pointer of VV stack. */
111 /* The difference between allocated and returned regsets. */
113 } regset_pool = { NULL, 0, 0, NULL, 0, 0, 0 };
115 /* This represents the nop pool. */
118 /* The vector which holds previously emitted nops. */
126 } nop_pool = { NULL, 0, 0 };
128 /* The pool for basic block notes. */
129 static rtx_vec_t bb_note_pool;
131 /* A NOP pattern used to emit placeholder insns. */
132 rtx nop_pattern = NULL_RTX;
133 /* A special instruction that resides in EXIT_BLOCK.
134 EXIT_INSN is successor of the insns that lead to EXIT_BLOCK. */
135 rtx exit_insn = NULL_RTX;
137 /* TRUE if while scheduling current region, which is loop, its preheader
139 bool preheader_removed = false;
142 /* Forward static declarations. */
143 static void fence_clear (fence_t);
145 static void deps_init_id (idata_t, insn_t, bool);
146 static void init_id_from_df (idata_t, insn_t, bool);
147 static expr_t set_insn_init (expr_t, vinsn_t, int);
149 static void cfg_preds (basic_block, insn_t **, int *);
150 static void prepare_insn_expr (insn_t, int);
151 static void free_history_vect (VEC (expr_history_def, heap) **);
153 static void move_bb_info (basic_block, basic_block);
154 static void remove_empty_bb (basic_block, bool);
155 static void sel_remove_loop_preheader (void);
157 static bool insn_is_the_only_one_in_bb_p (insn_t);
158 static void create_initial_data_sets (basic_block);
160 static void invalidate_av_set (basic_block);
161 static void extend_insn_data (void);
162 static void sel_init_new_insn (insn_t, int);
163 static void finish_insns (void);
165 /* Various list functions. */
167 /* Copy an instruction list L. */
169 ilist_copy (ilist_t l)
171 ilist_t head = NULL, *tailp = &head;
175 ilist_add (tailp, ILIST_INSN (l));
176 tailp = &ILIST_NEXT (*tailp);
183 /* Invert an instruction list L. */
185 ilist_invert (ilist_t l)
191 ilist_add (&res, ILIST_INSN (l));
198 /* Add a new boundary to the LP list with parameters TO, PTR, and DC. */
200 blist_add (blist_t *lp, insn_t to, ilist_t ptr, deps_t dc)
205 bnd = BLIST_BND (*lp);
210 BND_AV1 (bnd) = NULL;
214 /* Remove the list note pointed to by LP. */
216 blist_remove (blist_t *lp)
218 bnd_t b = BLIST_BND (*lp);
220 av_set_clear (&BND_AV (b));
221 av_set_clear (&BND_AV1 (b));
222 ilist_clear (&BND_PTR (b));
227 /* Init a fence tail L. */
229 flist_tail_init (flist_tail_t l)
231 FLIST_TAIL_HEAD (l) = NULL;
232 FLIST_TAIL_TAILP (l) = &FLIST_TAIL_HEAD (l);
235 /* Try to find fence corresponding to INSN in L. */
237 flist_lookup (flist_t l, insn_t insn)
241 if (FENCE_INSN (FLIST_FENCE (l)) == insn)
242 return FLIST_FENCE (l);
250 /* Init the fields of F before running fill_insns. */
252 init_fence_for_scheduling (fence_t f)
254 FENCE_BNDS (f) = NULL;
255 FENCE_PROCESSED_P (f) = false;
256 FENCE_SCHEDULED_P (f) = false;
259 /* Add new fence consisting of INSN and STATE to the list pointed to by LP. */
261 flist_add (flist_t *lp, insn_t insn, state_t state, deps_t dc, void *tc,
262 insn_t last_scheduled_insn, VEC(rtx,gc) *executing_insns,
263 int *ready_ticks, int ready_ticks_size, insn_t sched_next,
264 int cycle, int cycle_issued_insns,
265 bool starts_cycle_p, bool after_stall_p)
270 f = FLIST_FENCE (*lp);
272 FENCE_INSN (f) = insn;
274 gcc_assert (state != NULL);
275 FENCE_STATE (f) = state;
277 FENCE_CYCLE (f) = cycle;
278 FENCE_ISSUED_INSNS (f) = cycle_issued_insns;
279 FENCE_STARTS_CYCLE_P (f) = starts_cycle_p;
280 FENCE_AFTER_STALL_P (f) = after_stall_p;
282 gcc_assert (dc != NULL);
285 gcc_assert (tc != NULL || targetm.sched.alloc_sched_context == NULL);
288 FENCE_LAST_SCHEDULED_INSN (f) = last_scheduled_insn;
289 FENCE_EXECUTING_INSNS (f) = executing_insns;
290 FENCE_READY_TICKS (f) = ready_ticks;
291 FENCE_READY_TICKS_SIZE (f) = ready_ticks_size;
292 FENCE_SCHED_NEXT (f) = sched_next;
294 init_fence_for_scheduling (f);
297 /* Remove the head node of the list pointed to by LP. */
299 flist_remove (flist_t *lp)
301 if (FENCE_INSN (FLIST_FENCE (*lp)))
302 fence_clear (FLIST_FENCE (*lp));
306 /* Clear the fence list pointed to by LP. */
308 flist_clear (flist_t *lp)
314 /* Add ORIGINAL_INSN the def list DL honoring CROSSES_CALL. */
316 def_list_add (def_list_t *dl, insn_t original_insn, bool crosses_call)
321 d = DEF_LIST_DEF (*dl);
323 d->orig_insn = original_insn;
324 d->crosses_call = crosses_call;
328 /* Functions to work with target contexts. */
330 /* Bulk target context. It is convenient for debugging purposes to ensure
331 that there are no uninitialized (null) target contexts. */
332 static tc_t bulk_tc = (tc_t) 1;
334 /* Target hooks wrappers. In the future we can provide some default
335 implementations for them. */
337 /* Allocate a store for the target context. */
339 alloc_target_context (void)
341 return (targetm.sched.alloc_sched_context
342 ? targetm.sched.alloc_sched_context () : bulk_tc);
345 /* Init target context TC.
346 If CLEAN_P is true, then make TC as it is beginning of the scheduler.
347 Overwise, copy current backend context to TC. */
349 init_target_context (tc_t tc, bool clean_p)
351 if (targetm.sched.init_sched_context)
352 targetm.sched.init_sched_context (tc, clean_p);
355 /* Allocate and initialize a target context. Meaning of CLEAN_P is the same as
356 int init_target_context (). */
358 create_target_context (bool clean_p)
360 tc_t tc = alloc_target_context ();
362 init_target_context (tc, clean_p);
366 /* Copy TC to the current backend context. */
368 set_target_context (tc_t tc)
370 if (targetm.sched.set_sched_context)
371 targetm.sched.set_sched_context (tc);
374 /* TC is about to be destroyed. Free any internal data. */
376 clear_target_context (tc_t tc)
378 if (targetm.sched.clear_sched_context)
379 targetm.sched.clear_sched_context (tc);
382 /* Clear and free it. */
384 delete_target_context (tc_t tc)
386 clear_target_context (tc);
388 if (targetm.sched.free_sched_context)
389 targetm.sched.free_sched_context (tc);
392 /* Make a copy of FROM in TO.
393 NB: May be this should be a hook. */
395 copy_target_context (tc_t to, tc_t from)
397 tc_t tmp = create_target_context (false);
399 set_target_context (from);
400 init_target_context (to, false);
402 set_target_context (tmp);
403 delete_target_context (tmp);
406 /* Create a copy of TC. */
408 create_copy_of_target_context (tc_t tc)
410 tc_t copy = alloc_target_context ();
412 copy_target_context (copy, tc);
417 /* Clear TC and initialize it according to CLEAN_P. The meaning of CLEAN_P
418 is the same as in init_target_context (). */
420 reset_target_context (tc_t tc, bool clean_p)
422 clear_target_context (tc);
423 init_target_context (tc, clean_p);
426 /* Functions to work with dependence contexts.
427 Dc (aka deps context, aka deps_t, aka struct deps *) is short for dependence
428 context. It accumulates information about processed insns to decide if
429 current insn is dependent on the processed ones. */
431 /* Make a copy of FROM in TO. */
433 copy_deps_context (deps_t to, deps_t from)
436 deps_join (to, from);
439 /* Allocate store for dep context. */
441 alloc_deps_context (void)
443 return XNEW (struct deps);
446 /* Allocate and initialize dep context. */
448 create_deps_context (void)
450 deps_t dc = alloc_deps_context ();
456 /* Create a copy of FROM. */
458 create_copy_of_deps_context (deps_t from)
460 deps_t to = alloc_deps_context ();
462 copy_deps_context (to, from);
466 /* Clean up internal data of DC. */
468 clear_deps_context (deps_t dc)
473 /* Clear and free DC. */
475 delete_deps_context (deps_t dc)
477 clear_deps_context (dc);
481 /* Clear and init DC. */
483 reset_deps_context (deps_t dc)
485 clear_deps_context (dc);
489 /* This structure describes the dependence analysis hooks for advancing
490 dependence context. */
491 static struct sched_deps_info_def advance_deps_context_sched_deps_info =
495 NULL, /* start_insn */
496 NULL, /* finish_insn */
497 NULL, /* start_lhs */
498 NULL, /* finish_lhs */
499 NULL, /* start_rhs */
500 NULL, /* finish_rhs */
502 haifa_note_reg_clobber,
504 NULL, /* note_mem_dep */
510 /* Process INSN and add its impact on DC. */
512 advance_deps_context (deps_t dc, insn_t insn)
514 sched_deps_info = &advance_deps_context_sched_deps_info;
515 deps_analyze_insn (dc, insn);
519 /* Functions to work with DFA states. */
521 /* Allocate store for a DFA state. */
525 return xmalloc (dfa_state_size);
528 /* Allocate and initialize DFA state. */
532 state_t state = state_alloc ();
535 advance_state (state);
539 /* Free DFA state. */
541 state_free (state_t state)
546 /* Make a copy of FROM in TO. */
548 state_copy (state_t to, state_t from)
550 memcpy (to, from, dfa_state_size);
553 /* Create a copy of FROM. */
555 state_create_copy (state_t from)
557 state_t to = state_alloc ();
559 state_copy (to, from);
564 /* Functions to work with fences. */
566 /* Clear the fence. */
568 fence_clear (fence_t f)
570 state_t s = FENCE_STATE (f);
571 deps_t dc = FENCE_DC (f);
572 void *tc = FENCE_TC (f);
574 ilist_clear (&FENCE_BNDS (f));
576 gcc_assert ((s != NULL && dc != NULL && tc != NULL)
577 || (s == NULL && dc == NULL && tc == NULL));
583 delete_deps_context (dc);
586 delete_target_context (tc);
587 VEC_free (rtx, gc, FENCE_EXECUTING_INSNS (f));
588 free (FENCE_READY_TICKS (f));
589 FENCE_READY_TICKS (f) = NULL;
592 /* Init a list of fences with successors of OLD_FENCE. */
594 init_fences (insn_t old_fence)
599 int ready_ticks_size = get_max_uid () + 1;
601 FOR_EACH_SUCC_1 (succ, si, old_fence,
602 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
608 gcc_assert (flag_sel_sched_pipelining_outer_loops);
610 flist_add (&fences, succ,
612 create_deps_context () /* dc */,
613 create_target_context (true) /* tc */,
614 NULL_RTX /* last_scheduled_insn */,
615 NULL, /* executing_insns */
616 XCNEWVEC (int, ready_ticks_size), /* ready_ticks */
618 NULL_RTX /* sched_next */,
619 1 /* cycle */, 0 /* cycle_issued_insns */,
620 1 /* starts_cycle_p */, 0 /* after_stall_p */);
624 /* Merges two fences (filling fields of fence F with resulting values) by
625 following rules: 1) state, target context and last scheduled insn are
626 propagated from fallthrough edge if it is available;
627 2) deps context and cycle is propagated from more probable edge;
628 3) all other fields are set to corresponding constant values.
630 INSN, STATE, DC, TC, LAST_SCHEDULED_INSN, EXECUTING_INSNS,
631 READY_TICKS, READY_TICKS_SIZE, SCHED_NEXT, CYCLE and AFTER_STALL_P
632 are the corresponding fields of the second fence. */
634 merge_fences (fence_t f, insn_t insn,
635 state_t state, deps_t dc, void *tc,
636 rtx last_scheduled_insn, VEC(rtx, gc) *executing_insns,
637 int *ready_ticks, int ready_ticks_size,
638 rtx sched_next, int cycle, bool after_stall_p)
640 insn_t last_scheduled_insn_old = FENCE_LAST_SCHEDULED_INSN (f);
642 gcc_assert (sel_bb_head_p (FENCE_INSN (f))
643 && !sched_next && !FENCE_SCHED_NEXT (f));
645 /* Check if we can decide which path fences came.
646 If we can't (or don't want to) - reset all. */
647 if (last_scheduled_insn == NULL
648 || last_scheduled_insn_old == NULL
649 /* This is a case when INSN is reachable on several paths from
650 one insn (this can happen when pipelining of outer loops is on and
651 there are two edges: one going around of inner loop and the other -
652 right through it; in such case just reset everything). */
653 || last_scheduled_insn == last_scheduled_insn_old)
655 state_reset (FENCE_STATE (f));
658 reset_deps_context (FENCE_DC (f));
659 delete_deps_context (dc);
661 reset_target_context (FENCE_TC (f), true);
662 delete_target_context (tc);
664 if (cycle > FENCE_CYCLE (f))
665 FENCE_CYCLE (f) = cycle;
667 FENCE_LAST_SCHEDULED_INSN (f) = NULL;
668 VEC_free (rtx, gc, executing_insns);
670 if (FENCE_EXECUTING_INSNS (f))
671 VEC_block_remove (rtx, FENCE_EXECUTING_INSNS (f), 0,
672 VEC_length (rtx, FENCE_EXECUTING_INSNS (f)));
673 if (FENCE_READY_TICKS (f))
674 memset (FENCE_READY_TICKS (f), 0, FENCE_READY_TICKS_SIZE (f));
678 edge edge_old = NULL, edge_new = NULL;
683 /* Find fallthrough edge. */
684 gcc_assert (BLOCK_FOR_INSN (insn)->prev_bb);
685 candidate = find_fallthru_edge (BLOCK_FOR_INSN (insn)->prev_bb);
688 || (candidate->src != BLOCK_FOR_INSN (last_scheduled_insn)
689 && candidate->src != BLOCK_FOR_INSN (last_scheduled_insn_old)))
691 /* No fallthrough edge leading to basic block of INSN. */
692 state_reset (FENCE_STATE (f));
695 reset_target_context (FENCE_TC (f), true);
696 delete_target_context (tc);
698 FENCE_LAST_SCHEDULED_INSN (f) = NULL;
701 if (candidate->src == BLOCK_FOR_INSN (last_scheduled_insn))
703 /* Would be weird if same insn is successor of several fallthrough
705 gcc_assert (BLOCK_FOR_INSN (insn)->prev_bb
706 != BLOCK_FOR_INSN (last_scheduled_insn_old));
708 state_free (FENCE_STATE (f));
709 FENCE_STATE (f) = state;
711 delete_target_context (FENCE_TC (f));
714 FENCE_LAST_SCHEDULED_INSN (f) = last_scheduled_insn;
718 /* Leave STATE, TC and LAST_SCHEDULED_INSN fields untouched. */
720 delete_target_context (tc);
722 gcc_assert (BLOCK_FOR_INSN (insn)->prev_bb
723 != BLOCK_FOR_INSN (last_scheduled_insn));
726 /* Find edge of first predecessor (last_scheduled_insn_old->insn). */
727 FOR_EACH_SUCC_1 (succ, si, last_scheduled_insn_old,
728 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
732 /* No same successor allowed from several edges. */
733 gcc_assert (!edge_old);
737 /* Find edge of second predecessor (last_scheduled_insn->insn). */
738 FOR_EACH_SUCC_1 (succ, si, last_scheduled_insn,
739 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
743 /* No same successor allowed from several edges. */
744 gcc_assert (!edge_new);
749 /* Check if we can choose most probable predecessor. */
750 if (edge_old == NULL || edge_new == NULL)
752 reset_deps_context (FENCE_DC (f));
753 delete_deps_context (dc);
754 VEC_free (rtx, gc, executing_insns);
757 FENCE_CYCLE (f) = MAX (FENCE_CYCLE (f), cycle);
758 if (FENCE_EXECUTING_INSNS (f))
759 VEC_block_remove (rtx, FENCE_EXECUTING_INSNS (f), 0,
760 VEC_length (rtx, FENCE_EXECUTING_INSNS (f)));
761 if (FENCE_READY_TICKS (f))
762 memset (FENCE_READY_TICKS (f), 0, FENCE_READY_TICKS_SIZE (f));
765 if (edge_new->probability > edge_old->probability)
767 delete_deps_context (FENCE_DC (f));
769 VEC_free (rtx, gc, FENCE_EXECUTING_INSNS (f));
770 FENCE_EXECUTING_INSNS (f) = executing_insns;
771 free (FENCE_READY_TICKS (f));
772 FENCE_READY_TICKS (f) = ready_ticks;
773 FENCE_READY_TICKS_SIZE (f) = ready_ticks_size;
774 FENCE_CYCLE (f) = cycle;
778 /* Leave DC and CYCLE untouched. */
779 delete_deps_context (dc);
780 VEC_free (rtx, gc, executing_insns);
785 /* Fill remaining invariant fields. */
787 FENCE_AFTER_STALL_P (f) = 1;
789 FENCE_ISSUED_INSNS (f) = 0;
790 FENCE_STARTS_CYCLE_P (f) = 1;
791 FENCE_SCHED_NEXT (f) = NULL;
794 /* Add a new fence to NEW_FENCES list, initializing it from all
797 add_to_fences (flist_tail_t new_fences, insn_t insn,
798 state_t state, deps_t dc, void *tc, rtx last_scheduled_insn,
799 VEC(rtx, gc) *executing_insns, int *ready_ticks,
800 int ready_ticks_size, rtx sched_next, int cycle,
801 int cycle_issued_insns, bool starts_cycle_p, bool after_stall_p)
803 fence_t f = flist_lookup (FLIST_TAIL_HEAD (new_fences), insn);
807 flist_add (FLIST_TAIL_TAILP (new_fences), insn, state, dc, tc,
808 last_scheduled_insn, executing_insns, ready_ticks,
809 ready_ticks_size, sched_next, cycle, cycle_issued_insns,
810 starts_cycle_p, after_stall_p);
812 FLIST_TAIL_TAILP (new_fences)
813 = &FLIST_NEXT (*FLIST_TAIL_TAILP (new_fences));
817 merge_fences (f, insn, state, dc, tc, last_scheduled_insn,
818 executing_insns, ready_ticks, ready_ticks_size,
819 sched_next, cycle, after_stall_p);
823 /* Move the first fence in the OLD_FENCES list to NEW_FENCES. */
825 move_fence_to_fences (flist_t old_fences, flist_tail_t new_fences)
828 flist_t *tailp = FLIST_TAIL_TAILP (new_fences);
830 old = FLIST_FENCE (old_fences);
831 f = flist_lookup (FLIST_TAIL_HEAD (new_fences),
832 FENCE_INSN (FLIST_FENCE (old_fences)));
835 merge_fences (f, old->insn, old->state, old->dc, old->tc,
836 old->last_scheduled_insn, old->executing_insns,
837 old->ready_ticks, old->ready_ticks_size,
838 old->sched_next, old->cycle,
844 FLIST_TAIL_TAILP (new_fences) = &FLIST_NEXT (*tailp);
845 *FLIST_FENCE (*tailp) = *old;
846 init_fence_for_scheduling (FLIST_FENCE (*tailp));
848 FENCE_INSN (old) = NULL;
851 /* Add a new fence to NEW_FENCES list and initialize most of its data
854 add_clean_fence_to_fences (flist_tail_t new_fences, insn_t succ, fence_t fence)
856 int ready_ticks_size = get_max_uid () + 1;
858 add_to_fences (new_fences,
859 succ, state_create (), create_deps_context (),
860 create_target_context (true),
862 XCNEWVEC (int, ready_ticks_size), ready_ticks_size,
863 NULL_RTX, FENCE_CYCLE (fence) + 1,
864 0, 1, FENCE_AFTER_STALL_P (fence));
867 /* Add a new fence to NEW_FENCES list and initialize all of its data
868 from FENCE and SUCC. */
870 add_dirty_fence_to_fences (flist_tail_t new_fences, insn_t succ, fence_t fence)
872 int * new_ready_ticks
873 = XNEWVEC (int, FENCE_READY_TICKS_SIZE (fence));
875 memcpy (new_ready_ticks, FENCE_READY_TICKS (fence),
876 FENCE_READY_TICKS_SIZE (fence) * sizeof (int));
877 add_to_fences (new_fences,
878 succ, state_create_copy (FENCE_STATE (fence)),
879 create_copy_of_deps_context (FENCE_DC (fence)),
880 create_copy_of_target_context (FENCE_TC (fence)),
881 FENCE_LAST_SCHEDULED_INSN (fence),
882 VEC_copy (rtx, gc, FENCE_EXECUTING_INSNS (fence)),
884 FENCE_READY_TICKS_SIZE (fence),
885 FENCE_SCHED_NEXT (fence),
887 FENCE_ISSUED_INSNS (fence),
888 FENCE_STARTS_CYCLE_P (fence),
889 FENCE_AFTER_STALL_P (fence));
893 /* Functions to work with regset and nop pools. */
895 /* Returns the new regset from pool. It might have some of the bits set
896 from the previous usage. */
898 get_regset_from_pool (void)
902 if (regset_pool.n != 0)
903 rs = regset_pool.v[--regset_pool.n];
905 /* We need to create the regset. */
907 rs = ALLOC_REG_SET (®_obstack);
909 if (regset_pool.nn == regset_pool.ss)
910 regset_pool.vv = XRESIZEVEC (regset, regset_pool.vv,
911 (regset_pool.ss = 2 * regset_pool.ss + 1));
912 regset_pool.vv[regset_pool.nn++] = rs;
920 /* Same as above, but returns the empty regset. */
922 get_clear_regset_from_pool (void)
924 regset rs = get_regset_from_pool ();
930 /* Return regset RS to the pool for future use. */
932 return_regset_to_pool (regset rs)
936 if (regset_pool.n == regset_pool.s)
937 regset_pool.v = XRESIZEVEC (regset, regset_pool.v,
938 (regset_pool.s = 2 * regset_pool.s + 1));
939 regset_pool.v[regset_pool.n++] = rs;
942 /* This is used as a qsort callback for sorting regset pool stacks.
943 X and XX are addresses of two regsets. They are never equal. */
945 cmp_v_in_regset_pool (const void *x, const void *xx)
947 return *((const regset *) x) - *((const regset *) xx);
950 /* Free the regset pool possibly checking for memory leaks. */
952 free_regset_pool (void)
954 #ifdef ENABLE_CHECKING
956 regset *v = regset_pool.v;
958 int n = regset_pool.n;
960 regset *vv = regset_pool.vv;
962 int nn = regset_pool.nn;
966 gcc_assert (n <= nn);
968 /* Sort both vectors so it will be possible to compare them. */
969 qsort (v, n, sizeof (*v), cmp_v_in_regset_pool);
970 qsort (vv, nn, sizeof (*vv), cmp_v_in_regset_pool);
977 /* VV[II] was lost. */
983 gcc_assert (diff == regset_pool.diff);
987 /* If not true - we have a memory leak. */
988 gcc_assert (regset_pool.diff == 0);
990 while (regset_pool.n)
993 FREE_REG_SET (regset_pool.v[regset_pool.n]);
996 free (regset_pool.v);
997 regset_pool.v = NULL;
1000 free (regset_pool.vv);
1001 regset_pool.vv = NULL;
1005 regset_pool.diff = 0;
1009 /* Functions to work with nop pools. NOP insns are used as temporary
1010 placeholders of the insns being scheduled to allow correct update of
1011 the data sets. When update is finished, NOPs are deleted. */
1013 /* A vinsn that is used to represent a nop. This vinsn is shared among all
1014 nops sel-sched generates. */
1015 static vinsn_t nop_vinsn = NULL;
1017 /* Emit a nop before INSN, taking it from pool. */
1019 get_nop_from_pool (insn_t insn)
1022 bool old_p = nop_pool.n != 0;
1026 nop = nop_pool.v[--nop_pool.n];
1030 nop = emit_insn_before (nop, insn);
1033 flags = INSN_INIT_TODO_SSID;
1035 flags = INSN_INIT_TODO_LUID | INSN_INIT_TODO_SSID;
1037 set_insn_init (INSN_EXPR (insn), nop_vinsn, INSN_SEQNO (insn));
1038 sel_init_new_insn (nop, flags);
1043 /* Remove NOP from the instruction stream and return it to the pool. */
1045 return_nop_to_pool (insn_t nop)
1047 gcc_assert (INSN_IN_STREAM_P (nop));
1048 sel_remove_insn (nop, false, true);
1050 if (nop_pool.n == nop_pool.s)
1051 nop_pool.v = XRESIZEVEC (rtx, nop_pool.v,
1052 (nop_pool.s = 2 * nop_pool.s + 1));
1053 nop_pool.v[nop_pool.n++] = nop;
1056 /* Free the nop pool. */
1058 free_nop_pool (void)
1067 /* Skip unspec to support ia64 speculation. Called from rtx_equal_p_cb.
1068 The callback is given two rtxes XX and YY and writes the new rtxes
1069 to NX and NY in case some needs to be skipped. */
1071 skip_unspecs_callback (const_rtx *xx, const_rtx *yy, rtx *nx, rtx* ny)
1076 if (GET_CODE (x) == UNSPEC
1077 && (targetm.sched.skip_rtx_p == NULL
1078 || targetm.sched.skip_rtx_p (x)))
1080 *nx = XVECEXP (x, 0, 0);
1081 *ny = CONST_CAST_RTX (y);
1085 if (GET_CODE (y) == UNSPEC
1086 && (targetm.sched.skip_rtx_p == NULL
1087 || targetm.sched.skip_rtx_p (y)))
1089 *nx = CONST_CAST_RTX (x);
1090 *ny = XVECEXP (y, 0, 0);
1097 /* Callback, called from hash_rtx_cb. Helps to hash UNSPEC rtx X in a correct way
1098 to support ia64 speculation. When changes are needed, new rtx X and new mode
1099 NMODE are written, and the callback returns true. */
1101 hash_with_unspec_callback (const_rtx x, enum machine_mode mode ATTRIBUTE_UNUSED,
1102 rtx *nx, enum machine_mode* nmode)
1104 if (GET_CODE (x) == UNSPEC
1105 && targetm.sched.skip_rtx_p
1106 && targetm.sched.skip_rtx_p (x))
1108 *nx = XVECEXP (x, 0 ,0);
1116 /* Returns LHS and RHS are ok to be scheduled separately. */
1118 lhs_and_rhs_separable_p (rtx lhs, rtx rhs)
1120 if (lhs == NULL || rhs == NULL)
1123 /* Do not schedule CONST, CONST_INT and CONST_DOUBLE etc as rhs: no point
1124 to use reg, if const can be used. Moreover, scheduling const as rhs may
1125 lead to mode mismatch cause consts don't have modes but they could be
1126 merged from branches where the same const used in different modes. */
1127 if (CONSTANT_P (rhs))
1130 /* ??? Do not rename predicate registers to avoid ICEs in bundling. */
1131 if (COMPARISON_P (rhs))
1134 /* Do not allow single REG to be an rhs. */
1138 /* See comment at find_used_regs_1 (*1) for explanation of this
1140 /* FIXME: remove this later. */
1144 /* This will filter all tricky things like ZERO_EXTRACT etc.
1145 For now we don't handle it. */
1146 if (!REG_P (lhs) && !MEM_P (lhs))
1152 /* Initialize vinsn VI for INSN. Only for use from vinsn_create (). When
1153 FORCE_UNIQUE_P is true, the resulting vinsn will not be clonable. This is
1154 used e.g. for insns from recovery blocks. */
1156 vinsn_init (vinsn_t vi, insn_t insn, bool force_unique_p)
1158 hash_rtx_callback_function hrcf;
1161 VINSN_INSN_RTX (vi) = insn;
1162 VINSN_COUNT (vi) = 0;
1165 if (DF_INSN_UID_SAFE_GET (INSN_UID (insn)) != NULL)
1166 init_id_from_df (VINSN_ID (vi), insn, force_unique_p);
1168 deps_init_id (VINSN_ID (vi), insn, force_unique_p);
1170 /* Hash vinsn depending on whether it is separable or not. */
1171 hrcf = targetm.sched.skip_rtx_p ? hash_with_unspec_callback : NULL;
1172 if (VINSN_SEPARABLE_P (vi))
1174 rtx rhs = VINSN_RHS (vi);
1176 VINSN_HASH (vi) = hash_rtx_cb (rhs, GET_MODE (rhs),
1177 NULL, NULL, false, hrcf);
1178 VINSN_HASH_RTX (vi) = hash_rtx_cb (VINSN_PATTERN (vi),
1179 VOIDmode, NULL, NULL,
1184 VINSN_HASH (vi) = hash_rtx_cb (VINSN_PATTERN (vi), VOIDmode,
1185 NULL, NULL, false, hrcf);
1186 VINSN_HASH_RTX (vi) = VINSN_HASH (vi);
1189 insn_class = haifa_classify_insn (insn);
1191 && (!targetm.sched.get_insn_spec_ds
1192 || ((targetm.sched.get_insn_spec_ds (insn) & BEGIN_CONTROL)
1194 VINSN_MAY_TRAP_P (vi) = true;
1196 VINSN_MAY_TRAP_P (vi) = false;
1199 /* Indicate that VI has become the part of an rtx object. */
1201 vinsn_attach (vinsn_t vi)
1203 /* Assert that VI is not pending for deletion. */
1204 gcc_assert (VINSN_INSN_RTX (vi));
1209 /* Create and init VI from the INSN. Use UNIQUE_P for determining the correct
1212 vinsn_create (insn_t insn, bool force_unique_p)
1214 vinsn_t vi = XCNEW (struct vinsn_def);
1216 vinsn_init (vi, insn, force_unique_p);
1220 /* Return a copy of VI. When REATTACH_P is true, detach VI and attach
1223 vinsn_copy (vinsn_t vi, bool reattach_p)
1226 bool unique = VINSN_UNIQUE_P (vi);
1229 copy = create_copy_of_insn_rtx (VINSN_INSN_RTX (vi));
1230 new_vi = create_vinsn_from_insn_rtx (copy, unique);
1234 vinsn_attach (new_vi);
1240 /* Delete the VI vinsn and free its data. */
1242 vinsn_delete (vinsn_t vi)
1244 gcc_assert (VINSN_COUNT (vi) == 0);
1246 return_regset_to_pool (VINSN_REG_SETS (vi));
1247 return_regset_to_pool (VINSN_REG_USES (vi));
1248 return_regset_to_pool (VINSN_REG_CLOBBERS (vi));
1253 /* Indicate that VI is no longer a part of some rtx object.
1254 Remove VI if it is no longer needed. */
1256 vinsn_detach (vinsn_t vi)
1258 gcc_assert (VINSN_COUNT (vi) > 0);
1260 if (--VINSN_COUNT (vi) == 0)
1264 /* Returns TRUE if VI is a branch. */
1266 vinsn_cond_branch_p (vinsn_t vi)
1270 if (!VINSN_UNIQUE_P (vi))
1273 insn = VINSN_INSN_RTX (vi);
1274 if (BB_END (BLOCK_FOR_INSN (insn)) != insn)
1277 return control_flow_insn_p (insn);
1280 /* Return latency of INSN. */
1282 sel_insn_rtx_cost (rtx insn)
1286 /* A USE insn, or something else we don't need to
1287 understand. We can't pass these directly to
1288 result_ready_cost or insn_default_latency because it will
1289 trigger a fatal error for unrecognizable insns. */
1290 if (recog_memoized (insn) < 0)
1294 cost = insn_default_latency (insn);
1303 /* Return the cost of the VI.
1304 !!! FIXME: Unify with haifa-sched.c: insn_cost (). */
1306 sel_vinsn_cost (vinsn_t vi)
1308 int cost = vi->cost;
1312 cost = sel_insn_rtx_cost (VINSN_INSN_RTX (vi));
1320 /* Functions for insn emitting. */
1322 /* Emit new insn after AFTER based on PATTERN and initialize its data from
1325 sel_gen_insn_from_rtx_after (rtx pattern, expr_t expr, int seqno, insn_t after)
1329 gcc_assert (EXPR_TARGET_AVAILABLE (expr) == true);
1331 new_insn = emit_insn_after (pattern, after);
1332 set_insn_init (expr, NULL, seqno);
1333 sel_init_new_insn (new_insn, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SSID);
1338 /* Force newly generated vinsns to be unique. */
1339 static bool init_insn_force_unique_p = false;
1341 /* Emit new speculation recovery insn after AFTER based on PATTERN and
1342 initialize its data from EXPR and SEQNO. */
1344 sel_gen_recovery_insn_from_rtx_after (rtx pattern, expr_t expr, int seqno,
1349 gcc_assert (!init_insn_force_unique_p);
1351 init_insn_force_unique_p = true;
1352 insn = sel_gen_insn_from_rtx_after (pattern, expr, seqno, after);
1353 CANT_MOVE (insn) = 1;
1354 init_insn_force_unique_p = false;
1359 /* Emit new insn after AFTER based on EXPR and SEQNO. If VINSN is not NULL,
1360 take it as a new vinsn instead of EXPR's vinsn.
1361 We simplify insns later, after scheduling region in
1362 simplify_changed_insns. */
1364 sel_gen_insn_from_expr_after (expr_t expr, vinsn_t vinsn, int seqno,
1371 emit_expr = set_insn_init (expr, vinsn ? vinsn : EXPR_VINSN (expr),
1373 insn = EXPR_INSN_RTX (emit_expr);
1374 add_insn_after (insn, after, BLOCK_FOR_INSN (insn));
1376 flags = INSN_INIT_TODO_SSID;
1377 if (INSN_LUID (insn) == 0)
1378 flags |= INSN_INIT_TODO_LUID;
1379 sel_init_new_insn (insn, flags);
1384 /* Move insn from EXPR after AFTER. */
1386 sel_move_insn (expr_t expr, int seqno, insn_t after)
1388 insn_t insn = EXPR_INSN_RTX (expr);
1389 basic_block bb = BLOCK_FOR_INSN (after);
1390 insn_t next = NEXT_INSN (after);
1392 /* Assert that in move_op we disconnected this insn properly. */
1393 gcc_assert (EXPR_VINSN (INSN_EXPR (insn)) != NULL);
1394 PREV_INSN (insn) = after;
1395 NEXT_INSN (insn) = next;
1397 NEXT_INSN (after) = insn;
1398 PREV_INSN (next) = insn;
1400 /* Update links from insn to bb and vice versa. */
1401 df_insn_change_bb (insn, bb);
1402 if (BB_END (bb) == after)
1405 prepare_insn_expr (insn, seqno);
1410 /* Functions to work with right-hand sides. */
1412 /* Search for a hash value determined by UID/NEW_VINSN in a sorted vector
1413 VECT and return true when found. Use NEW_VINSN for comparison only when
1414 COMPARE_VINSNS is true. Write to INDP the index on which
1415 the search has stopped, such that inserting the new element at INDP will
1416 retain VECT's sort order. */
1418 find_in_history_vect_1 (VEC(expr_history_def, heap) *vect,
1419 unsigned uid, vinsn_t new_vinsn,
1420 bool compare_vinsns, int *indp)
1422 expr_history_def *arr;
1423 int i, j, len = VEC_length (expr_history_def, vect);
1431 arr = VEC_address (expr_history_def, vect);
1436 unsigned auid = arr[i].uid;
1437 vinsn_t avinsn = arr[i].new_expr_vinsn;
1440 /* When undoing transformation on a bookkeeping copy, the new vinsn
1441 may not be exactly equal to the one that is saved in the vector.
1442 This is because the insn whose copy we're checking was possibly
1443 substituted itself. */
1444 && (! compare_vinsns
1445 || vinsn_equal_p (avinsn, new_vinsn)))
1450 else if (auid > uid)
1459 /* Search for a uid of INSN and NEW_VINSN in a sorted vector VECT. Return
1460 the position found or -1, if no such value is in vector.
1461 Search also for UIDs of insn's originators, if ORIGINATORS_P is true. */
1463 find_in_history_vect (VEC(expr_history_def, heap) *vect, rtx insn,
1464 vinsn_t new_vinsn, bool originators_p)
1468 if (find_in_history_vect_1 (vect, INSN_UID (insn), new_vinsn,
1472 if (INSN_ORIGINATORS (insn) && originators_p)
1477 EXECUTE_IF_SET_IN_BITMAP (INSN_ORIGINATORS (insn), 0, uid, bi)
1478 if (find_in_history_vect_1 (vect, uid, new_vinsn, false, &ind))
1485 /* Insert new element in a sorted history vector pointed to by PVECT,
1486 if it is not there already. The element is searched using
1487 UID/NEW_EXPR_VINSN pair. TYPE, OLD_EXPR_VINSN and SPEC_DS save
1488 the history of a transformation. */
1490 insert_in_history_vect (VEC (expr_history_def, heap) **pvect,
1491 unsigned uid, enum local_trans_type type,
1492 vinsn_t old_expr_vinsn, vinsn_t new_expr_vinsn,
1495 VEC(expr_history_def, heap) *vect = *pvect;
1496 expr_history_def temp;
1500 res = find_in_history_vect_1 (vect, uid, new_expr_vinsn, true, &ind);
1504 expr_history_def *phist = VEC_index (expr_history_def, vect, ind);
1506 /* When merging, either old vinsns are the *same* or, if not, both
1507 old and new vinsns are different pointers. In the latter case,
1508 though, new vinsns should be equal. */
1509 gcc_assert (phist->old_expr_vinsn == old_expr_vinsn
1510 || (phist->new_expr_vinsn != new_expr_vinsn
1512 (phist->old_expr_vinsn, old_expr_vinsn))));
1514 /* It is possible that speculation types of expressions that were
1515 propagated through different paths will be different here. In this
1516 case, merge the status to get the correct check later. */
1517 if (phist->spec_ds != spec_ds)
1518 phist->spec_ds = ds_max_merge (phist->spec_ds, spec_ds);
1523 temp.old_expr_vinsn = old_expr_vinsn;
1524 temp.new_expr_vinsn = new_expr_vinsn;
1525 temp.spec_ds = spec_ds;
1528 vinsn_attach (old_expr_vinsn);
1529 vinsn_attach (new_expr_vinsn);
1530 VEC_safe_insert (expr_history_def, heap, vect, ind, &temp);
1534 /* Free history vector PVECT. */
1536 free_history_vect (VEC (expr_history_def, heap) **pvect)
1539 expr_history_def *phist;
1545 VEC_iterate (expr_history_def, *pvect, i, phist);
1548 vinsn_detach (phist->old_expr_vinsn);
1549 vinsn_detach (phist->new_expr_vinsn);
1552 VEC_free (expr_history_def, heap, *pvect);
1557 /* Compare two vinsns as rhses if possible and as vinsns otherwise. */
1559 vinsn_equal_p (vinsn_t x, vinsn_t y)
1561 rtx_equal_p_callback_function repcf;
1566 if (VINSN_TYPE (x) != VINSN_TYPE (y))
1569 if (VINSN_HASH (x) != VINSN_HASH (y))
1572 repcf = targetm.sched.skip_rtx_p ? skip_unspecs_callback : NULL;
1573 if (VINSN_SEPARABLE_P (x))
1575 /* Compare RHSes of VINSNs. */
1576 gcc_assert (VINSN_RHS (x));
1577 gcc_assert (VINSN_RHS (y));
1579 return rtx_equal_p_cb (VINSN_RHS (x), VINSN_RHS (y), repcf);
1582 return rtx_equal_p_cb (VINSN_PATTERN (x), VINSN_PATTERN (y), repcf);
1586 /* Functions for working with expressions. */
1588 /* Initialize EXPR. */
1590 init_expr (expr_t expr, vinsn_t vi, int spec, int use, int priority,
1591 int sched_times, int orig_bb_index, ds_t spec_done_ds,
1592 ds_t spec_to_check_ds, int orig_sched_cycle,
1593 VEC(expr_history_def, heap) *history, bool target_available,
1594 bool was_substituted, bool was_renamed, bool needs_spec_check_p,
1599 EXPR_VINSN (expr) = vi;
1600 EXPR_SPEC (expr) = spec;
1601 EXPR_USEFULNESS (expr) = use;
1602 EXPR_PRIORITY (expr) = priority;
1603 EXPR_PRIORITY_ADJ (expr) = 0;
1604 EXPR_SCHED_TIMES (expr) = sched_times;
1605 EXPR_ORIG_BB_INDEX (expr) = orig_bb_index;
1606 EXPR_ORIG_SCHED_CYCLE (expr) = orig_sched_cycle;
1607 EXPR_SPEC_DONE_DS (expr) = spec_done_ds;
1608 EXPR_SPEC_TO_CHECK_DS (expr) = spec_to_check_ds;
1611 EXPR_HISTORY_OF_CHANGES (expr) = history;
1613 EXPR_HISTORY_OF_CHANGES (expr) = NULL;
1615 EXPR_TARGET_AVAILABLE (expr) = target_available;
1616 EXPR_WAS_SUBSTITUTED (expr) = was_substituted;
1617 EXPR_WAS_RENAMED (expr) = was_renamed;
1618 EXPR_NEEDS_SPEC_CHECK_P (expr) = needs_spec_check_p;
1619 EXPR_CANT_MOVE (expr) = cant_move;
1622 /* Make a copy of the expr FROM into the expr TO. */
1624 copy_expr (expr_t to, expr_t from)
1626 VEC(expr_history_def, heap) *temp = NULL;
1628 if (EXPR_HISTORY_OF_CHANGES (from))
1631 expr_history_def *phist;
1633 temp = VEC_copy (expr_history_def, heap, EXPR_HISTORY_OF_CHANGES (from));
1635 VEC_iterate (expr_history_def, temp, i, phist);
1638 vinsn_attach (phist->old_expr_vinsn);
1639 vinsn_attach (phist->new_expr_vinsn);
1643 init_expr (to, EXPR_VINSN (from), EXPR_SPEC (from),
1644 EXPR_USEFULNESS (from), EXPR_PRIORITY (from),
1645 EXPR_SCHED_TIMES (from), EXPR_ORIG_BB_INDEX (from),
1646 EXPR_SPEC_DONE_DS (from), EXPR_SPEC_TO_CHECK_DS (from),
1647 EXPR_ORIG_SCHED_CYCLE (from), temp,
1648 EXPR_TARGET_AVAILABLE (from), EXPR_WAS_SUBSTITUTED (from),
1649 EXPR_WAS_RENAMED (from), EXPR_NEEDS_SPEC_CHECK_P (from),
1650 EXPR_CANT_MOVE (from));
1653 /* Same, but the final expr will not ever be in av sets, so don't copy
1654 "uninteresting" data such as bitmap cache. */
1656 copy_expr_onside (expr_t to, expr_t from)
1658 init_expr (to, EXPR_VINSN (from), EXPR_SPEC (from), EXPR_USEFULNESS (from),
1659 EXPR_PRIORITY (from), EXPR_SCHED_TIMES (from), 0,
1660 EXPR_SPEC_DONE_DS (from), EXPR_SPEC_TO_CHECK_DS (from), 0, NULL,
1661 EXPR_TARGET_AVAILABLE (from), EXPR_WAS_SUBSTITUTED (from),
1662 EXPR_WAS_RENAMED (from), EXPR_NEEDS_SPEC_CHECK_P (from),
1663 EXPR_CANT_MOVE (from));
1666 /* Prepare the expr of INSN for scheduling. Used when moving insn and when
1667 initializing new insns. */
1669 prepare_insn_expr (insn_t insn, int seqno)
1671 expr_t expr = INSN_EXPR (insn);
1674 INSN_SEQNO (insn) = seqno;
1675 EXPR_ORIG_BB_INDEX (expr) = BLOCK_NUM (insn);
1676 EXPR_SPEC (expr) = 0;
1677 EXPR_ORIG_SCHED_CYCLE (expr) = 0;
1678 EXPR_WAS_SUBSTITUTED (expr) = 0;
1679 EXPR_WAS_RENAMED (expr) = 0;
1680 EXPR_TARGET_AVAILABLE (expr) = 1;
1681 INSN_LIVE_VALID_P (insn) = false;
1683 /* ??? If this expression is speculative, make its dependence
1684 as weak as possible. We can filter this expression later
1685 in process_spec_exprs, because we do not distinguish
1686 between the status we got during compute_av_set and the
1687 existing status. To be fixed. */
1688 ds = EXPR_SPEC_DONE_DS (expr);
1690 EXPR_SPEC_DONE_DS (expr) = ds_get_max_dep_weak (ds);
1692 free_history_vect (&EXPR_HISTORY_OF_CHANGES (expr));
1695 /* Update target_available bits when merging exprs TO and FROM. SPLIT_POINT
1696 is non-null when expressions are merged from different successors at
1699 update_target_availability (expr_t to, expr_t from, insn_t split_point)
1701 if (EXPR_TARGET_AVAILABLE (to) < 0
1702 || EXPR_TARGET_AVAILABLE (from) < 0)
1703 EXPR_TARGET_AVAILABLE (to) = -1;
1706 /* We try to detect the case when one of the expressions
1707 can only be reached through another one. In this case,
1708 we can do better. */
1709 if (split_point == NULL)
1713 toind = EXPR_ORIG_BB_INDEX (to);
1714 fromind = EXPR_ORIG_BB_INDEX (from);
1716 if (toind && toind == fromind)
1717 /* Do nothing -- everything is done in
1718 merge_with_other_exprs. */
1721 EXPR_TARGET_AVAILABLE (to) = -1;
1724 EXPR_TARGET_AVAILABLE (to) &= EXPR_TARGET_AVAILABLE (from);
1728 /* Update speculation bits when merging exprs TO and FROM. SPLIT_POINT
1729 is non-null when expressions are merged from different successors at
1732 update_speculative_bits (expr_t to, expr_t from, insn_t split_point)
1734 ds_t old_to_ds, old_from_ds;
1736 old_to_ds = EXPR_SPEC_DONE_DS (to);
1737 old_from_ds = EXPR_SPEC_DONE_DS (from);
1739 EXPR_SPEC_DONE_DS (to) = ds_max_merge (old_to_ds, old_from_ds);
1740 EXPR_SPEC_TO_CHECK_DS (to) |= EXPR_SPEC_TO_CHECK_DS (from);
1741 EXPR_NEEDS_SPEC_CHECK_P (to) |= EXPR_NEEDS_SPEC_CHECK_P (from);
1743 /* When merging e.g. control & data speculative exprs, or a control
1744 speculative with a control&data speculative one, we really have
1745 to change vinsn too. Also, when speculative status is changed,
1746 we also need to record this as a transformation in expr's history. */
1747 if ((old_to_ds & SPECULATIVE) || (old_from_ds & SPECULATIVE))
1749 old_to_ds = ds_get_speculation_types (old_to_ds);
1750 old_from_ds = ds_get_speculation_types (old_from_ds);
1752 if (old_to_ds != old_from_ds)
1756 /* When both expressions are speculative, we need to change
1758 if ((old_to_ds & SPECULATIVE) && (old_from_ds & SPECULATIVE))
1762 res = speculate_expr (to, EXPR_SPEC_DONE_DS (to));
1763 gcc_assert (res >= 0);
1766 if (split_point != NULL)
1768 /* Record the change with proper status. */
1769 record_ds = EXPR_SPEC_DONE_DS (to) & SPECULATIVE;
1770 record_ds &= ~(old_to_ds & SPECULATIVE);
1771 record_ds &= ~(old_from_ds & SPECULATIVE);
1773 insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (to),
1774 INSN_UID (split_point), TRANS_SPECULATION,
1775 EXPR_VINSN (from), EXPR_VINSN (to),
1783 /* Merge bits of FROM expr to TO expr. When SPLIT_POINT is not NULL,
1784 this is done along different paths. */
1786 merge_expr_data (expr_t to, expr_t from, insn_t split_point)
1789 expr_history_def *phist;
1791 /* For now, we just set the spec of resulting expr to be minimum of the specs
1793 if (EXPR_SPEC (to) > EXPR_SPEC (from))
1794 EXPR_SPEC (to) = EXPR_SPEC (from);
1797 EXPR_USEFULNESS (to) += EXPR_USEFULNESS (from);
1799 EXPR_USEFULNESS (to) = MAX (EXPR_USEFULNESS (to),
1800 EXPR_USEFULNESS (from));
1802 if (EXPR_PRIORITY (to) < EXPR_PRIORITY (from))
1803 EXPR_PRIORITY (to) = EXPR_PRIORITY (from);
1805 if (EXPR_SCHED_TIMES (to) > EXPR_SCHED_TIMES (from))
1806 EXPR_SCHED_TIMES (to) = EXPR_SCHED_TIMES (from);
1808 if (EXPR_ORIG_BB_INDEX (to) != EXPR_ORIG_BB_INDEX (from))
1809 EXPR_ORIG_BB_INDEX (to) = 0;
1811 EXPR_ORIG_SCHED_CYCLE (to) = MIN (EXPR_ORIG_SCHED_CYCLE (to),
1812 EXPR_ORIG_SCHED_CYCLE (from));
1814 /* We keep this vector sorted. */
1816 VEC_iterate (expr_history_def, EXPR_HISTORY_OF_CHANGES (from),
1819 insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (to),
1820 phist->uid, phist->type,
1821 phist->old_expr_vinsn, phist->new_expr_vinsn,
1824 EXPR_WAS_SUBSTITUTED (to) |= EXPR_WAS_SUBSTITUTED (from);
1825 EXPR_WAS_RENAMED (to) |= EXPR_WAS_RENAMED (from);
1826 EXPR_CANT_MOVE (to) |= EXPR_CANT_MOVE (from);
1828 update_target_availability (to, from, split_point);
1829 update_speculative_bits (to, from, split_point);
1832 /* Merge bits of FROM expr to TO expr. Vinsns in the exprs should be equal
1833 in terms of vinsn_equal_p. SPLIT_POINT is non-null when expressions
1834 are merged from different successors at a split point. */
1836 merge_expr (expr_t to, expr_t from, insn_t split_point)
1838 vinsn_t to_vi = EXPR_VINSN (to);
1839 vinsn_t from_vi = EXPR_VINSN (from);
1841 gcc_assert (vinsn_equal_p (to_vi, from_vi));
1843 /* Make sure that speculative pattern is propagated into exprs that
1844 have non-speculative one. This will provide us with consistent
1845 speculative bits and speculative patterns inside expr. */
1846 if (EXPR_SPEC_DONE_DS (to) == 0
1847 && EXPR_SPEC_DONE_DS (from) != 0)
1848 change_vinsn_in_expr (to, EXPR_VINSN (from));
1850 merge_expr_data (to, from, split_point);
1851 gcc_assert (EXPR_USEFULNESS (to) <= REG_BR_PROB_BASE);
1854 /* Clear the information of this EXPR. */
1856 clear_expr (expr_t expr)
1859 vinsn_detach (EXPR_VINSN (expr));
1860 EXPR_VINSN (expr) = NULL;
1862 free_history_vect (&EXPR_HISTORY_OF_CHANGES (expr));
1865 /* For a given LV_SET, mark EXPR having unavailable target register. */
1867 set_unavailable_target_for_expr (expr_t expr, regset lv_set)
1869 if (EXPR_SEPARABLE_P (expr))
1871 if (REG_P (EXPR_LHS (expr))
1872 && bitmap_bit_p (lv_set, REGNO (EXPR_LHS (expr))))
1874 /* If it's an insn like r1 = use (r1, ...), and it exists in
1875 different forms in each of the av_sets being merged, we can't say
1876 whether original destination register is available or not.
1877 However, this still works if destination register is not used
1878 in the original expression: if the branch at which LV_SET we're
1879 looking here is not actually 'other branch' in sense that same
1880 expression is available through it (but it can't be determined
1881 at computation stage because of transformations on one of the
1882 branches), it still won't affect the availability.
1883 Liveness of a register somewhere on a code motion path means
1884 it's either read somewhere on a codemotion path, live on
1885 'other' branch, live at the point immediately following
1886 the original operation, or is read by the original operation.
1887 The latter case is filtered out in the condition below.
1888 It still doesn't cover the case when register is defined and used
1889 somewhere within the code motion path, and in this case we could
1890 miss a unifying code motion along both branches using a renamed
1891 register, but it won't affect a code correctness since upon
1892 an actual code motion a bookkeeping code would be generated. */
1893 if (bitmap_bit_p (VINSN_REG_USES (EXPR_VINSN (expr)),
1894 REGNO (EXPR_LHS (expr))))
1895 EXPR_TARGET_AVAILABLE (expr) = -1;
1897 EXPR_TARGET_AVAILABLE (expr) = false;
1903 reg_set_iterator rsi;
1905 EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_SETS (EXPR_VINSN (expr)),
1907 if (bitmap_bit_p (lv_set, regno))
1909 EXPR_TARGET_AVAILABLE (expr) = false;
1913 EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_CLOBBERS (EXPR_VINSN (expr)),
1915 if (bitmap_bit_p (lv_set, regno))
1917 EXPR_TARGET_AVAILABLE (expr) = false;
1923 /* Try to make EXPR speculative. Return 1 when EXPR's pattern
1924 or dependence status have changed, 2 when also the target register
1925 became unavailable, 0 if nothing had to be changed. */
1927 speculate_expr (expr_t expr, ds_t ds)
1932 ds_t target_ds, current_ds;
1934 /* Obtain the status we need to put on EXPR. */
1935 target_ds = (ds & SPECULATIVE);
1936 current_ds = EXPR_SPEC_DONE_DS (expr);
1937 ds = ds_full_merge (current_ds, target_ds, NULL_RTX, NULL_RTX);
1939 orig_insn_rtx = EXPR_INSN_RTX (expr);
1941 res = sched_speculate_insn (orig_insn_rtx, ds, &spec_pat);
1946 EXPR_SPEC_DONE_DS (expr) = ds;
1947 return current_ds != ds ? 1 : 0;
1951 rtx spec_insn_rtx = create_insn_rtx_from_pattern (spec_pat, NULL_RTX);
1952 vinsn_t spec_vinsn = create_vinsn_from_insn_rtx (spec_insn_rtx, false);
1954 change_vinsn_in_expr (expr, spec_vinsn);
1955 EXPR_SPEC_DONE_DS (expr) = ds;
1956 EXPR_NEEDS_SPEC_CHECK_P (expr) = true;
1958 /* Do not allow clobbering the address register of speculative
1960 if (bitmap_bit_p (VINSN_REG_USES (EXPR_VINSN (expr)),
1961 expr_dest_regno (expr)))
1963 EXPR_TARGET_AVAILABLE (expr) = false;
1979 /* Return a destination register, if any, of EXPR. */
1981 expr_dest_reg (expr_t expr)
1983 rtx dest = VINSN_LHS (EXPR_VINSN (expr));
1985 if (dest != NULL_RTX && REG_P (dest))
1991 /* Returns the REGNO of the R's destination. */
1993 expr_dest_regno (expr_t expr)
1995 rtx dest = expr_dest_reg (expr);
1997 gcc_assert (dest != NULL_RTX);
1998 return REGNO (dest);
2001 /* For a given LV_SET, mark all expressions in JOIN_SET, but not present in
2002 AV_SET having unavailable target register. */
2004 mark_unavailable_targets (av_set_t join_set, av_set_t av_set, regset lv_set)
2007 av_set_iterator avi;
2009 FOR_EACH_EXPR (expr, avi, join_set)
2010 if (av_set_lookup (av_set, EXPR_VINSN (expr)) == NULL)
2011 set_unavailable_target_for_expr (expr, lv_set);
2015 /* Av set functions. */
2017 /* Add a new element to av set SETP.
2018 Return the element added. */
2020 av_set_add_element (av_set_t *setp)
2022 /* Insert at the beginning of the list. */
2027 /* Add EXPR to SETP. */
2029 av_set_add (av_set_t *setp, expr_t expr)
2033 gcc_assert (!INSN_NOP_P (EXPR_INSN_RTX (expr)));
2034 elem = av_set_add_element (setp);
2035 copy_expr (_AV_SET_EXPR (elem), expr);
2038 /* Same, but do not copy EXPR. */
2040 av_set_add_nocopy (av_set_t *setp, expr_t expr)
2044 elem = av_set_add_element (setp);
2045 *_AV_SET_EXPR (elem) = *expr;
2048 /* Remove expr pointed to by IP from the av_set. */
2050 av_set_iter_remove (av_set_iterator *ip)
2052 clear_expr (_AV_SET_EXPR (*ip->lp));
2053 _list_iter_remove (ip);
2056 /* Search for an expr in SET, such that it's equivalent to SOUGHT_VINSN in the
2057 sense of vinsn_equal_p function. Return NULL if no such expr is
2058 in SET was found. */
2060 av_set_lookup (av_set_t set, vinsn_t sought_vinsn)
2065 FOR_EACH_EXPR (expr, i, set)
2066 if (vinsn_equal_p (EXPR_VINSN (expr), sought_vinsn))
2071 /* Same, but also remove the EXPR found. */
2073 av_set_lookup_and_remove (av_set_t *setp, vinsn_t sought_vinsn)
2078 FOR_EACH_EXPR_1 (expr, i, setp)
2079 if (vinsn_equal_p (EXPR_VINSN (expr), sought_vinsn))
2081 _list_iter_remove_nofree (&i);
2087 /* Search for an expr in SET, such that it's equivalent to EXPR in the
2088 sense of vinsn_equal_p function of their vinsns, but not EXPR itself.
2089 Returns NULL if no such expr is in SET was found. */
2091 av_set_lookup_other_equiv_expr (av_set_t set, expr_t expr)
2096 FOR_EACH_EXPR (cur_expr, i, set)
2098 if (cur_expr == expr)
2100 if (vinsn_equal_p (EXPR_VINSN (cur_expr), EXPR_VINSN (expr)))
2107 /* If other expression is already in AVP, remove one of them. */
2109 merge_with_other_exprs (av_set_t *avp, av_set_iterator *ip, expr_t expr)
2113 expr2 = av_set_lookup_other_equiv_expr (*avp, expr);
2116 /* Reset target availability on merge, since taking it only from one
2117 of the exprs would be controversial for different code. */
2118 EXPR_TARGET_AVAILABLE (expr2) = -1;
2119 EXPR_USEFULNESS (expr2) = 0;
2121 merge_expr (expr2, expr, NULL);
2123 /* Fix usefulness as it should be now REG_BR_PROB_BASE. */
2124 EXPR_USEFULNESS (expr2) = REG_BR_PROB_BASE;
2126 av_set_iter_remove (ip);
2133 /* Return true if there is an expr that correlates to VI in SET. */
2135 av_set_is_in_p (av_set_t set, vinsn_t vi)
2137 return av_set_lookup (set, vi) != NULL;
2140 /* Return a copy of SET. */
2142 av_set_copy (av_set_t set)
2146 av_set_t res = NULL;
2148 FOR_EACH_EXPR (expr, i, set)
2149 av_set_add (&res, expr);
2154 /* Join two av sets that do not have common elements by attaching second set
2155 (pointed to by FROMP) to the end of first set (TO_TAILP must point to
2156 _AV_SET_NEXT of first set's last element). */
2158 join_distinct_sets (av_set_t *to_tailp, av_set_t *fromp)
2160 gcc_assert (*to_tailp == NULL);
2165 /* Makes set pointed to by TO to be the union of TO and FROM. Clear av_set
2166 pointed to by FROMP afterwards. */
2168 av_set_union_and_clear (av_set_t *top, av_set_t *fromp, insn_t insn)
2173 /* Delete from TOP all exprs, that present in FROMP. */
2174 FOR_EACH_EXPR_1 (expr1, i, top)
2176 expr_t expr2 = av_set_lookup (*fromp, EXPR_VINSN (expr1));
2180 merge_expr (expr2, expr1, insn);
2181 av_set_iter_remove (&i);
2185 join_distinct_sets (i.lp, fromp);
2188 /* Same as above, but also update availability of target register in
2189 TOP judging by TO_LV_SET and FROM_LV_SET. */
2191 av_set_union_and_live (av_set_t *top, av_set_t *fromp, regset to_lv_set,
2192 regset from_lv_set, insn_t insn)
2196 av_set_t *to_tailp, in_both_set = NULL;
2198 /* Delete from TOP all expres, that present in FROMP. */
2199 FOR_EACH_EXPR_1 (expr1, i, top)
2201 expr_t expr2 = av_set_lookup_and_remove (fromp, EXPR_VINSN (expr1));
2205 /* It may be that the expressions have different destination
2206 registers, in which case we need to check liveness here. */
2207 if (EXPR_SEPARABLE_P (expr1))
2209 int regno1 = (REG_P (EXPR_LHS (expr1))
2210 ? (int) expr_dest_regno (expr1) : -1);
2211 int regno2 = (REG_P (EXPR_LHS (expr2))
2212 ? (int) expr_dest_regno (expr2) : -1);
2214 /* ??? We don't have a way to check restrictions for
2215 *other* register on the current path, we did it only
2216 for the current target register. Give up. */
2217 if (regno1 != regno2)
2218 EXPR_TARGET_AVAILABLE (expr2) = -1;
2220 else if (EXPR_INSN_RTX (expr1) != EXPR_INSN_RTX (expr2))
2221 EXPR_TARGET_AVAILABLE (expr2) = -1;
2223 merge_expr (expr2, expr1, insn);
2224 av_set_add_nocopy (&in_both_set, expr2);
2225 av_set_iter_remove (&i);
2228 /* EXPR1 is present in TOP, but not in FROMP. Check it on
2230 set_unavailable_target_for_expr (expr1, from_lv_set);
2234 /* These expressions are not present in TOP. Check liveness
2235 restrictions on TO_LV_SET. */
2236 FOR_EACH_EXPR (expr1, i, *fromp)
2237 set_unavailable_target_for_expr (expr1, to_lv_set);
2239 join_distinct_sets (i.lp, &in_both_set);
2240 join_distinct_sets (to_tailp, fromp);
2243 /* Clear av_set pointed to by SETP. */
2245 av_set_clear (av_set_t *setp)
2250 FOR_EACH_EXPR_1 (expr, i, setp)
2251 av_set_iter_remove (&i);
2253 gcc_assert (*setp == NULL);
2256 /* Leave only one non-speculative element in the SETP. */
2258 av_set_leave_one_nonspec (av_set_t *setp)
2262 bool has_one_nonspec = false;
2264 /* Keep all speculative exprs, and leave one non-speculative
2266 FOR_EACH_EXPR_1 (expr, i, setp)
2268 if (!EXPR_SPEC_DONE_DS (expr))
2270 if (has_one_nonspec)
2271 av_set_iter_remove (&i);
2273 has_one_nonspec = true;
2278 /* Return the N'th element of the SET. */
2280 av_set_element (av_set_t set, int n)
2285 FOR_EACH_EXPR (expr, i, set)
2293 /* Deletes all expressions from AVP that are conditional branches (IFs). */
2295 av_set_substract_cond_branches (av_set_t *avp)
2300 FOR_EACH_EXPR_1 (expr, i, avp)
2301 if (vinsn_cond_branch_p (EXPR_VINSN (expr)))
2302 av_set_iter_remove (&i);
2305 /* Multiplies usefulness attribute of each member of av-set *AVP by
2306 value PROB / ALL_PROB. */
2308 av_set_split_usefulness (av_set_t av, int prob, int all_prob)
2313 FOR_EACH_EXPR (expr, i, av)
2314 EXPR_USEFULNESS (expr) = (all_prob
2315 ? (EXPR_USEFULNESS (expr) * prob) / all_prob
2319 /* Leave in AVP only those expressions, which are present in AV,
2322 av_set_intersect (av_set_t *avp, av_set_t av)
2327 FOR_EACH_EXPR_1 (expr, i, avp)
2328 if (av_set_lookup (av, EXPR_VINSN (expr)) == NULL)
2329 av_set_iter_remove (&i);
2334 /* Dependence hooks to initialize insn data. */
2336 /* This is used in hooks callable from dependence analysis when initializing
2337 instruction's data. */
2340 /* Where the dependence was found (lhs/rhs). */
2343 /* The actual data object to initialize. */
2346 /* True when the insn should not be made clonable. */
2347 bool force_unique_p;
2349 /* True when insn should be treated as of type USE, i.e. never renamed. */
2351 } deps_init_id_data;
2354 /* Setup ID for INSN. FORCE_UNIQUE_P is true when INSN should not be
2357 setup_id_for_insn (idata_t id, insn_t insn, bool force_unique_p)
2361 /* Determine whether INSN could be cloned and return appropriate vinsn type.
2362 That clonable insns which can be separated into lhs and rhs have type SET.
2363 Other clonable insns have type USE. */
2364 type = GET_CODE (insn);
2366 /* Only regular insns could be cloned. */
2367 if (type == INSN && !force_unique_p)
2369 else if (type == JUMP_INSN && simplejump_p (insn))
2372 IDATA_TYPE (id) = type;
2373 IDATA_REG_SETS (id) = get_clear_regset_from_pool ();
2374 IDATA_REG_USES (id) = get_clear_regset_from_pool ();
2375 IDATA_REG_CLOBBERS (id) = get_clear_regset_from_pool ();
2378 /* Start initializing insn data. */
2380 deps_init_id_start_insn (insn_t insn)
2382 gcc_assert (deps_init_id_data.where == DEPS_IN_NOWHERE);
2384 setup_id_for_insn (deps_init_id_data.id, insn,
2385 deps_init_id_data.force_unique_p);
2386 deps_init_id_data.where = DEPS_IN_INSN;
2389 /* Start initializing lhs data. */
2391 deps_init_id_start_lhs (rtx lhs)
2393 gcc_assert (deps_init_id_data.where == DEPS_IN_INSN);
2394 gcc_assert (IDATA_LHS (deps_init_id_data.id) == NULL);
2396 if (IDATA_TYPE (deps_init_id_data.id) == SET)
2398 IDATA_LHS (deps_init_id_data.id) = lhs;
2399 deps_init_id_data.where = DEPS_IN_LHS;
2403 /* Finish initializing lhs data. */
2405 deps_init_id_finish_lhs (void)
2407 deps_init_id_data.where = DEPS_IN_INSN;
2410 /* Note a set of REGNO. */
2412 deps_init_id_note_reg_set (int regno)
2414 haifa_note_reg_set (regno);
2416 if (deps_init_id_data.where == DEPS_IN_RHS)
2417 deps_init_id_data.force_use_p = true;
2419 if (IDATA_TYPE (deps_init_id_data.id) != PC)
2420 SET_REGNO_REG_SET (IDATA_REG_SETS (deps_init_id_data.id), regno);
2423 /* Make instructions that set stack registers to be ineligible for
2424 renaming to avoid issues with find_used_regs. */
2425 if (IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG))
2426 deps_init_id_data.force_use_p = true;
2430 /* Note a clobber of REGNO. */
2432 deps_init_id_note_reg_clobber (int regno)
2434 haifa_note_reg_clobber (regno);
2436 if (deps_init_id_data.where == DEPS_IN_RHS)
2437 deps_init_id_data.force_use_p = true;
2439 if (IDATA_TYPE (deps_init_id_data.id) != PC)
2440 SET_REGNO_REG_SET (IDATA_REG_CLOBBERS (deps_init_id_data.id), regno);
2443 /* Note a use of REGNO. */
2445 deps_init_id_note_reg_use (int regno)
2447 haifa_note_reg_use (regno);
2449 if (IDATA_TYPE (deps_init_id_data.id) != PC)
2450 SET_REGNO_REG_SET (IDATA_REG_USES (deps_init_id_data.id), regno);
2453 /* Start initializing rhs data. */
2455 deps_init_id_start_rhs (rtx rhs)
2457 gcc_assert (deps_init_id_data.where == DEPS_IN_INSN);
2459 /* And there was no sel_deps_reset_to_insn (). */
2460 if (IDATA_LHS (deps_init_id_data.id) != NULL)
2462 IDATA_RHS (deps_init_id_data.id) = rhs;
2463 deps_init_id_data.where = DEPS_IN_RHS;
2467 /* Finish initializing rhs data. */
2469 deps_init_id_finish_rhs (void)
2471 gcc_assert (deps_init_id_data.where == DEPS_IN_RHS
2472 || deps_init_id_data.where == DEPS_IN_INSN);
2473 deps_init_id_data.where = DEPS_IN_INSN;
2476 /* Finish initializing insn data. */
2478 deps_init_id_finish_insn (void)
2480 gcc_assert (deps_init_id_data.where == DEPS_IN_INSN);
2482 if (IDATA_TYPE (deps_init_id_data.id) == SET)
2484 rtx lhs = IDATA_LHS (deps_init_id_data.id);
2485 rtx rhs = IDATA_RHS (deps_init_id_data.id);
2487 if (lhs == NULL || rhs == NULL || !lhs_and_rhs_separable_p (lhs, rhs)
2488 || deps_init_id_data.force_use_p)
2490 /* This should be a USE, as we don't want to schedule its RHS
2491 separately. However, we still want to have them recorded
2492 for the purposes of substitution. That's why we don't
2493 simply call downgrade_to_use () here. */
2494 gcc_assert (IDATA_TYPE (deps_init_id_data.id) == SET);
2495 gcc_assert (!lhs == !rhs);
2497 IDATA_TYPE (deps_init_id_data.id) = USE;
2501 deps_init_id_data.where = DEPS_IN_NOWHERE;
2504 /* This is dependence info used for initializing insn's data. */
2505 static struct sched_deps_info_def deps_init_id_sched_deps_info;
2507 /* This initializes most of the static part of the above structure. */
2508 static const struct sched_deps_info_def const_deps_init_id_sched_deps_info =
2512 deps_init_id_start_insn,
2513 deps_init_id_finish_insn,
2514 deps_init_id_start_lhs,
2515 deps_init_id_finish_lhs,
2516 deps_init_id_start_rhs,
2517 deps_init_id_finish_rhs,
2518 deps_init_id_note_reg_set,
2519 deps_init_id_note_reg_clobber,
2520 deps_init_id_note_reg_use,
2521 NULL, /* note_mem_dep */
2522 NULL, /* note_dep */
2525 0, /* use_deps_list */
2526 0 /* generate_spec_deps */
2529 /* Initialize INSN's lhs and rhs in ID. When FORCE_UNIQUE_P is true,
2530 we don't actually need information about lhs and rhs. */
2532 setup_id_lhs_rhs (idata_t id, insn_t insn, bool force_unique_p)
2534 rtx pat = PATTERN (insn);
2536 if (GET_CODE (insn) == INSN
2537 && GET_CODE (pat) == SET
2540 IDATA_RHS (id) = SET_SRC (pat);
2541 IDATA_LHS (id) = SET_DEST (pat);
2544 IDATA_LHS (id) = IDATA_RHS (id) = NULL;
2547 /* Possibly downgrade INSN to USE. */
2549 maybe_downgrade_id_to_use (idata_t id, insn_t insn)
2551 bool must_be_use = false;
2552 unsigned uid = INSN_UID (insn);
2553 struct df_ref **rec;
2554 rtx lhs = IDATA_LHS (id);
2555 rtx rhs = IDATA_RHS (id);
2557 /* We downgrade only SETs. */
2558 if (IDATA_TYPE (id) != SET)
2561 if (!lhs || !lhs_and_rhs_separable_p (lhs, rhs))
2563 IDATA_TYPE (id) = USE;
2567 for (rec = DF_INSN_UID_DEFS (uid); *rec; rec++)
2569 struct df_ref *def = *rec;
2571 if (DF_REF_INSN (def)
2572 && DF_REF_FLAGS_IS_SET (def, DF_REF_PRE_POST_MODIFY)
2573 && loc_mentioned_in_p (DF_REF_LOC (def), IDATA_RHS (id)))
2580 /* Make instructions that set stack registers to be ineligible for
2581 renaming to avoid issues with find_used_regs. */
2582 if (IN_RANGE (DF_REF_REGNO (def), FIRST_STACK_REG, LAST_STACK_REG))
2591 IDATA_TYPE (id) = USE;
2594 /* Setup register sets describing INSN in ID. */
2596 setup_id_reg_sets (idata_t id, insn_t insn)
2598 unsigned uid = INSN_UID (insn);
2599 struct df_ref **rec;
2600 regset tmp = get_clear_regset_from_pool ();
2602 for (rec = DF_INSN_UID_DEFS (uid); *rec; rec++)
2604 struct df_ref *def = *rec;
2605 unsigned int regno = DF_REF_REGNO (def);
2607 /* Post modifies are treated like clobbers by sched-deps.c. */
2608 if (DF_REF_FLAGS_IS_SET (def, (DF_REF_MUST_CLOBBER
2609 | DF_REF_PRE_POST_MODIFY)))
2610 SET_REGNO_REG_SET (IDATA_REG_CLOBBERS (id), regno);
2611 else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
2613 SET_REGNO_REG_SET (IDATA_REG_SETS (id), regno);
2616 /* For stack registers, treat writes to them as writes
2617 to the first one to be consistent with sched-deps.c. */
2618 if (IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG))
2619 SET_REGNO_REG_SET (IDATA_REG_SETS (id), FIRST_STACK_REG);
2622 /* Mark special refs that generate read/write def pair. */
2623 if (DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL)
2624 || regno == STACK_POINTER_REGNUM)
2625 bitmap_set_bit (tmp, regno);
2628 for (rec = DF_INSN_UID_USES (uid); *rec; rec++)
2630 struct df_ref *use = *rec;
2631 unsigned int regno = DF_REF_REGNO (use);
2633 /* When these refs are met for the first time, skip them, as
2634 these uses are just counterparts of some defs. */
2635 if (bitmap_bit_p (tmp, regno))
2636 bitmap_clear_bit (tmp, regno);
2637 else if (! DF_REF_FLAGS_IS_SET (use, DF_REF_CALL_STACK_USAGE))
2639 SET_REGNO_REG_SET (IDATA_REG_USES (id), regno);
2642 /* For stack registers, treat reads from them as reads from
2643 the first one to be consistent with sched-deps.c. */
2644 if (IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG))
2645 SET_REGNO_REG_SET (IDATA_REG_USES (id), FIRST_STACK_REG);
2650 return_regset_to_pool (tmp);
2653 /* Initialize instruction data for INSN in ID using DF's data. */
2655 init_id_from_df (idata_t id, insn_t insn, bool force_unique_p)
2657 gcc_assert (DF_INSN_UID_SAFE_GET (INSN_UID (insn)) != NULL);
2659 setup_id_for_insn (id, insn, force_unique_p);
2660 setup_id_lhs_rhs (id, insn, force_unique_p);
2662 if (INSN_NOP_P (insn))
2665 maybe_downgrade_id_to_use (id, insn);
2666 setup_id_reg_sets (id, insn);
2669 /* Initialize instruction data for INSN in ID. */
2671 deps_init_id (idata_t id, insn_t insn, bool force_unique_p)
2673 struct deps _dc, *dc = &_dc;
2675 deps_init_id_data.where = DEPS_IN_NOWHERE;
2676 deps_init_id_data.id = id;
2677 deps_init_id_data.force_unique_p = force_unique_p;
2678 deps_init_id_data.force_use_p = false;
2682 memcpy (&deps_init_id_sched_deps_info,
2683 &const_deps_init_id_sched_deps_info,
2684 sizeof (deps_init_id_sched_deps_info));
2686 if (spec_info != NULL)
2687 deps_init_id_sched_deps_info.generate_spec_deps = 1;
2689 sched_deps_info = &deps_init_id_sched_deps_info;
2691 deps_analyze_insn (dc, insn);
2695 deps_init_id_data.id = NULL;
2700 /* Implement hooks for collecting fundamental insn properties like if insn is
2701 an ASM or is within a SCHED_GROUP. */
2703 /* True when a "one-time init" data for INSN was already inited. */
2705 first_time_insn_init (insn_t insn)
2707 return INSN_LIVE (insn) == NULL;
2710 /* Hash an entry in a transformed_insns hashtable. */
2712 hash_transformed_insns (const void *p)
2714 return VINSN_HASH_RTX (((const struct transformed_insns *) p)->vinsn_old);
2717 /* Compare the entries in a transformed_insns hashtable. */
2719 eq_transformed_insns (const void *p, const void *q)
2721 rtx i1 = VINSN_INSN_RTX (((const struct transformed_insns *) p)->vinsn_old);
2722 rtx i2 = VINSN_INSN_RTX (((const struct transformed_insns *) q)->vinsn_old);
2724 if (INSN_UID (i1) == INSN_UID (i2))
2726 return rtx_equal_p (PATTERN (i1), PATTERN (i2));
2729 /* Free an entry in a transformed_insns hashtable. */
2731 free_transformed_insns (void *p)
2733 struct transformed_insns *pti = (struct transformed_insns *) p;
2735 vinsn_detach (pti->vinsn_old);
2736 vinsn_detach (pti->vinsn_new);
2740 /* Init the s_i_d data for INSN which should be inited just once, when
2741 we first see the insn. */
2743 init_first_time_insn_data (insn_t insn)
2745 /* This should not be set if this is the first time we init data for
2747 gcc_assert (first_time_insn_init (insn));
2749 /* These are needed for nops too. */
2750 INSN_LIVE (insn) = get_regset_from_pool ();
2751 INSN_LIVE_VALID_P (insn) = false;
2753 if (!INSN_NOP_P (insn))
2755 INSN_ANALYZED_DEPS (insn) = BITMAP_ALLOC (NULL);
2756 INSN_FOUND_DEPS (insn) = BITMAP_ALLOC (NULL);
2757 INSN_TRANSFORMED_INSNS (insn)
2758 = htab_create (16, hash_transformed_insns,
2759 eq_transformed_insns, free_transformed_insns);
2760 init_deps (&INSN_DEPS_CONTEXT (insn));
2764 /* Free the same data as above for INSN. */
2766 free_first_time_insn_data (insn_t insn)
2768 gcc_assert (! first_time_insn_init (insn));
2770 BITMAP_FREE (INSN_ANALYZED_DEPS (insn));
2771 BITMAP_FREE (INSN_FOUND_DEPS (insn));
2772 htab_delete (INSN_TRANSFORMED_INSNS (insn));
2773 return_regset_to_pool (INSN_LIVE (insn));
2774 INSN_LIVE (insn) = NULL;
2775 INSN_LIVE_VALID_P (insn) = false;
2777 /* This is allocated only for bookkeeping insns. */
2778 if (INSN_ORIGINATORS (insn))
2779 BITMAP_FREE (INSN_ORIGINATORS (insn));
2780 free_deps (&INSN_DEPS_CONTEXT (insn));
2783 /* Initialize region-scope data structures for basic blocks. */
2785 init_global_and_expr_for_bb (basic_block bb)
2787 if (sel_bb_empty_p (bb))
2790 invalidate_av_set (bb);
2793 /* Data for global dependency analysis (to initialize CANT_MOVE and
2797 /* Previous insn. */
2801 /* Determine if INSN is in the sched_group, is an asm or should not be
2802 cloned. After that initialize its expr. */
2804 init_global_and_expr_for_insn (insn_t insn)
2809 if (NOTE_INSN_BASIC_BLOCK_P (insn))
2811 init_global_data.prev_insn = NULL_RTX;
2815 gcc_assert (INSN_P (insn));
2817 if (SCHED_GROUP_P (insn))
2818 /* Setup a sched_group. */
2820 insn_t prev_insn = init_global_data.prev_insn;
2823 INSN_SCHED_NEXT (prev_insn) = insn;
2825 init_global_data.prev_insn = insn;
2828 init_global_data.prev_insn = NULL_RTX;
2830 if (GET_CODE (PATTERN (insn)) == ASM_INPUT
2831 || asm_noperands (PATTERN (insn)) >= 0)
2832 /* Mark INSN as an asm. */
2833 INSN_ASM_P (insn) = true;
2836 bool force_unique_p;
2839 /* Certain instructions cannot be cloned. */
2840 if (CANT_MOVE (insn)
2841 || INSN_ASM_P (insn)
2842 || SCHED_GROUP_P (insn)
2843 || prologue_epilogue_contains (insn)
2844 /* Exception handling insns are always unique. */
2845 || (flag_non_call_exceptions && can_throw_internal (insn))
2846 /* TRAP_IF though have an INSN code is control_flow_insn_p (). */
2847 || control_flow_insn_p (insn))
2848 force_unique_p = true;
2850 force_unique_p = false;
2852 if (targetm.sched.get_insn_spec_ds)
2854 spec_done_ds = targetm.sched.get_insn_spec_ds (insn);
2855 spec_done_ds = ds_get_max_dep_weak (spec_done_ds);
2860 /* Initialize INSN's expr. */
2861 init_expr (INSN_EXPR (insn), vinsn_create (insn, force_unique_p), 0,
2862 REG_BR_PROB_BASE, INSN_PRIORITY (insn), 0, BLOCK_NUM (insn),
2863 spec_done_ds, 0, 0, NULL, true, false, false, false,
2867 init_first_time_insn_data (insn);
2870 /* Scan the region and initialize instruction data for basic blocks BBS. */
2872 sel_init_global_and_expr (bb_vec_t bbs)
2874 /* ??? It would be nice to implement push / pop scheme for sched_infos. */
2875 const struct sched_scan_info_def ssi =
2877 NULL, /* extend_bb */
2878 init_global_and_expr_for_bb, /* init_bb */
2879 extend_insn_data, /* extend_insn */
2880 init_global_and_expr_for_insn /* init_insn */
2883 sched_scan (&ssi, bbs, NULL, NULL, NULL);
2886 /* Finalize region-scope data structures for basic blocks. */
2888 finish_global_and_expr_for_bb (basic_block bb)
2890 av_set_clear (&BB_AV_SET (bb));
2891 BB_AV_LEVEL (bb) = 0;
2894 /* Finalize INSN's data. */
2896 finish_global_and_expr_insn (insn_t insn)
2898 if (LABEL_P (insn) || NOTE_INSN_BASIC_BLOCK_P (insn))
2901 gcc_assert (INSN_P (insn));
2903 if (INSN_LUID (insn) > 0)
2905 free_first_time_insn_data (insn);
2906 INSN_WS_LEVEL (insn) = 0;
2907 CANT_MOVE (insn) = 0;
2909 /* We can no longer assert this, as vinsns of this insn could be
2910 easily live in other insn's caches. This should be changed to
2911 a counter-like approach among all vinsns. */
2912 gcc_assert (true || VINSN_COUNT (INSN_VINSN (insn)) == 1);
2913 clear_expr (INSN_EXPR (insn));
2917 /* Finalize per instruction data for the whole region. */
2919 sel_finish_global_and_expr (void)
2925 bbs = VEC_alloc (basic_block, heap, current_nr_blocks);
2927 for (i = 0; i < current_nr_blocks; i++)
2928 VEC_quick_push (basic_block, bbs, BASIC_BLOCK (BB_TO_BLOCK (i)));
2930 /* Clear AV_SETs and INSN_EXPRs. */
2932 const struct sched_scan_info_def ssi =
2934 NULL, /* extend_bb */
2935 finish_global_and_expr_for_bb, /* init_bb */
2936 NULL, /* extend_insn */
2937 finish_global_and_expr_insn /* init_insn */
2940 sched_scan (&ssi, bbs, NULL, NULL, NULL);
2943 VEC_free (basic_block, heap, bbs);
2950 /* In the below hooks, we merely calculate whether or not a dependence
2951 exists, and in what part of insn. However, we will need more data
2952 when we'll start caching dependence requests. */
2954 /* Container to hold information for dependency analysis. */
2959 /* A variable to track which part of rtx we are scanning in
2960 sched-deps.c: sched_analyze_insn (). */
2963 /* Current producer. */
2966 /* Current consumer. */
2969 /* Is SEL_DEPS_HAS_DEP_P[DEPS_IN_X] is true, then X has a dependence.
2970 X is from { INSN, LHS, RHS }. */
2971 ds_t has_dep_p[DEPS_IN_NOWHERE];
2972 } has_dependence_data;
2974 /* Start analyzing dependencies of INSN. */
2976 has_dependence_start_insn (insn_t insn ATTRIBUTE_UNUSED)
2978 gcc_assert (has_dependence_data.where == DEPS_IN_NOWHERE);
2980 has_dependence_data.where = DEPS_IN_INSN;
2983 /* Finish analyzing dependencies of an insn. */
2985 has_dependence_finish_insn (void)
2987 gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
2989 has_dependence_data.where = DEPS_IN_NOWHERE;
2992 /* Start analyzing dependencies of LHS. */
2994 has_dependence_start_lhs (rtx lhs ATTRIBUTE_UNUSED)
2996 gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
2998 if (VINSN_LHS (has_dependence_data.con) != NULL)
2999 has_dependence_data.where = DEPS_IN_LHS;
3002 /* Finish analyzing dependencies of an lhs. */
3004 has_dependence_finish_lhs (void)
3006 has_dependence_data.where = DEPS_IN_INSN;
3009 /* Start analyzing dependencies of RHS. */
3011 has_dependence_start_rhs (rtx rhs ATTRIBUTE_UNUSED)
3013 gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
3015 if (VINSN_RHS (has_dependence_data.con) != NULL)
3016 has_dependence_data.where = DEPS_IN_RHS;
3019 /* Start analyzing dependencies of an rhs. */
3021 has_dependence_finish_rhs (void)
3023 gcc_assert (has_dependence_data.where == DEPS_IN_RHS
3024 || has_dependence_data.where == DEPS_IN_INSN);
3026 has_dependence_data.where = DEPS_IN_INSN;
3029 /* Note a set of REGNO. */
3031 has_dependence_note_reg_set (int regno)
3033 struct deps_reg *reg_last = &has_dependence_data.dc->reg_last[regno];
3035 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3037 (has_dependence_data.con)))
3039 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3041 if (reg_last->sets != NULL
3042 || reg_last->clobbers != NULL)
3043 *dsp = (*dsp & ~SPECULATIVE) | DEP_OUTPUT;
3046 *dsp = (*dsp & ~SPECULATIVE) | DEP_ANTI;
3050 /* Note a clobber of REGNO. */
3052 has_dependence_note_reg_clobber (int regno)
3054 struct deps_reg *reg_last = &has_dependence_data.dc->reg_last[regno];
3056 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3058 (has_dependence_data.con)))
3060 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3063 *dsp = (*dsp & ~SPECULATIVE) | DEP_OUTPUT;
3066 *dsp = (*dsp & ~SPECULATIVE) | DEP_ANTI;
3070 /* Note a use of REGNO. */
3072 has_dependence_note_reg_use (int regno)
3074 struct deps_reg *reg_last = &has_dependence_data.dc->reg_last[regno];
3076 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3078 (has_dependence_data.con)))
3080 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3083 *dsp = (*dsp & ~SPECULATIVE) | DEP_TRUE;
3085 if (reg_last->clobbers)
3086 *dsp = (*dsp & ~SPECULATIVE) | DEP_ANTI;
3088 /* Handle BE_IN_SPEC. */
3091 ds_t pro_spec_checked_ds;
3093 pro_spec_checked_ds = INSN_SPEC_CHECKED_DS (has_dependence_data.pro);
3094 pro_spec_checked_ds = ds_get_max_dep_weak (pro_spec_checked_ds);
3096 if (pro_spec_checked_ds != 0)
3097 /* Merge BE_IN_SPEC bits into *DSP. */
3098 *dsp = ds_full_merge (*dsp, pro_spec_checked_ds,
3099 NULL_RTX, NULL_RTX);
3104 /* Note a memory dependence. */
3106 has_dependence_note_mem_dep (rtx mem ATTRIBUTE_UNUSED,
3107 rtx pending_mem ATTRIBUTE_UNUSED,
3108 insn_t pending_insn ATTRIBUTE_UNUSED,
3109 ds_t ds ATTRIBUTE_UNUSED)
3111 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3112 VINSN_INSN_RTX (has_dependence_data.con)))
3114 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3116 *dsp = ds_full_merge (ds, *dsp, pending_mem, mem);
3120 /* Note a dependence. */
3122 has_dependence_note_dep (insn_t pro ATTRIBUTE_UNUSED,
3123 ds_t ds ATTRIBUTE_UNUSED)
3125 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3126 VINSN_INSN_RTX (has_dependence_data.con)))
3128 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3130 *dsp = ds_full_merge (ds, *dsp, NULL_RTX, NULL_RTX);
3134 /* Mark the insn as having a hard dependence that prevents speculation. */
3136 sel_mark_hard_insn (rtx insn)
3140 /* Only work when we're in has_dependence_p mode.
3141 ??? This is a hack, this should actually be a hook. */
3142 if (!has_dependence_data.dc || !has_dependence_data.pro)
3145 gcc_assert (insn == VINSN_INSN_RTX (has_dependence_data.con));
3146 gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
3148 for (i = 0; i < DEPS_IN_NOWHERE; i++)
3149 has_dependence_data.has_dep_p[i] &= ~SPECULATIVE;
3152 /* This structure holds the hooks for the dependency analysis used when
3153 actually processing dependencies in the scheduler. */
3154 static struct sched_deps_info_def has_dependence_sched_deps_info;
3156 /* This initializes most of the fields of the above structure. */
3157 static const struct sched_deps_info_def const_has_dependence_sched_deps_info =
3161 has_dependence_start_insn,
3162 has_dependence_finish_insn,
3163 has_dependence_start_lhs,
3164 has_dependence_finish_lhs,
3165 has_dependence_start_rhs,
3166 has_dependence_finish_rhs,
3167 has_dependence_note_reg_set,
3168 has_dependence_note_reg_clobber,
3169 has_dependence_note_reg_use,
3170 has_dependence_note_mem_dep,
3171 has_dependence_note_dep,
3174 0, /* use_deps_list */
3175 0 /* generate_spec_deps */
3178 /* Initialize has_dependence_sched_deps_info with extra spec field. */
3180 setup_has_dependence_sched_deps_info (void)
3182 memcpy (&has_dependence_sched_deps_info,
3183 &const_has_dependence_sched_deps_info,
3184 sizeof (has_dependence_sched_deps_info));
3186 if (spec_info != NULL)
3187 has_dependence_sched_deps_info.generate_spec_deps = 1;
3189 sched_deps_info = &has_dependence_sched_deps_info;
3192 /* Remove all dependences found and recorded in has_dependence_data array. */
3194 sel_clear_has_dependence (void)
3198 for (i = 0; i < DEPS_IN_NOWHERE; i++)
3199 has_dependence_data.has_dep_p[i] = 0;
3202 /* Return nonzero if EXPR has is dependent upon PRED. Return the pointer
3203 to the dependence information array in HAS_DEP_PP. */
3205 has_dependence_p (expr_t expr, insn_t pred, ds_t **has_dep_pp)
3211 if (INSN_SIMPLEJUMP_P (pred))
3212 /* Unconditional jump is just a transfer of control flow.
3216 dc = &INSN_DEPS_CONTEXT (pred);
3219 has_dependence_data.pro = NULL;
3220 /* Initialize empty dep context with information about PRED. */
3221 advance_deps_context (dc, pred);
3225 has_dependence_data.where = DEPS_IN_NOWHERE;
3226 has_dependence_data.pro = pred;
3227 has_dependence_data.con = EXPR_VINSN (expr);
3228 has_dependence_data.dc = dc;
3230 sel_clear_has_dependence ();
3232 /* Now catch all dependencies that would be generated between PRED and
3234 setup_has_dependence_sched_deps_info ();
3235 deps_analyze_insn (dc, EXPR_INSN_RTX (expr));
3236 has_dependence_data.dc = NULL;
3238 /* When a barrier was found, set DEPS_IN_INSN bits. */
3239 if (dc->last_reg_pending_barrier == TRUE_BARRIER)
3240 has_dependence_data.has_dep_p[DEPS_IN_INSN] = DEP_TRUE;
3241 else if (dc->last_reg_pending_barrier == MOVE_BARRIER)
3242 has_dependence_data.has_dep_p[DEPS_IN_INSN] = DEP_ANTI;
3244 /* Do not allow stores to memory to move through checks. Currently
3245 we don't move this to sched-deps.c as the check doesn't have
3246 obvious places to which this dependence can be attached.
3247 FIMXE: this should go to a hook. */
3249 && MEM_P (EXPR_LHS (expr))
3250 && sel_insn_is_speculation_check (pred))
3251 has_dependence_data.has_dep_p[DEPS_IN_INSN] = DEP_ANTI;
3253 *has_dep_pp = has_dependence_data.has_dep_p;
3255 for (i = 0; i < DEPS_IN_NOWHERE; i++)
3256 ds = ds_full_merge (ds, has_dependence_data.has_dep_p[i],
3257 NULL_RTX, NULL_RTX);
3263 /* Dependence hooks implementation that checks dependence latency constraints
3264 on the insns being scheduled. The entry point for these routines is
3265 tick_check_p predicate. */
3269 /* An expr we are currently checking. */
3272 /* A minimal cycle for its scheduling. */
3275 /* Whether we have seen a true dependence while checking. */
3276 bool seen_true_dep_p;
3279 /* Update minimal scheduling cycle for tick_check_insn given that it depends
3280 on PRO with status DS and weight DW. */
3282 tick_check_dep_with_dw (insn_t pro_insn, ds_t ds, dw_t dw)
3284 expr_t con_expr = tick_check_data.expr;
3285 insn_t con_insn = EXPR_INSN_RTX (con_expr);
3287 if (con_insn != pro_insn)
3292 if (/* PROducer was removed from above due to pipelining. */
3293 !INSN_IN_STREAM_P (pro_insn)
3294 /* Or PROducer was originally on the next iteration regarding the
3296 || (INSN_SCHED_TIMES (pro_insn)
3297 - EXPR_SCHED_TIMES (con_expr)) > 1)
3298 /* Don't count this dependence. */
3302 if (dt == REG_DEP_TRUE)
3303 tick_check_data.seen_true_dep_p = true;
3305 gcc_assert (INSN_SCHED_CYCLE (pro_insn) > 0);
3308 dep_def _dep, *dep = &_dep;
3310 init_dep (dep, pro_insn, con_insn, dt);
3312 tick = INSN_SCHED_CYCLE (pro_insn) + dep_cost_1 (dep, dw);
3315 /* When there are several kinds of dependencies between pro and con,
3316 only REG_DEP_TRUE should be taken into account. */
3317 if (tick > tick_check_data.cycle
3318 && (dt == REG_DEP_TRUE || !tick_check_data.seen_true_dep_p))
3319 tick_check_data.cycle = tick;
3323 /* An implementation of note_dep hook. */
3325 tick_check_note_dep (insn_t pro, ds_t ds)
3327 tick_check_dep_with_dw (pro, ds, 0);
3330 /* An implementation of note_mem_dep hook. */
3332 tick_check_note_mem_dep (rtx mem1, rtx mem2, insn_t pro, ds_t ds)
3336 dw = (ds_to_dt (ds) == REG_DEP_TRUE
3337 ? estimate_dep_weak (mem1, mem2)
3340 tick_check_dep_with_dw (pro, ds, dw);
3343 /* This structure contains hooks for dependence analysis used when determining
3344 whether an insn is ready for scheduling. */
3345 static struct sched_deps_info_def tick_check_sched_deps_info =
3356 haifa_note_reg_clobber,
3358 tick_check_note_mem_dep,
3359 tick_check_note_dep,
3364 /* Estimate number of cycles from the current cycle of FENCE until EXPR can be
3365 scheduled. Return 0 if all data from producers in DC is ready. */
3367 tick_check_p (expr_t expr, deps_t dc, fence_t fence)
3370 /* Initialize variables. */
3371 tick_check_data.expr = expr;
3372 tick_check_data.cycle = 0;
3373 tick_check_data.seen_true_dep_p = false;
3374 sched_deps_info = &tick_check_sched_deps_info;
3376 gcc_assert (!dc->readonly);
3378 deps_analyze_insn (dc, EXPR_INSN_RTX (expr));
3381 cycles_left = tick_check_data.cycle - FENCE_CYCLE (fence);
3383 return cycles_left >= 0 ? cycles_left : 0;
3387 /* Functions to work with insns. */
3389 /* Returns true if LHS of INSN is the same as DEST of an insn
3392 lhs_of_insn_equals_to_dest_p (insn_t insn, rtx dest)
3394 rtx lhs = INSN_LHS (insn);
3396 if (lhs == NULL || dest == NULL)
3399 return rtx_equal_p (lhs, dest);
3402 /* Return s_i_d entry of INSN. Callable from debugger. */
3404 insn_sid (insn_t insn)
3409 /* True when INSN is a speculative check. We can tell this by looking
3410 at the data structures of the selective scheduler, not by examining
3413 sel_insn_is_speculation_check (rtx insn)
3415 return s_i_d && !! INSN_SPEC_CHECKED_DS (insn);
3418 /* Extracts machine mode MODE and destination location DST_LOC
3421 get_dest_and_mode (rtx insn, rtx *dst_loc, enum machine_mode *mode)
3423 rtx pat = PATTERN (insn);
3425 gcc_assert (dst_loc);
3426 gcc_assert (GET_CODE (pat) == SET);
3428 *dst_loc = SET_DEST (pat);
3430 gcc_assert (*dst_loc);
3431 gcc_assert (MEM_P (*dst_loc) || REG_P (*dst_loc));
3434 *mode = GET_MODE (*dst_loc);
3437 /* Returns true when moving through JUMP will result in bookkeeping
3440 bookkeeping_can_be_created_if_moved_through_p (insn_t jump)
3445 FOR_EACH_SUCC (succ, si, jump)
3446 if (sel_num_cfg_preds_gt_1 (succ))
3452 /* Return 'true' if INSN is the only one in its basic block. */
3454 insn_is_the_only_one_in_bb_p (insn_t insn)
3456 return sel_bb_head_p (insn) && sel_bb_end_p (insn);
3459 #ifdef ENABLE_CHECKING
3460 /* Check that the region we're scheduling still has at most one
3463 verify_backedges (void)
3471 for (i = 0; i < current_nr_blocks; i++)
3472 FOR_EACH_EDGE (e, ei, BASIC_BLOCK (BB_TO_BLOCK (i))->succs)
3473 if (in_current_region_p (e->dest)
3474 && BLOCK_TO_BB (e->dest->index) < i)
3477 gcc_assert (n <= 1);
3483 /* Functions to work with control flow. */
3485 /* Tidy the possibly empty block BB. */
3487 maybe_tidy_empty_bb (basic_block bb)
3489 basic_block succ_bb, pred_bb;
3492 /* Keep empty bb only if this block immediately precedes EXIT and
3493 has incoming non-fallthrough edge. Otherwise remove it. */
3494 if (!sel_bb_empty_p (bb)
3495 || (single_succ_p (bb)
3496 && single_succ (bb) == EXIT_BLOCK_PTR
3497 && (!single_pred_p (bb)
3498 || !(single_pred_edge (bb)->flags & EDGE_FALLTHRU))))
3501 free_data_sets (bb);
3503 /* Do not delete BB if it has more than one successor.
3504 That can occur when we moving a jump. */
3505 if (!single_succ_p (bb))
3507 gcc_assert (can_merge_blocks_p (bb->prev_bb, bb));
3508 sel_merge_blocks (bb->prev_bb, bb);
3512 succ_bb = single_succ (bb);
3516 /* Redirect all non-fallthru edges to the next bb. */
3524 FOR_EACH_EDGE (e, ei, bb->preds)
3528 if (!(e->flags & EDGE_FALLTHRU))
3530 sel_redirect_edge_and_branch (e, succ_bb);
3537 /* If it is possible - merge BB with its predecessor. */
3538 if (can_merge_blocks_p (bb->prev_bb, bb))
3539 sel_merge_blocks (bb->prev_bb, bb);
3541 /* Otherwise this is a block without fallthru predecessor.
3544 gcc_assert (pred_bb != NULL);
3546 move_bb_info (pred_bb, bb);
3547 remove_empty_bb (bb, true);
3550 #ifdef ENABLE_CHECKING
3551 verify_backedges ();
3557 /* Tidy the control flow after we have removed original insn from
3558 XBB. Return true if we have removed some blocks. When FULL_TIDYING
3559 is true, also try to optimize control flow on non-empty blocks. */
3561 tidy_control_flow (basic_block xbb, bool full_tidying)
3563 bool changed = true;
3565 /* First check whether XBB is empty. */
3566 changed = maybe_tidy_empty_bb (xbb);
3567 if (changed || !full_tidying)
3570 /* Check if there is a unnecessary jump after insn left. */
3571 if (jump_leads_only_to_bb_p (BB_END (xbb), xbb->next_bb)
3572 && INSN_SCHED_TIMES (BB_END (xbb)) == 0
3573 && !IN_CURRENT_FENCE_P (BB_END (xbb)))
3575 if (sel_remove_insn (BB_END (xbb), false, false))
3577 tidy_fallthru_edge (EDGE_SUCC (xbb, 0));
3580 /* Check if there is an unnecessary jump in previous basic block leading
3581 to next basic block left after removing INSN from stream.
3582 If it is so, remove that jump and redirect edge to current
3583 basic block (where there was INSN before deletion). This way
3584 when NOP will be deleted several instructions later with its
3585 basic block we will not get a jump to next instruction, which
3587 if (sel_bb_head (xbb) == sel_bb_end (xbb)
3588 && !sel_bb_empty_p (xbb)
3589 && INSN_NOP_P (sel_bb_end (xbb))
3590 /* Flow goes fallthru from current block to the next. */
3591 && EDGE_COUNT (xbb->succs) == 1
3592 && (EDGE_SUCC (xbb, 0)->flags & EDGE_FALLTHRU)
3593 /* When successor is an EXIT block, it may not be the next block. */
3594 && single_succ (xbb) != EXIT_BLOCK_PTR
3595 /* And unconditional jump in previous basic block leads to
3596 next basic block of XBB and this jump can be safely removed. */
3597 && in_current_region_p (xbb->prev_bb)
3598 && jump_leads_only_to_bb_p (BB_END (xbb->prev_bb), xbb->next_bb)
3599 && INSN_SCHED_TIMES (BB_END (xbb->prev_bb)) == 0
3600 /* Also this jump is not at the scheduling boundary. */
3601 && !IN_CURRENT_FENCE_P (BB_END (xbb->prev_bb)))
3603 /* Clear data structures of jump - jump itself will be removed
3604 by sel_redirect_edge_and_branch. */
3605 clear_expr (INSN_EXPR (BB_END (xbb->prev_bb)));
3606 sel_redirect_edge_and_branch (EDGE_SUCC (xbb->prev_bb, 0), xbb);
3607 gcc_assert (EDGE_SUCC (xbb->prev_bb, 0)->flags & EDGE_FALLTHRU);
3609 /* It can turn out that after removing unused jump, basic block
3610 that contained that jump, becomes empty too. In such case
3612 if (sel_bb_empty_p (xbb->prev_bb))
3613 changed = maybe_tidy_empty_bb (xbb->prev_bb);
3619 /* Rip-off INSN from the insn stream. When ONLY_DISCONNECT is true,
3620 do not delete insn's data, because it will be later re-emitted.
3621 Return true if we have removed some blocks afterwards. */
3623 sel_remove_insn (insn_t insn, bool only_disconnect, bool full_tidying)
3625 basic_block bb = BLOCK_FOR_INSN (insn);
3627 gcc_assert (INSN_IN_STREAM_P (insn));
3629 if (only_disconnect)
3631 insn_t prev = PREV_INSN (insn);
3632 insn_t next = NEXT_INSN (insn);
3633 basic_block bb = BLOCK_FOR_INSN (insn);
3635 NEXT_INSN (prev) = next;
3636 PREV_INSN (next) = prev;
3638 if (BB_HEAD (bb) == insn)
3640 gcc_assert (BLOCK_FOR_INSN (prev) == bb);
3641 BB_HEAD (bb) = prev;
3643 if (BB_END (bb) == insn)
3649 clear_expr (INSN_EXPR (insn));
3652 /* It is necessary to null this fields before calling add_insn (). */
3653 PREV_INSN (insn) = NULL_RTX;
3654 NEXT_INSN (insn) = NULL_RTX;
3656 return tidy_control_flow (bb, full_tidying);
3659 /* Estimate number of the insns in BB. */
3661 sel_estimate_number_of_insns (basic_block bb)
3664 insn_t insn = NEXT_INSN (BB_HEAD (bb)), next_tail = NEXT_INSN (BB_END (bb));
3666 for (; insn != next_tail; insn = NEXT_INSN (insn))
3673 /* We don't need separate luids for notes or labels. */
3675 sel_luid_for_non_insn (rtx x)
3677 gcc_assert (NOTE_P (x) || LABEL_P (x));
3682 /* Return seqno of the only predecessor of INSN. */
3684 get_seqno_of_a_pred (insn_t insn)
3688 gcc_assert (INSN_SIMPLEJUMP_P (insn));
3690 if (!sel_bb_head_p (insn))
3691 seqno = INSN_SEQNO (PREV_INSN (insn));
3694 basic_block bb = BLOCK_FOR_INSN (insn);
3696 if (single_pred_p (bb)
3697 && !in_current_region_p (single_pred (bb)))
3699 /* We can have preds outside a region when splitting edges
3700 for pipelining of an outer loop. Use succ instead.
3701 There should be only one of them. */
3706 gcc_assert (flag_sel_sched_pipelining_outer_loops
3707 && current_loop_nest);
3708 FOR_EACH_SUCC_1 (succ, si, insn,
3709 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
3715 gcc_assert (succ != NULL);
3716 seqno = INSN_SEQNO (succ);
3723 cfg_preds (BLOCK_FOR_INSN (insn), &preds, &n);
3724 gcc_assert (n == 1);
3726 seqno = INSN_SEQNO (preds[0]);
3735 /* Find the proper seqno for inserting at INSN. */
3737 get_seqno_by_preds (rtx insn)
3739 basic_block bb = BLOCK_FOR_INSN (insn);
3740 rtx tmp = insn, head = BB_HEAD (bb);
3746 return INSN_SEQNO (tmp);
3748 tmp = PREV_INSN (tmp);
3750 cfg_preds (bb, &preds, &n);
3751 for (i = 0, seqno = -1; i < n; i++)
3752 seqno = MAX (seqno, INSN_SEQNO (preds[i]));
3754 gcc_assert (seqno > 0);
3760 /* Extend pass-scope data structures for basic blocks. */
3762 sel_extend_global_bb_info (void)
3764 VEC_safe_grow_cleared (sel_global_bb_info_def, heap, sel_global_bb_info,
3768 /* Extend region-scope data structures for basic blocks. */
3770 extend_region_bb_info (void)
3772 VEC_safe_grow_cleared (sel_region_bb_info_def, heap, sel_region_bb_info,
3776 /* Extend all data structures to fit for all basic blocks. */
3778 extend_bb_info (void)
3780 sel_extend_global_bb_info ();
3781 extend_region_bb_info ();
3784 /* Finalize pass-scope data structures for basic blocks. */
3786 sel_finish_global_bb_info (void)
3788 VEC_free (sel_global_bb_info_def, heap, sel_global_bb_info);
3791 /* Finalize region-scope data structures for basic blocks. */
3793 finish_region_bb_info (void)
3795 VEC_free (sel_region_bb_info_def, heap, sel_region_bb_info);
3799 /* Data for each insn in current region. */
3800 VEC (sel_insn_data_def, heap) *s_i_d = NULL;
3802 /* A vector for the insns we've emitted. */
3803 static insn_vec_t new_insns = NULL;
3805 /* Extend data structures for insns from current region. */
3807 extend_insn_data (void)
3811 sched_extend_target ();
3812 sched_deps_init (false);
3814 /* Extend data structures for insns from current region. */
3815 reserve = (sched_max_luid + 1
3816 - VEC_length (sel_insn_data_def, s_i_d));
3818 && ! VEC_space (sel_insn_data_def, s_i_d, reserve))
3819 VEC_safe_grow_cleared (sel_insn_data_def, heap, s_i_d,
3820 3 * sched_max_luid / 2);
3823 /* Finalize data structures for insns from current region. */
3829 /* Clear here all dependence contexts that may have left from insns that were
3830 removed during the scheduling. */
3831 for (i = 0; i < VEC_length (sel_insn_data_def, s_i_d); i++)
3833 sel_insn_data_def *sid_entry = VEC_index (sel_insn_data_def, s_i_d, i);
3835 if (sid_entry->live)
3836 return_regset_to_pool (sid_entry->live);
3837 if (sid_entry->analyzed_deps)
3839 BITMAP_FREE (sid_entry->analyzed_deps);
3840 BITMAP_FREE (sid_entry->found_deps);
3841 htab_delete (sid_entry->transformed_insns);
3842 free_deps (&sid_entry->deps_context);
3844 if (EXPR_VINSN (&sid_entry->expr))
3846 clear_expr (&sid_entry->expr);
3848 /* Also, clear CANT_MOVE bit here, because we really don't want it
3849 to be passed to the next region. */
3850 CANT_MOVE_BY_LUID (i) = 0;
3854 VEC_free (sel_insn_data_def, heap, s_i_d);
3857 /* A proxy to pass initialization data to init_insn (). */
3858 static sel_insn_data_def _insn_init_ssid;
3859 static sel_insn_data_t insn_init_ssid = &_insn_init_ssid;
3861 /* If true create a new vinsn. Otherwise use the one from EXPR. */
3862 static bool insn_init_create_new_vinsn_p;
3864 /* Set all necessary data for initialization of the new insn[s]. */
3866 set_insn_init (expr_t expr, vinsn_t vi, int seqno)
3868 expr_t x = &insn_init_ssid->expr;
3870 copy_expr_onside (x, expr);
3873 insn_init_create_new_vinsn_p = false;
3874 change_vinsn_in_expr (x, vi);
3877 insn_init_create_new_vinsn_p = true;
3879 insn_init_ssid->seqno = seqno;
3883 /* Init data for INSN. */
3885 init_insn_data (insn_t insn)
3888 sel_insn_data_t ssid = insn_init_ssid;
3890 /* The fields mentioned below are special and hence are not being
3891 propagated to the new insns. */
3892 gcc_assert (!ssid->asm_p && ssid->sched_next == NULL
3893 && !ssid->after_stall_p && ssid->sched_cycle == 0);
3894 gcc_assert (INSN_P (insn) && INSN_LUID (insn) > 0);
3896 expr = INSN_EXPR (insn);
3897 copy_expr (expr, &ssid->expr);
3898 prepare_insn_expr (insn, ssid->seqno);
3900 if (insn_init_create_new_vinsn_p)
3901 change_vinsn_in_expr (expr, vinsn_create (insn, init_insn_force_unique_p));
3903 if (first_time_insn_init (insn))
3904 init_first_time_insn_data (insn);
3907 /* This is used to initialize spurious jumps generated by
3908 sel_redirect_edge (). */
3910 init_simplejump_data (insn_t insn)
3912 init_expr (INSN_EXPR (insn), vinsn_create (insn, false), 0,
3913 REG_BR_PROB_BASE, 0, 0, 0, 0, 0, 0, NULL, true, false, false,
3915 INSN_SEQNO (insn) = get_seqno_of_a_pred (insn);
3916 init_first_time_insn_data (insn);
3919 /* Perform deferred initialization of insns. This is used to process
3920 a new jump that may be created by redirect_edge. */
3922 sel_init_new_insn (insn_t insn, int flags)
3924 /* We create data structures for bb when the first insn is emitted in it. */
3926 && INSN_IN_STREAM_P (insn)
3927 && insn_is_the_only_one_in_bb_p (insn))
3930 create_initial_data_sets (BLOCK_FOR_INSN (insn));
3933 if (flags & INSN_INIT_TODO_LUID)
3934 sched_init_luids (NULL, NULL, NULL, insn);
3936 if (flags & INSN_INIT_TODO_SSID)
3938 extend_insn_data ();
3939 init_insn_data (insn);
3940 clear_expr (&insn_init_ssid->expr);
3943 if (flags & INSN_INIT_TODO_SIMPLEJUMP)
3945 extend_insn_data ();
3946 init_simplejump_data (insn);
3949 gcc_assert (CONTAINING_RGN (BLOCK_NUM (insn))
3950 == CONTAINING_RGN (BB_TO_BLOCK (0)));
3954 /* Functions to init/finish work with lv sets. */
3956 /* Init BB_LV_SET of BB from DF_LR_IN set of BB. */
3958 init_lv_set (basic_block bb)
3960 gcc_assert (!BB_LV_SET_VALID_P (bb));
3962 BB_LV_SET (bb) = get_regset_from_pool ();
3963 COPY_REG_SET (BB_LV_SET (bb), DF_LR_IN (bb));
3964 BB_LV_SET_VALID_P (bb) = true;
3967 /* Copy liveness information to BB from FROM_BB. */
3969 copy_lv_set_from (basic_block bb, basic_block from_bb)
3971 gcc_assert (!BB_LV_SET_VALID_P (bb));
3973 COPY_REG_SET (BB_LV_SET (bb), BB_LV_SET (from_bb));
3974 BB_LV_SET_VALID_P (bb) = true;
3977 /* Initialize lv set of all bb headers. */
3983 /* Initialize of LV sets. */
3987 /* Don't forget EXIT_BLOCK. */
3988 init_lv_set (EXIT_BLOCK_PTR);
3991 /* Release lv set of HEAD. */
3993 free_lv_set (basic_block bb)
3995 gcc_assert (BB_LV_SET (bb) != NULL);
3997 return_regset_to_pool (BB_LV_SET (bb));
3998 BB_LV_SET (bb) = NULL;
3999 BB_LV_SET_VALID_P (bb) = false;
4002 /* Finalize lv sets of all bb headers. */
4008 /* Don't forget EXIT_BLOCK. */
4009 free_lv_set (EXIT_BLOCK_PTR);
4017 /* Initialize an invalid AV_SET for BB.
4018 This set will be updated next time compute_av () process BB. */
4020 invalidate_av_set (basic_block bb)
4022 gcc_assert (BB_AV_LEVEL (bb) <= 0
4023 && BB_AV_SET (bb) == NULL);
4025 BB_AV_LEVEL (bb) = -1;
4028 /* Create initial data sets for BB (they will be invalid). */
4030 create_initial_data_sets (basic_block bb)
4033 BB_LV_SET_VALID_P (bb) = false;
4035 BB_LV_SET (bb) = get_regset_from_pool ();
4036 invalidate_av_set (bb);
4039 /* Free av set of BB. */
4041 free_av_set (basic_block bb)
4043 av_set_clear (&BB_AV_SET (bb));
4044 BB_AV_LEVEL (bb) = 0;
4047 /* Free data sets of BB. */
4049 free_data_sets (basic_block bb)
4055 /* Exchange lv sets of TO and FROM. */
4057 exchange_lv_sets (basic_block to, basic_block from)
4060 regset to_lv_set = BB_LV_SET (to);
4062 BB_LV_SET (to) = BB_LV_SET (from);
4063 BB_LV_SET (from) = to_lv_set;
4067 bool to_lv_set_valid_p = BB_LV_SET_VALID_P (to);
4069 BB_LV_SET_VALID_P (to) = BB_LV_SET_VALID_P (from);
4070 BB_LV_SET_VALID_P (from) = to_lv_set_valid_p;
4075 /* Exchange av sets of TO and FROM. */
4077 exchange_av_sets (basic_block to, basic_block from)
4080 av_set_t to_av_set = BB_AV_SET (to);
4082 BB_AV_SET (to) = BB_AV_SET (from);
4083 BB_AV_SET (from) = to_av_set;
4087 int to_av_level = BB_AV_LEVEL (to);
4089 BB_AV_LEVEL (to) = BB_AV_LEVEL (from);
4090 BB_AV_LEVEL (from) = to_av_level;
4094 /* Exchange data sets of TO and FROM. */
4096 exchange_data_sets (basic_block to, basic_block from)
4098 exchange_lv_sets (to, from);
4099 exchange_av_sets (to, from);
4102 /* Copy data sets of FROM to TO. */
4104 copy_data_sets (basic_block to, basic_block from)
4106 gcc_assert (!BB_LV_SET_VALID_P (to) && !BB_AV_SET_VALID_P (to));
4107 gcc_assert (BB_AV_SET (to) == NULL);
4109 BB_AV_LEVEL (to) = BB_AV_LEVEL (from);
4110 BB_LV_SET_VALID_P (to) = BB_LV_SET_VALID_P (from);
4112 if (BB_AV_SET_VALID_P (from))
4114 BB_AV_SET (to) = av_set_copy (BB_AV_SET (from));
4116 if (BB_LV_SET_VALID_P (from))
4118 gcc_assert (BB_LV_SET (to) != NULL);
4119 COPY_REG_SET (BB_LV_SET (to), BB_LV_SET (from));
4123 /* Return an av set for INSN, if any. */
4125 get_av_set (insn_t insn)
4129 gcc_assert (AV_SET_VALID_P (insn));
4131 if (sel_bb_head_p (insn))
4132 av_set = BB_AV_SET (BLOCK_FOR_INSN (insn));
4139 /* Implementation of AV_LEVEL () macro. Return AV_LEVEL () of INSN. */
4141 get_av_level (insn_t insn)
4145 gcc_assert (INSN_P (insn));
4147 if (sel_bb_head_p (insn))
4148 av_level = BB_AV_LEVEL (BLOCK_FOR_INSN (insn));
4150 av_level = INSN_WS_LEVEL (insn);
4157 /* Variables to work with control-flow graph. */
4159 /* The basic block that already has been processed by the sched_data_update (),
4160 but hasn't been in sel_add_bb () yet. */
4161 static VEC (basic_block, heap) *last_added_blocks = NULL;
4163 /* A pool for allocating successor infos. */
4166 /* A stack for saving succs_info structures. */
4167 struct succs_info *stack;
4172 /* Top of the stack. */
4175 /* Maximal value of the top. */
4179 /* Functions to work with control-flow graph. */
4181 /* Return basic block note of BB. */
4183 sel_bb_head (basic_block bb)
4187 if (bb == EXIT_BLOCK_PTR)
4189 gcc_assert (exit_insn != NULL_RTX);
4196 note = bb_note (bb);
4197 head = next_nonnote_insn (note);
4199 if (head && BLOCK_FOR_INSN (head) != bb)
4206 /* Return true if INSN is a basic block header. */
4208 sel_bb_head_p (insn_t insn)
4210 return sel_bb_head (BLOCK_FOR_INSN (insn)) == insn;
4213 /* Return last insn of BB. */
4215 sel_bb_end (basic_block bb)
4217 if (sel_bb_empty_p (bb))
4220 gcc_assert (bb != EXIT_BLOCK_PTR);
4225 /* Return true if INSN is the last insn in its basic block. */
4227 sel_bb_end_p (insn_t insn)
4229 return insn == sel_bb_end (BLOCK_FOR_INSN (insn));
4232 /* Return true if BB consist of single NOTE_INSN_BASIC_BLOCK. */
4234 sel_bb_empty_p (basic_block bb)
4236 return sel_bb_head (bb) == NULL;
4239 /* True when BB belongs to the current scheduling region. */
4241 in_current_region_p (basic_block bb)
4243 if (bb->index < NUM_FIXED_BLOCKS)
4246 return CONTAINING_RGN (bb->index) == CONTAINING_RGN (BB_TO_BLOCK (0));
4249 /* Return the block which is a fallthru bb of a conditional jump JUMP. */
4251 fallthru_bb_of_jump (rtx jump)
4256 if (any_uncondjump_p (jump))
4257 return single_succ (BLOCK_FOR_INSN (jump));
4259 if (!any_condjump_p (jump))
4262 return FALLTHRU_EDGE (BLOCK_FOR_INSN (jump))->dest;
4265 /* Remove all notes from BB. */
4267 init_bb (basic_block bb)
4269 remove_notes (bb_note (bb), BB_END (bb));
4270 BB_NOTE_LIST (bb) = note_list;
4274 sel_init_bbs (bb_vec_t bbs, basic_block bb)
4276 const struct sched_scan_info_def ssi =
4278 extend_bb_info, /* extend_bb */
4279 init_bb, /* init_bb */
4280 NULL, /* extend_insn */
4281 NULL /* init_insn */
4284 sched_scan (&ssi, bbs, bb, new_insns, NULL);
4287 /* Restore other notes for the whole region. */
4289 sel_restore_other_notes (void)
4293 for (bb = 0; bb < current_nr_blocks; bb++)
4295 basic_block first, last;
4297 first = EBB_FIRST_BB (bb);
4298 last = EBB_LAST_BB (bb)->next_bb;
4302 note_list = BB_NOTE_LIST (first);
4303 restore_other_notes (NULL, first);
4304 BB_NOTE_LIST (first) = NULL_RTX;
4306 first = first->next_bb;
4308 while (first != last);
4312 /* Free per-bb data structures. */
4314 sel_finish_bbs (void)
4316 sel_restore_other_notes ();
4318 /* Remove current loop preheader from this loop. */
4319 if (current_loop_nest)
4320 sel_remove_loop_preheader ();
4322 finish_region_bb_info ();
4325 /* Return true if INSN has a single successor of type FLAGS. */
4327 sel_insn_has_single_succ_p (insn_t insn, int flags)
4331 bool first_p = true;
4333 FOR_EACH_SUCC_1 (succ, si, insn, flags)
4344 /* Allocate successor's info. */
4345 static struct succs_info *
4346 alloc_succs_info (void)
4348 if (succs_info_pool.top == succs_info_pool.max_top)
4352 if (++succs_info_pool.max_top >= succs_info_pool.size)
4355 i = ++succs_info_pool.top;
4356 succs_info_pool.stack[i].succs_ok = VEC_alloc (rtx, heap, 10);
4357 succs_info_pool.stack[i].succs_other = VEC_alloc (rtx, heap, 10);
4358 succs_info_pool.stack[i].probs_ok = VEC_alloc (int, heap, 10);
4361 succs_info_pool.top++;
4363 return &succs_info_pool.stack[succs_info_pool.top];
4366 /* Free successor's info. */
4368 free_succs_info (struct succs_info * sinfo)
4370 gcc_assert (succs_info_pool.top >= 0
4371 && &succs_info_pool.stack[succs_info_pool.top] == sinfo);
4372 succs_info_pool.top--;
4374 /* Clear stale info. */
4375 VEC_block_remove (rtx, sinfo->succs_ok,
4376 0, VEC_length (rtx, sinfo->succs_ok));
4377 VEC_block_remove (rtx, sinfo->succs_other,
4378 0, VEC_length (rtx, sinfo->succs_other));
4379 VEC_block_remove (int, sinfo->probs_ok,
4380 0, VEC_length (int, sinfo->probs_ok));
4381 sinfo->all_prob = 0;
4382 sinfo->succs_ok_n = 0;
4383 sinfo->all_succs_n = 0;
4386 /* Compute successor info for INSN. FLAGS are the flags passed
4387 to the FOR_EACH_SUCC_1 iterator. */
4389 compute_succs_info (insn_t insn, short flags)
4393 struct succs_info *sinfo = alloc_succs_info ();
4395 /* Traverse *all* successors and decide what to do with each. */
4396 FOR_EACH_SUCC_1 (succ, si, insn, SUCCS_ALL)
4398 /* FIXME: this doesn't work for skipping to loop exits, as we don't
4399 perform code motion through inner loops. */
4400 short current_flags = si.current_flags & ~SUCCS_SKIP_TO_LOOP_EXITS;
4402 if (current_flags & flags)
4404 VEC_safe_push (rtx, heap, sinfo->succs_ok, succ);
4405 VEC_safe_push (int, heap, sinfo->probs_ok,
4406 /* FIXME: Improve calculation when skipping
4407 inner loop to exits. */
4409 ? si.e1->probability
4410 : REG_BR_PROB_BASE));
4411 sinfo->succs_ok_n++;
4414 VEC_safe_push (rtx, heap, sinfo->succs_other, succ);
4416 /* Compute all_prob. */
4418 sinfo->all_prob = REG_BR_PROB_BASE;
4420 sinfo->all_prob += si.e1->probability;
4422 sinfo->all_succs_n++;
4428 /* Return the predecessors of BB in PREDS and their number in N.
4429 Empty blocks are skipped. SIZE is used to allocate PREDS. */
4431 cfg_preds_1 (basic_block bb, insn_t **preds, int *n, int *size)
4436 gcc_assert (BLOCK_TO_BB (bb->index) != 0);
4438 FOR_EACH_EDGE (e, ei, bb->preds)
4440 basic_block pred_bb = e->src;
4441 insn_t bb_end = BB_END (pred_bb);
4443 /* ??? This code is not supposed to walk out of a region. */
4444 gcc_assert (in_current_region_p (pred_bb));
4446 if (sel_bb_empty_p (pred_bb))
4447 cfg_preds_1 (pred_bb, preds, n, size);
4451 *preds = XRESIZEVEC (insn_t, *preds,
4452 (*size = 2 * *size + 1));
4453 (*preds)[(*n)++] = bb_end;
4457 gcc_assert (*n != 0);
4460 /* Find all predecessors of BB and record them in PREDS and their number
4461 in N. Empty blocks are skipped, and only normal (forward in-region)
4462 edges are processed. */
4464 cfg_preds (basic_block bb, insn_t **preds, int *n)
4470 cfg_preds_1 (bb, preds, n, &size);
4473 /* Returns true if we are moving INSN through join point. */
4475 sel_num_cfg_preds_gt_1 (insn_t insn)
4479 if (!sel_bb_head_p (insn) || INSN_BB (insn) == 0)
4482 bb = BLOCK_FOR_INSN (insn);
4486 if (EDGE_COUNT (bb->preds) > 1)
4489 gcc_assert (EDGE_PRED (bb, 0)->dest == bb);
4490 bb = EDGE_PRED (bb, 0)->src;
4492 if (!sel_bb_empty_p (bb))
4499 /* Returns true when BB should be the end of an ebb. Adapted from the
4500 code in sched-ebb.c. */
4502 bb_ends_ebb_p (basic_block bb)
4504 basic_block next_bb = bb_next_bb (bb);
4508 if (next_bb == EXIT_BLOCK_PTR
4509 || bitmap_bit_p (forced_ebb_heads, next_bb->index)
4510 || (LABEL_P (BB_HEAD (next_bb))
4511 /* NB: LABEL_NUSES () is not maintained outside of jump.c.
4512 Work around that. */
4513 && !single_pred_p (next_bb)))
4516 if (!in_current_region_p (next_bb))
4519 FOR_EACH_EDGE (e, ei, bb->succs)
4520 if ((e->flags & EDGE_FALLTHRU) != 0)
4522 gcc_assert (e->dest == next_bb);
4530 /* Returns true when INSN and SUCC are in the same EBB, given that SUCC is a
4531 successor of INSN. */
4533 in_same_ebb_p (insn_t insn, insn_t succ)
4535 basic_block ptr = BLOCK_FOR_INSN (insn);
4539 if (ptr == BLOCK_FOR_INSN (succ))
4542 if (bb_ends_ebb_p (ptr))
4545 ptr = bb_next_bb (ptr);
4552 /* Recomputes the reverse topological order for the function and
4553 saves it in REV_TOP_ORDER_INDEX. REV_TOP_ORDER_INDEX_LEN is also
4554 modified appropriately. */
4556 recompute_rev_top_order (void)
4561 if (!rev_top_order_index || rev_top_order_index_len < last_basic_block)
4563 rev_top_order_index_len = last_basic_block;
4564 rev_top_order_index = XRESIZEVEC (int, rev_top_order_index,
4565 rev_top_order_index_len);
4568 postorder = XNEWVEC (int, n_basic_blocks);
4570 n_blocks = post_order_compute (postorder, true, false);
4571 gcc_assert (n_basic_blocks == n_blocks);
4573 /* Build reverse function: for each basic block with BB->INDEX == K
4574 rev_top_order_index[K] is it's reverse topological sort number. */
4575 for (i = 0; i < n_blocks; i++)
4577 gcc_assert (postorder[i] < rev_top_order_index_len);
4578 rev_top_order_index[postorder[i]] = i;
4584 /* Clear all flags from insns in BB that could spoil its rescheduling. */
4586 clear_outdated_rtx_info (basic_block bb)
4590 FOR_BB_INSNS (bb, insn)
4593 SCHED_GROUP_P (insn) = 0;
4594 INSN_AFTER_STALL_P (insn) = 0;
4595 INSN_SCHED_TIMES (insn) = 0;
4596 EXPR_PRIORITY_ADJ (INSN_EXPR (insn)) = 0;
4598 /* We cannot use the changed caches, as previously we could ignore
4599 the LHS dependence due to enabled renaming and transform
4600 the expression, and currently we'll be unable to do this. */
4601 htab_empty (INSN_TRANSFORMED_INSNS (insn));
4605 /* Add BB_NOTE to the pool of available basic block notes. */
4607 return_bb_to_pool (basic_block bb)
4609 rtx note = bb_note (bb);
4611 gcc_assert (NOTE_BASIC_BLOCK (note) == bb
4612 && bb->aux == NULL);
4614 /* It turns out that current cfg infrastructure does not support
4615 reuse of basic blocks. Don't bother for now. */
4616 /*VEC_safe_push (rtx, heap, bb_note_pool, note);*/
4619 /* Get a bb_note from pool or return NULL_RTX if pool is empty. */
4621 get_bb_note_from_pool (void)
4623 if (VEC_empty (rtx, bb_note_pool))
4627 rtx note = VEC_pop (rtx, bb_note_pool);
4629 PREV_INSN (note) = NULL_RTX;
4630 NEXT_INSN (note) = NULL_RTX;
4636 /* Free bb_note_pool. */
4638 free_bb_note_pool (void)
4640 VEC_free (rtx, heap, bb_note_pool);
4643 /* Setup scheduler pool and successor structure. */
4645 alloc_sched_pools (void)
4649 succs_size = MAX_WS + 1;
4650 succs_info_pool.stack = XCNEWVEC (struct succs_info, succs_size);
4651 succs_info_pool.size = succs_size;
4652 succs_info_pool.top = -1;
4653 succs_info_pool.max_top = -1;
4655 sched_lists_pool = create_alloc_pool ("sel-sched-lists",
4656 sizeof (struct _list_node), 500);
4659 /* Free the pools. */
4661 free_sched_pools (void)
4665 free_alloc_pool (sched_lists_pool);
4666 gcc_assert (succs_info_pool.top == -1);
4667 for (i = 0; i < succs_info_pool.max_top; i++)
4669 VEC_free (rtx, heap, succs_info_pool.stack[i].succs_ok);
4670 VEC_free (rtx, heap, succs_info_pool.stack[i].succs_other);
4671 VEC_free (int, heap, succs_info_pool.stack[i].probs_ok);
4673 free (succs_info_pool.stack);
4677 /* Returns a position in RGN where BB can be inserted retaining
4678 topological order. */
4680 find_place_to_insert_bb (basic_block bb, int rgn)
4682 bool has_preds_outside_rgn = false;
4686 /* Find whether we have preds outside the region. */
4687 FOR_EACH_EDGE (e, ei, bb->preds)
4688 if (!in_current_region_p (e->src))
4690 has_preds_outside_rgn = true;
4694 /* Recompute the top order -- needed when we have > 1 pred
4695 and in case we don't have preds outside. */
4696 if (flag_sel_sched_pipelining_outer_loops
4697 && (has_preds_outside_rgn || EDGE_COUNT (bb->preds) > 1))
4699 int i, bbi = bb->index, cur_bbi;
4701 recompute_rev_top_order ();
4702 for (i = RGN_NR_BLOCKS (rgn) - 1; i >= 0; i--)
4704 cur_bbi = BB_TO_BLOCK (i);
4705 if (rev_top_order_index[bbi]
4706 < rev_top_order_index[cur_bbi])
4710 /* We skipped the right block, so we increase i. We accomodate
4711 it for increasing by step later, so we decrease i. */
4714 else if (has_preds_outside_rgn)
4716 /* This is the case when we generate an extra empty block
4717 to serve as region head during pipelining. */
4718 e = EDGE_SUCC (bb, 0);
4719 gcc_assert (EDGE_COUNT (bb->succs) == 1
4720 && in_current_region_p (EDGE_SUCC (bb, 0)->dest)
4721 && (BLOCK_TO_BB (e->dest->index) == 0));
4725 /* We don't have preds outside the region. We should have
4726 the only pred, because the multiple preds case comes from
4727 the pipelining of outer loops, and that is handled above.
4728 Just take the bbi of this single pred. */
4729 if (EDGE_COUNT (bb->succs) > 0)
4733 gcc_assert (EDGE_COUNT (bb->preds) == 1);
4735 pred_bbi = EDGE_PRED (bb, 0)->src->index;
4736 return BLOCK_TO_BB (pred_bbi);
4739 /* BB has no successors. It is safe to put it in the end. */
4740 return current_nr_blocks - 1;
4743 /* Deletes an empty basic block freeing its data. */
4745 delete_and_free_basic_block (basic_block bb)
4747 gcc_assert (sel_bb_empty_p (bb));
4752 bitmap_clear_bit (blocks_to_reschedule, bb->index);
4754 /* Can't assert av_set properties because we use sel_aremove_bb
4755 when removing loop preheader from the region. At the point of
4756 removing the preheader we already have deallocated sel_region_bb_info. */
4757 gcc_assert (BB_LV_SET (bb) == NULL
4758 && !BB_LV_SET_VALID_P (bb)
4759 && BB_AV_LEVEL (bb) == 0
4760 && BB_AV_SET (bb) == NULL);
4762 delete_basic_block (bb);
4765 /* Add BB to the current region and update the region data. */
4767 add_block_to_current_region (basic_block bb)
4769 int i, pos, bbi = -2, rgn;
4771 rgn = CONTAINING_RGN (BB_TO_BLOCK (0));
4772 bbi = find_place_to_insert_bb (bb, rgn);
4774 pos = RGN_BLOCKS (rgn) + bbi;
4776 gcc_assert (RGN_HAS_REAL_EBB (rgn) == 0
4777 && ebb_head[bbi] == pos);
4779 /* Make a place for the new block. */
4782 for (i = RGN_BLOCKS (rgn + 1) - 1; i >= pos; i--)
4783 BLOCK_TO_BB (rgn_bb_table[i])++;
4785 memmove (rgn_bb_table + pos + 1,
4787 (RGN_BLOCKS (nr_regions) - pos) * sizeof (*rgn_bb_table));
4789 /* Initialize data for BB. */
4790 rgn_bb_table[pos] = bb->index;
4791 BLOCK_TO_BB (bb->index) = bbi;
4792 CONTAINING_RGN (bb->index) = rgn;
4794 RGN_NR_BLOCKS (rgn)++;
4796 for (i = rgn + 1; i <= nr_regions; i++)
4800 /* Remove BB from the current region and update the region data. */
4802 remove_bb_from_region (basic_block bb)
4804 int i, pos, bbi = -2, rgn;
4806 rgn = CONTAINING_RGN (BB_TO_BLOCK (0));
4807 bbi = BLOCK_TO_BB (bb->index);
4808 pos = RGN_BLOCKS (rgn) + bbi;
4810 gcc_assert (RGN_HAS_REAL_EBB (rgn) == 0
4811 && ebb_head[bbi] == pos);
4813 for (i = RGN_BLOCKS (rgn + 1) - 1; i >= pos; i--)
4814 BLOCK_TO_BB (rgn_bb_table[i])--;
4816 memmove (rgn_bb_table + pos,
4817 rgn_bb_table + pos + 1,
4818 (RGN_BLOCKS (nr_regions) - pos) * sizeof (*rgn_bb_table));
4820 RGN_NR_BLOCKS (rgn)--;
4821 for (i = rgn + 1; i <= nr_regions; i++)
4825 /* Add BB to the current region and update all data. If BB is NULL, add all
4826 blocks from last_added_blocks vector. */
4828 sel_add_bb (basic_block bb)
4830 /* Extend luids so that new notes will receive zero luids. */
4831 sched_init_luids (NULL, NULL, NULL, NULL);
4833 sel_init_bbs (last_added_blocks, NULL);
4835 /* When bb is passed explicitly, the vector should contain
4836 the only element that equals to bb; otherwise, the vector
4837 should not be NULL. */
4838 gcc_assert (last_added_blocks != NULL);
4842 gcc_assert (VEC_length (basic_block, last_added_blocks) == 1
4843 && VEC_index (basic_block,
4844 last_added_blocks, 0) == bb);
4845 add_block_to_current_region (bb);
4847 /* We associate creating/deleting data sets with the first insn
4848 appearing / disappearing in the bb. */
4849 if (!sel_bb_empty_p (bb) && BB_LV_SET (bb) == NULL)
4850 create_initial_data_sets (bb);
4852 VEC_free (basic_block, heap, last_added_blocks);
4855 /* BB is NULL - process LAST_ADDED_BLOCKS instead. */
4858 basic_block temp_bb = NULL;
4861 VEC_iterate (basic_block, last_added_blocks, i, bb); i++)
4863 add_block_to_current_region (bb);
4867 /* We need to fetch at least one bb so we know the region
4869 gcc_assert (temp_bb != NULL);
4872 VEC_free (basic_block, heap, last_added_blocks);
4875 rgn_setup_region (CONTAINING_RGN (bb->index));
4878 /* Remove BB from the current region and update all data.
4879 If REMOVE_FROM_CFG_PBB is true, also remove the block cfom cfg. */
4881 sel_remove_bb (basic_block bb, bool remove_from_cfg_p)
4883 gcc_assert (bb != NULL && BB_NOTE_LIST (bb) == NULL_RTX);
4885 remove_bb_from_region (bb);
4886 return_bb_to_pool (bb);
4887 bitmap_clear_bit (blocks_to_reschedule, bb->index);
4889 if (remove_from_cfg_p)
4890 delete_and_free_basic_block (bb);
4892 rgn_setup_region (CONTAINING_RGN (bb->index));
4895 /* Concatenate info of EMPTY_BB to info of MERGE_BB. */
4897 move_bb_info (basic_block merge_bb, basic_block empty_bb)
4899 gcc_assert (in_current_region_p (merge_bb));
4901 concat_note_lists (BB_NOTE_LIST (empty_bb),
4902 &BB_NOTE_LIST (merge_bb));
4903 BB_NOTE_LIST (empty_bb) = NULL_RTX;
4907 /* Remove an empty basic block EMPTY_BB. When MERGE_UP_P is true, we put
4908 EMPTY_BB's note lists into its predecessor instead of putting them
4909 into the successor. When REMOVE_FROM_CFG_P is true, also remove
4912 sel_remove_empty_bb (basic_block empty_bb, bool merge_up_p,
4913 bool remove_from_cfg_p)
4915 basic_block merge_bb;
4917 gcc_assert (sel_bb_empty_p (empty_bb));
4921 merge_bb = empty_bb->prev_bb;
4922 gcc_assert (EDGE_COUNT (empty_bb->preds) == 1
4923 && EDGE_PRED (empty_bb, 0)->src == merge_bb);
4930 merge_bb = bb_next_bb (empty_bb);
4932 /* Redirect incoming edges (except fallthrough one) of EMPTY_BB to its
4934 for (ei = ei_start (empty_bb->preds);
4935 (e = ei_safe_edge (ei)); )
4937 if (! (e->flags & EDGE_FALLTHRU))
4938 sel_redirect_edge_and_branch (e, merge_bb);
4943 gcc_assert (EDGE_COUNT (empty_bb->succs) == 1
4944 && EDGE_SUCC (empty_bb, 0)->dest == merge_bb);
4947 move_bb_info (merge_bb, empty_bb);
4948 remove_empty_bb (empty_bb, remove_from_cfg_p);
4951 /* Remove EMPTY_BB. If REMOVE_FROM_CFG_P is false, remove EMPTY_BB from
4952 region, but keep it in CFG. */
4954 remove_empty_bb (basic_block empty_bb, bool remove_from_cfg_p)
4956 /* The block should contain just a note or a label.
4957 We try to check whether it is unused below. */
4958 gcc_assert (BB_HEAD (empty_bb) == BB_END (empty_bb)
4959 || LABEL_P (BB_HEAD (empty_bb)));
4961 /* If basic block has predecessors or successors, redirect them. */
4962 if (remove_from_cfg_p
4963 && (EDGE_COUNT (empty_bb->preds) > 0
4964 || EDGE_COUNT (empty_bb->succs) > 0))
4969 /* We need to init PRED and SUCC before redirecting edges. */
4970 if (EDGE_COUNT (empty_bb->preds) > 0)
4974 gcc_assert (EDGE_COUNT (empty_bb->preds) == 1);
4976 e = EDGE_PRED (empty_bb, 0);
4977 gcc_assert (e->src == empty_bb->prev_bb
4978 && (e->flags & EDGE_FALLTHRU));
4980 pred = empty_bb->prev_bb;
4985 if (EDGE_COUNT (empty_bb->succs) > 0)
4987 /* We do not check fallthruness here as above, because
4988 after removing a jump the edge may actually be not fallthru. */
4989 gcc_assert (EDGE_COUNT (empty_bb->succs) == 1);
4990 succ = EDGE_SUCC (empty_bb, 0)->dest;
4995 if (EDGE_COUNT (empty_bb->preds) > 0 && succ != NULL)
4997 edge e = EDGE_PRED (empty_bb, 0);
4999 if (e->flags & EDGE_FALLTHRU)
5000 redirect_edge_succ_nodup (e, succ);
5002 sel_redirect_edge_and_branch (EDGE_PRED (empty_bb, 0), succ);
5005 if (EDGE_COUNT (empty_bb->succs) > 0 && pred != NULL)
5007 edge e = EDGE_SUCC (empty_bb, 0);
5009 if (find_edge (pred, e->dest) == NULL)
5010 redirect_edge_pred (e, pred);
5014 /* Finish removing. */
5015 sel_remove_bb (empty_bb, remove_from_cfg_p);
5018 /* An implementation of create_basic_block hook, which additionally updates
5019 per-bb data structures. */
5021 sel_create_basic_block (void *headp, void *endp, basic_block after)
5026 gcc_assert (flag_sel_sched_pipelining_outer_loops
5027 || last_added_blocks == NULL);
5029 new_bb_note = get_bb_note_from_pool ();
5031 if (new_bb_note == NULL_RTX)
5032 new_bb = orig_cfg_hooks.create_basic_block (headp, endp, after);
5035 new_bb = create_basic_block_structure ((rtx) headp, (rtx) endp,
5036 new_bb_note, after);
5040 VEC_safe_push (basic_block, heap, last_added_blocks, new_bb);
5045 /* Implement sched_init_only_bb (). */
5047 sel_init_only_bb (basic_block bb, basic_block after)
5049 gcc_assert (after == NULL);
5052 rgn_make_new_region_out_of_new_block (bb);
5055 /* Update the latch when we've splitted or merged it from FROM block to TO.
5056 This should be checked for all outer loops, too. */
5058 change_loops_latches (basic_block from, basic_block to)
5060 gcc_assert (from != to);
5062 if (current_loop_nest)
5066 for (loop = current_loop_nest; loop; loop = loop_outer (loop))
5067 if (considered_for_pipelining_p (loop) && loop->latch == from)
5069 gcc_assert (loop == current_loop_nest);
5071 gcc_assert (loop_latch_edge (loop));
5076 /* Splits BB on two basic blocks, adding it to the region and extending
5077 per-bb data structures. Returns the newly created bb. */
5079 sel_split_block (basic_block bb, rtx after)
5084 new_bb = sched_split_block_1 (bb, after);
5085 sel_add_bb (new_bb);
5087 /* This should be called after sel_add_bb, because this uses
5088 CONTAINING_RGN for the new block, which is not yet initialized.
5089 FIXME: this function may be a no-op now. */
5090 change_loops_latches (bb, new_bb);
5092 /* Update ORIG_BB_INDEX for insns moved into the new block. */
5093 FOR_BB_INSNS (new_bb, insn)
5095 EXPR_ORIG_BB_INDEX (INSN_EXPR (insn)) = new_bb->index;
5097 if (sel_bb_empty_p (bb))
5099 gcc_assert (!sel_bb_empty_p (new_bb));
5101 /* NEW_BB has data sets that need to be updated and BB holds
5102 data sets that should be removed. Exchange these data sets
5103 so that we won't lose BB's valid data sets. */
5104 exchange_data_sets (new_bb, bb);
5105 free_data_sets (bb);
5108 if (!sel_bb_empty_p (new_bb)
5109 && bitmap_bit_p (blocks_to_reschedule, bb->index))
5110 bitmap_set_bit (blocks_to_reschedule, new_bb->index);
5115 /* If BB ends with a jump insn whose ID is bigger then PREV_MAX_UID, return it.
5116 Otherwise returns NULL. */
5118 check_for_new_jump (basic_block bb, int prev_max_uid)
5122 end = sel_bb_end (bb);
5123 if (end && INSN_UID (end) >= prev_max_uid)
5128 /* Look for a new jump either in FROM_BB block or in newly created JUMP_BB block.
5129 New means having UID at least equal to PREV_MAX_UID. */
5131 find_new_jump (basic_block from, basic_block jump_bb, int prev_max_uid)
5135 /* Return immediately if no new insns were emitted. */
5136 if (get_max_uid () == prev_max_uid)
5139 /* Now check both blocks for new jumps. It will ever be only one. */
5140 if ((jump = check_for_new_jump (from, prev_max_uid)))
5144 && (jump = check_for_new_jump (jump_bb, prev_max_uid)))
5149 /* Splits E and adds the newly created basic block to the current region.
5150 Returns this basic block. */
5152 sel_split_edge (edge e)
5154 basic_block new_bb, src, other_bb = NULL;
5159 prev_max_uid = get_max_uid ();
5160 new_bb = split_edge (e);
5162 if (flag_sel_sched_pipelining_outer_loops
5163 && current_loop_nest)
5168 /* Some of the basic blocks might not have been added to the loop.
5169 Add them here, until this is fixed in force_fallthru. */
5171 VEC_iterate (basic_block, last_added_blocks, i, bb); i++)
5172 if (!bb->loop_father)
5174 add_bb_to_loop (bb, e->dest->loop_father);
5176 gcc_assert (!other_bb && (new_bb->index != bb->index));
5181 /* Add all last_added_blocks to the region. */
5184 jump = find_new_jump (src, new_bb, prev_max_uid);
5186 sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP);
5188 /* Put the correct lv set on this block. */
5189 if (other_bb && !sel_bb_empty_p (other_bb))
5190 compute_live (sel_bb_head (other_bb));
5195 /* Implement sched_create_empty_bb (). */
5197 sel_create_empty_bb (basic_block after)
5201 new_bb = sched_create_empty_bb_1 (after);
5203 /* We'll explicitly initialize NEW_BB via sel_init_only_bb () a bit
5205 gcc_assert (VEC_length (basic_block, last_added_blocks) == 1
5206 && VEC_index (basic_block, last_added_blocks, 0) == new_bb);
5208 VEC_free (basic_block, heap, last_added_blocks);
5212 /* Implement sched_create_recovery_block. ORIG_INSN is where block
5213 will be splitted to insert a check. */
5215 sel_create_recovery_block (insn_t orig_insn)
5217 basic_block first_bb, second_bb, recovery_block;
5218 basic_block before_recovery = NULL;
5221 first_bb = BLOCK_FOR_INSN (orig_insn);
5222 if (sel_bb_end_p (orig_insn))
5224 /* Avoid introducing an empty block while splitting. */
5225 gcc_assert (single_succ_p (first_bb));
5226 second_bb = single_succ (first_bb);
5229 second_bb = sched_split_block (first_bb, orig_insn);
5231 recovery_block = sched_create_recovery_block (&before_recovery);
5232 if (before_recovery)
5233 copy_lv_set_from (before_recovery, EXIT_BLOCK_PTR);
5235 gcc_assert (sel_bb_empty_p (recovery_block));
5236 sched_create_recovery_edges (first_bb, recovery_block, second_bb);
5237 if (current_loops != NULL)
5238 add_bb_to_loop (recovery_block, first_bb->loop_father);
5240 sel_add_bb (recovery_block);
5242 jump = BB_END (recovery_block);
5243 gcc_assert (sel_bb_head (recovery_block) == jump);
5244 sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP);
5246 return recovery_block;
5249 /* Merge basic block B into basic block A. */
5251 sel_merge_blocks (basic_block a, basic_block b)
5253 gcc_assert (can_merge_blocks_p (a, b));
5255 sel_remove_empty_bb (b, true, false);
5256 merge_blocks (a, b);
5258 change_loops_latches (b, a);
5261 /* A wrapper for redirect_edge_and_branch_force, which also initializes
5262 data structures for possibly created bb and insns. Returns the newly
5263 added bb or NULL, when a bb was not needed. */
5265 sel_redirect_edge_and_branch_force (edge e, basic_block to)
5267 basic_block jump_bb, src;
5271 gcc_assert (!sel_bb_empty_p (e->src));
5274 prev_max_uid = get_max_uid ();
5275 jump_bb = redirect_edge_and_branch_force (e, to);
5277 if (jump_bb != NULL)
5278 sel_add_bb (jump_bb);
5280 /* This function could not be used to spoil the loop structure by now,
5281 thus we don't care to update anything. But check it to be sure. */
5282 if (current_loop_nest
5284 gcc_assert (loop_latch_edge (current_loop_nest));
5286 jump = find_new_jump (src, jump_bb, prev_max_uid);
5288 sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP);
5291 /* A wrapper for redirect_edge_and_branch. */
5293 sel_redirect_edge_and_branch (edge e, basic_block to)
5300 latch_edge_p = (pipelining_p
5301 && current_loop_nest
5302 && e == loop_latch_edge (current_loop_nest));
5305 prev_max_uid = get_max_uid ();
5307 redirect_edge_and_branch (e, to);
5308 gcc_assert (last_added_blocks == NULL);
5310 /* When we've redirected a latch edge, update the header. */
5313 current_loop_nest->header = to;
5314 gcc_assert (loop_latch_edge (current_loop_nest));
5317 jump = find_new_jump (src, NULL, prev_max_uid);
5319 sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP);
5322 /* This variable holds the cfg hooks used by the selective scheduler. */
5323 static struct cfg_hooks sel_cfg_hooks;
5325 /* Register sel-sched cfg hooks. */
5327 sel_register_cfg_hooks (void)
5329 sched_split_block = sel_split_block;
5331 orig_cfg_hooks = get_cfg_hooks ();
5332 sel_cfg_hooks = orig_cfg_hooks;
5334 sel_cfg_hooks.create_basic_block = sel_create_basic_block;
5336 set_cfg_hooks (sel_cfg_hooks);
5338 sched_init_only_bb = sel_init_only_bb;
5339 sched_split_block = sel_split_block;
5340 sched_create_empty_bb = sel_create_empty_bb;
5343 /* Unregister sel-sched cfg hooks. */
5345 sel_unregister_cfg_hooks (void)
5347 sched_create_empty_bb = NULL;
5348 sched_split_block = NULL;
5349 sched_init_only_bb = NULL;
5351 set_cfg_hooks (orig_cfg_hooks);
5355 /* Emit an insn rtx based on PATTERN. If a jump insn is wanted,
5356 LABEL is where this jump should be directed. */
5358 create_insn_rtx_from_pattern (rtx pattern, rtx label)
5362 gcc_assert (!INSN_P (pattern));
5366 if (label == NULL_RTX)
5367 insn_rtx = emit_insn (pattern);
5370 insn_rtx = emit_jump_insn (pattern);
5371 JUMP_LABEL (insn_rtx) = label;
5372 ++LABEL_NUSES (label);
5377 sched_init_luids (NULL, NULL, NULL, NULL);
5378 sched_extend_target ();
5379 sched_deps_init (false);
5381 /* Initialize INSN_CODE now. */
5382 recog_memoized (insn_rtx);
5386 /* Create a new vinsn for INSN_RTX. FORCE_UNIQUE_P is true when the vinsn
5387 must not be clonable. */
5389 create_vinsn_from_insn_rtx (rtx insn_rtx, bool force_unique_p)
5391 gcc_assert (INSN_P (insn_rtx) && !INSN_IN_STREAM_P (insn_rtx));
5393 /* If VINSN_TYPE is not USE, retain its uniqueness. */
5394 return vinsn_create (insn_rtx, force_unique_p);
5397 /* Create a copy of INSN_RTX. */
5399 create_copy_of_insn_rtx (rtx insn_rtx)
5403 gcc_assert (NONJUMP_INSN_P (insn_rtx));
5405 res = create_insn_rtx_from_pattern (copy_rtx (PATTERN (insn_rtx)),
5410 /* Change vinsn field of EXPR to hold NEW_VINSN. */
5412 change_vinsn_in_expr (expr_t expr, vinsn_t new_vinsn)
5414 vinsn_detach (EXPR_VINSN (expr));
5416 EXPR_VINSN (expr) = new_vinsn;
5417 vinsn_attach (new_vinsn);
5420 /* Helpers for global init. */
5421 /* This structure is used to be able to call existing bundling mechanism
5422 and calculate insn priorities. */
5423 static struct haifa_sched_info sched_sel_haifa_sched_info =
5425 NULL, /* init_ready_list */
5426 NULL, /* can_schedule_ready_p */
5427 NULL, /* schedule_more_p */
5428 NULL, /* new_ready */
5429 NULL, /* rgn_rank */
5430 sel_print_insn, /* rgn_print_insn */
5431 contributes_to_priority,
5437 NULL, /* add_remove_insn */
5438 NULL, /* begin_schedule_ready */
5439 NULL, /* advance_target_bb */
5443 /* Setup special insns used in the scheduler. */
5445 setup_nop_and_exit_insns (void)
5447 gcc_assert (nop_pattern == NULL_RTX
5448 && exit_insn == NULL_RTX);
5450 nop_pattern = gen_nop ();
5453 emit_insn (nop_pattern);
5454 exit_insn = get_insns ();
5456 set_block_for_insn (exit_insn, EXIT_BLOCK_PTR);
5459 /* Free special insns used in the scheduler. */
5461 free_nop_and_exit_insns (void)
5463 exit_insn = NULL_RTX;
5464 nop_pattern = NULL_RTX;
5467 /* Setup a special vinsn used in new insns initialization. */
5469 setup_nop_vinsn (void)
5471 nop_vinsn = vinsn_create (exit_insn, false);
5472 vinsn_attach (nop_vinsn);
5475 /* Free a special vinsn used in new insns initialization. */
5477 free_nop_vinsn (void)
5479 gcc_assert (VINSN_COUNT (nop_vinsn) == 1);
5480 vinsn_detach (nop_vinsn);
5484 /* Call a set_sched_flags hook. */
5486 sel_set_sched_flags (void)
5488 /* ??? This means that set_sched_flags were called, and we decided to
5489 support speculation. However, set_sched_flags also modifies flags
5490 on current_sched_info, doing this only at global init. And we
5491 sometimes change c_s_i later. So put the correct flags again. */
5492 if (spec_info && targetm.sched.set_sched_flags)
5493 targetm.sched.set_sched_flags (spec_info);
5496 /* Setup pointers to global sched info structures. */
5498 sel_setup_sched_infos (void)
5500 rgn_setup_common_sched_info ();
5502 memcpy (&sel_common_sched_info, common_sched_info,
5503 sizeof (sel_common_sched_info));
5505 sel_common_sched_info.fix_recovery_cfg = NULL;
5506 sel_common_sched_info.add_block = NULL;
5507 sel_common_sched_info.estimate_number_of_insns
5508 = sel_estimate_number_of_insns;
5509 sel_common_sched_info.luid_for_non_insn = sel_luid_for_non_insn;
5510 sel_common_sched_info.sched_pass_id = SCHED_SEL_PASS;
5512 common_sched_info = &sel_common_sched_info;
5514 current_sched_info = &sched_sel_haifa_sched_info;
5515 current_sched_info->sched_max_insns_priority =
5516 get_rgn_sched_max_insns_priority ();
5518 sel_set_sched_flags ();
5522 /* Adds basic block BB to region RGN at the position *BB_ORD_INDEX,
5523 *BB_ORD_INDEX after that is increased. */
5525 sel_add_block_to_region (basic_block bb, int *bb_ord_index, int rgn)
5527 RGN_NR_BLOCKS (rgn) += 1;
5528 RGN_DONT_CALC_DEPS (rgn) = 0;
5529 RGN_HAS_REAL_EBB (rgn) = 0;
5530 CONTAINING_RGN (bb->index) = rgn;
5531 BLOCK_TO_BB (bb->index) = *bb_ord_index;
5532 rgn_bb_table[RGN_BLOCKS (rgn) + *bb_ord_index] = bb->index;
5535 /* FIXME: it is true only when not scheduling ebbs. */
5536 RGN_BLOCKS (rgn + 1) = RGN_BLOCKS (rgn) + RGN_NR_BLOCKS (rgn);
5539 /* Functions to support pipelining of outer loops. */
5541 /* Creates a new empty region and returns it's number. */
5543 sel_create_new_region (void)
5545 int new_rgn_number = nr_regions;
5547 RGN_NR_BLOCKS (new_rgn_number) = 0;
5549 /* FIXME: This will work only when EBBs are not created. */
5550 if (new_rgn_number != 0)
5551 RGN_BLOCKS (new_rgn_number) = RGN_BLOCKS (new_rgn_number - 1) +
5552 RGN_NR_BLOCKS (new_rgn_number - 1);
5554 RGN_BLOCKS (new_rgn_number) = 0;
5556 /* Set the blocks of the next region so the other functions may
5557 calculate the number of blocks in the region. */
5558 RGN_BLOCKS (new_rgn_number + 1) = RGN_BLOCKS (new_rgn_number) +
5559 RGN_NR_BLOCKS (new_rgn_number);
5563 return new_rgn_number;
5566 /* If X has a smaller topological sort number than Y, returns -1;
5567 if greater, returns 1. */
5569 bb_top_order_comparator (const void *x, const void *y)
5571 basic_block bb1 = *(const basic_block *) x;
5572 basic_block bb2 = *(const basic_block *) y;
5574 gcc_assert (bb1 == bb2
5575 || rev_top_order_index[bb1->index]
5576 != rev_top_order_index[bb2->index]);
5578 /* It's a reverse topological order in REV_TOP_ORDER_INDEX, so
5579 bbs with greater number should go earlier. */
5580 if (rev_top_order_index[bb1->index] > rev_top_order_index[bb2->index])
5586 /* Create a region for LOOP and return its number. If we don't want
5587 to pipeline LOOP, return -1. */
5589 make_region_from_loop (struct loop *loop)
5592 int new_rgn_number = -1;
5595 /* Basic block index, to be assigned to BLOCK_TO_BB. */
5596 int bb_ord_index = 0;
5597 basic_block *loop_blocks;
5598 basic_block preheader_block;
5601 > (unsigned) PARAM_VALUE (PARAM_MAX_PIPELINE_REGION_BLOCKS))
5604 /* Don't pipeline loops whose latch belongs to some of its inner loops. */
5605 for (inner = loop->inner; inner; inner = inner->inner)
5606 if (flow_bb_inside_loop_p (inner, loop->latch))
5609 loop->ninsns = num_loop_insns (loop);
5610 if ((int) loop->ninsns > PARAM_VALUE (PARAM_MAX_PIPELINE_REGION_INSNS))
5613 loop_blocks = get_loop_body_in_custom_order (loop, bb_top_order_comparator);
5615 for (i = 0; i < loop->num_nodes; i++)
5616 if (loop_blocks[i]->flags & BB_IRREDUCIBLE_LOOP)
5622 preheader_block = loop_preheader_edge (loop)->src;
5623 gcc_assert (preheader_block);
5624 gcc_assert (loop_blocks[0] == loop->header);
5626 new_rgn_number = sel_create_new_region ();
5628 sel_add_block_to_region (preheader_block, &bb_ord_index, new_rgn_number);
5629 SET_BIT (bbs_in_loop_rgns, preheader_block->index);
5631 for (i = 0; i < loop->num_nodes; i++)
5633 /* Add only those blocks that haven't been scheduled in the inner loop.
5634 The exception is the basic blocks with bookkeeping code - they should
5635 be added to the region (and they actually don't belong to the loop
5636 body, but to the region containing that loop body). */
5638 gcc_assert (new_rgn_number >= 0);
5640 if (! TEST_BIT (bbs_in_loop_rgns, loop_blocks[i]->index))
5642 sel_add_block_to_region (loop_blocks[i], &bb_ord_index,
5644 SET_BIT (bbs_in_loop_rgns, loop_blocks[i]->index);
5649 MARK_LOOP_FOR_PIPELINING (loop);
5651 return new_rgn_number;
5654 /* Create a new region from preheader blocks LOOP_BLOCKS. */
5656 make_region_from_loop_preheader (VEC(basic_block, heap) **loop_blocks)
5659 int new_rgn_number = -1;
5662 /* Basic block index, to be assigned to BLOCK_TO_BB. */
5663 int bb_ord_index = 0;
5665 new_rgn_number = sel_create_new_region ();
5667 for (i = 0; VEC_iterate (basic_block, *loop_blocks, i, bb); i++)
5669 gcc_assert (new_rgn_number >= 0);
5671 sel_add_block_to_region (bb, &bb_ord_index, new_rgn_number);
5674 VEC_free (basic_block, heap, *loop_blocks);
5675 gcc_assert (*loop_blocks == NULL);
5679 /* Create region(s) from loop nest LOOP, such that inner loops will be
5680 pipelined before outer loops. Returns true when a region for LOOP
5683 make_regions_from_loop_nest (struct loop *loop)
5685 struct loop *cur_loop;
5688 /* Traverse all inner nodes of the loop. */
5689 for (cur_loop = loop->inner; cur_loop; cur_loop = cur_loop->next)
5690 if (! TEST_BIT (bbs_in_loop_rgns, cur_loop->header->index))
5693 /* At this moment all regular inner loops should have been pipelined.
5694 Try to create a region from this loop. */
5695 rgn_number = make_region_from_loop (loop);
5700 VEC_safe_push (loop_p, heap, loop_nests, loop);
5704 /* Initalize data structures needed. */
5706 sel_init_pipelining (void)
5708 /* Collect loop information to be used in outer loops pipelining. */
5709 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
5710 | LOOPS_HAVE_FALLTHRU_PREHEADERS
5711 | LOOPS_HAVE_RECORDED_EXITS
5712 | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS);
5713 current_loop_nest = NULL;
5715 bbs_in_loop_rgns = sbitmap_alloc (last_basic_block);
5716 sbitmap_zero (bbs_in_loop_rgns);
5718 recompute_rev_top_order ();
5721 /* Returns a struct loop for region RGN. */
5723 get_loop_nest_for_rgn (unsigned int rgn)
5725 /* Regions created with extend_rgns don't have corresponding loop nests,
5726 because they don't represent loops. */
5727 if (rgn < VEC_length (loop_p, loop_nests))
5728 return VEC_index (loop_p, loop_nests, rgn);
5733 /* True when LOOP was included into pipelining regions. */
5735 considered_for_pipelining_p (struct loop *loop)
5737 if (loop_depth (loop) == 0)
5740 /* Now, the loop could be too large or irreducible. Check whether its
5741 region is in LOOP_NESTS.
5742 We determine the region number of LOOP as the region number of its
5743 latch. We can't use header here, because this header could be
5744 just removed preheader and it will give us the wrong region number.
5745 Latch can't be used because it could be in the inner loop too. */
5746 if (LOOP_MARKED_FOR_PIPELINING_P (loop) && pipelining_p)
5748 int rgn = CONTAINING_RGN (loop->latch->index);
5750 gcc_assert ((unsigned) rgn < VEC_length (loop_p, loop_nests));
5757 /* Makes regions from the rest of the blocks, after loops are chosen
5760 make_regions_from_the_rest (void)
5772 /* Index in rgn_bb_table where to start allocating new regions. */
5773 cur_rgn_blocks = nr_regions ? RGN_BLOCKS (nr_regions) : 0;
5774 new_regions = nr_regions;
5776 /* Make regions from all the rest basic blocks - those that don't belong to
5777 any loop or belong to irreducible loops. Prepare the data structures
5780 /* LOOP_HDR[I] == -1 if I-th bb doesn't belong to any loop,
5781 LOOP_HDR[I] == LOOP_HDR[J] iff basic blocks I and J reside within the same
5783 loop_hdr = XNEWVEC (int, last_basic_block);
5784 degree = XCNEWVEC (int, last_basic_block);
5787 /* For each basic block that belongs to some loop assign the number
5788 of innermost loop it belongs to. */
5789 for (i = 0; i < last_basic_block; i++)
5794 if (bb->loop_father && !bb->loop_father->num == 0
5795 && !(bb->flags & BB_IRREDUCIBLE_LOOP))
5796 loop_hdr[bb->index] = bb->loop_father->num;
5799 /* For each basic block degree is calculated as the number of incoming
5800 edges, that are going out of bbs that are not yet scheduled.
5801 The basic blocks that are scheduled have degree value of zero. */
5804 degree[bb->index] = 0;
5806 if (!TEST_BIT (bbs_in_loop_rgns, bb->index))
5808 FOR_EACH_EDGE (e, ei, bb->preds)
5809 if (!TEST_BIT (bbs_in_loop_rgns, e->src->index))
5810 degree[bb->index]++;
5813 degree[bb->index] = -1;
5816 extend_rgns (degree, &cur_rgn_blocks, bbs_in_loop_rgns, loop_hdr);
5818 /* Any block that did not end up in a region is placed into a region
5821 if (degree[bb->index] >= 0)
5823 rgn_bb_table[cur_rgn_blocks] = bb->index;
5824 RGN_NR_BLOCKS (nr_regions) = 1;
5825 RGN_BLOCKS (nr_regions) = cur_rgn_blocks++;
5826 RGN_DONT_CALC_DEPS (nr_regions) = 0;
5827 RGN_HAS_REAL_EBB (nr_regions) = 0;
5828 CONTAINING_RGN (bb->index) = nr_regions++;
5829 BLOCK_TO_BB (bb->index) = 0;
5836 /* Free data structures used in pipelining of loops. */
5837 void sel_finish_pipelining (void)
5842 /* Release aux fields so we don't free them later by mistake. */
5843 FOR_EACH_LOOP (li, loop, 0)
5846 loop_optimizer_finalize ();
5848 VEC_free (loop_p, heap, loop_nests);
5850 free (rev_top_order_index);
5851 rev_top_order_index = NULL;
5854 /* This function replaces the find_rgns when
5855 FLAG_SEL_SCHED_PIPELINING_OUTER_LOOPS is set. */
5857 sel_find_rgns (void)
5859 sel_init_pipelining ();
5867 FOR_EACH_LOOP (li, loop, (flag_sel_sched_pipelining_outer_loops
5869 : LI_ONLY_INNERMOST))
5870 make_regions_from_loop_nest (loop);
5873 /* Make regions from all the rest basic blocks and schedule them.
5874 These blocks include blocks that don't belong to any loop or belong
5875 to irreducible loops. */
5876 make_regions_from_the_rest ();
5878 /* We don't need bbs_in_loop_rgns anymore. */
5879 sbitmap_free (bbs_in_loop_rgns);
5880 bbs_in_loop_rgns = NULL;
5883 /* Adds the preheader blocks from previous loop to current region taking
5884 it from LOOP_PREHEADER_BLOCKS (current_loop_nest).
5885 This function is only used with -fsel-sched-pipelining-outer-loops. */
5887 sel_add_loop_preheaders (void)
5891 VEC(basic_block, heap) *preheader_blocks
5892 = LOOP_PREHEADER_BLOCKS (current_loop_nest);
5895 VEC_iterate (basic_block, preheader_blocks, i, bb);
5899 VEC_free (basic_block, heap, preheader_blocks);
5902 /* While pipelining outer loops, returns TRUE if BB is a loop preheader.
5903 Please note that the function should also work when pipelining_p is
5904 false, because it is used when deciding whether we should or should
5905 not reschedule pipelined code. */
5907 sel_is_loop_preheader_p (basic_block bb)
5909 if (current_loop_nest)
5913 if (preheader_removed)
5916 /* Preheader is the first block in the region. */
5917 if (BLOCK_TO_BB (bb->index) == 0)
5920 /* We used to find a preheader with the topological information.
5921 Check that the above code is equivalent to what we did before. */
5923 if (in_current_region_p (current_loop_nest->header))
5924 gcc_assert (!(BLOCK_TO_BB (bb->index)
5925 < BLOCK_TO_BB (current_loop_nest->header->index)));
5927 /* Support the situation when the latch block of outer loop
5928 could be from here. */
5929 for (outer = loop_outer (current_loop_nest);
5931 outer = loop_outer (outer))
5932 if (considered_for_pipelining_p (outer) && outer->latch == bb)
5939 /* Checks whether JUMP leads to basic block DEST_BB and no other blocks. */
5941 jump_leads_only_to_bb_p (insn_t jump, basic_block dest_bb)
5943 basic_block jump_bb = BLOCK_FOR_INSN (jump);
5945 /* It is not jump, jump with side-effects or jump can lead to several
5947 if (!onlyjump_p (jump)
5948 || !any_uncondjump_p (jump))
5951 /* Several outgoing edges, abnormal edge or destination of jump is
5953 if (EDGE_COUNT (jump_bb->succs) != 1
5954 || EDGE_SUCC (jump_bb, 0)->flags & EDGE_ABNORMAL
5955 || EDGE_SUCC (jump_bb, 0)->dest != dest_bb)
5958 /* If not anything of the upper. */
5962 /* Removes the loop preheader from the current region and saves it in
5963 PREHEADER_BLOCKS of the father loop, so they will be added later to
5964 region that represents an outer loop. */
5966 sel_remove_loop_preheader (void)
5969 int cur_rgn = CONTAINING_RGN (BB_TO_BLOCK (0));
5971 bool all_empty_p = true;
5972 VEC(basic_block, heap) *preheader_blocks
5973 = LOOP_PREHEADER_BLOCKS (loop_outer (current_loop_nest));
5975 gcc_assert (current_loop_nest);
5976 old_len = VEC_length (basic_block, preheader_blocks);
5978 /* Add blocks that aren't within the current loop to PREHEADER_BLOCKS. */
5979 for (i = 0; i < RGN_NR_BLOCKS (cur_rgn); i++)
5981 bb = BASIC_BLOCK (BB_TO_BLOCK (i));
5983 /* If the basic block belongs to region, but doesn't belong to
5984 corresponding loop, then it should be a preheader. */
5985 if (sel_is_loop_preheader_p (bb))
5987 VEC_safe_push (basic_block, heap, preheader_blocks, bb);
5988 if (BB_END (bb) != bb_note (bb))
5989 all_empty_p = false;
5993 /* Remove these blocks only after iterating over the whole region. */
5994 for (i = VEC_length (basic_block, preheader_blocks) - 1;
5998 bb = VEC_index (basic_block, preheader_blocks, i);
5999 sel_remove_bb (bb, false);
6002 if (!considered_for_pipelining_p (loop_outer (current_loop_nest)))
6005 /* Immediately create new region from preheader. */
6006 make_region_from_loop_preheader (&preheader_blocks);
6009 /* If all preheader blocks are empty - dont create new empty region.
6010 Instead, remove them completely. */
6011 for (i = 0; VEC_iterate (basic_block, preheader_blocks, i, bb); i++)
6015 basic_block prev_bb = bb->prev_bb, next_bb = bb->next_bb;
6017 /* Redirect all incoming edges to next basic block. */
6018 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
6020 if (! (e->flags & EDGE_FALLTHRU))
6021 redirect_edge_and_branch (e, bb->next_bb);
6023 redirect_edge_succ (e, bb->next_bb);
6025 gcc_assert (BB_NOTE_LIST (bb) == NULL);
6026 delete_and_free_basic_block (bb);
6028 /* Check if after deleting preheader there is a nonconditional
6029 jump in PREV_BB that leads to the next basic block NEXT_BB.
6030 If it is so - delete this jump and clear data sets of its
6031 basic block if it becomes empty. */
6032 if (next_bb->prev_bb == prev_bb
6033 && prev_bb != ENTRY_BLOCK_PTR
6034 && jump_leads_only_to_bb_p (BB_END (prev_bb), next_bb))
6036 redirect_edge_and_branch (EDGE_SUCC (prev_bb, 0), next_bb);
6037 if (BB_END (prev_bb) == bb_note (prev_bb))
6038 free_data_sets (prev_bb);
6042 VEC_free (basic_block, heap, preheader_blocks);
6045 /* Store preheader within the father's loop structure. */
6046 SET_LOOP_PREHEADER_BLOCKS (loop_outer (current_loop_nest),