1 /* Instruction scheduling pass. Selective scheduler and pipeliner.
2 Copyright (C) 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
27 #include "hard-reg-set.h"
31 #include "insn-config.h"
32 #include "insn-attr.h"
39 #include "tree-pass.h"
40 #include "sched-int.h"
44 #include "langhooks.h"
45 #include "rtlhooks-def.h"
47 #ifdef INSN_SCHEDULING
48 #include "sel-sched-ir.h"
49 /* We don't have to use it except for sel_print_insn. */
50 #include "sel-sched-dump.h"
52 /* A vector holding bb info for whole scheduling pass. */
53 VEC(sel_global_bb_info_def, heap) *sel_global_bb_info = NULL;
55 /* A vector holding bb info. */
56 VEC(sel_region_bb_info_def, heap) *sel_region_bb_info = NULL;
58 /* A pool for allocating all lists. */
59 alloc_pool sched_lists_pool;
61 /* This contains information about successors for compute_av_set. */
62 struct succs_info current_succs;
64 /* Data structure to describe interaction with the generic scheduler utils. */
65 static struct common_sched_info_def sel_common_sched_info;
67 /* The loop nest being pipelined. */
68 struct loop *current_loop_nest;
70 /* LOOP_NESTS is a vector containing the corresponding loop nest for
72 static VEC(loop_p, heap) *loop_nests = NULL;
74 /* Saves blocks already in loop regions, indexed by bb->index. */
75 static sbitmap bbs_in_loop_rgns = NULL;
77 /* CFG hooks that are saved before changing create_basic_block hook. */
78 static struct cfg_hooks orig_cfg_hooks;
81 /* Array containing reverse topological index of function basic blocks,
82 indexed by BB->INDEX. */
83 static int *rev_top_order_index = NULL;
85 /* Length of the above array. */
86 static int rev_top_order_index_len = -1;
88 /* A regset pool structure. */
91 /* The stack to which regsets are returned. */
100 /* In VV we save all generated regsets so that, when destructing the
101 pool, we can compare it with V and check that every regset was returned
105 /* The pointer of VV stack. */
111 /* The difference between allocated and returned regsets. */
113 } regset_pool = { NULL, 0, 0, NULL, 0, 0, 0 };
115 /* This represents the nop pool. */
118 /* The vector which holds previously emitted nops. */
126 } nop_pool = { NULL, 0, 0 };
128 /* The pool for basic block notes. */
129 static rtx_vec_t bb_note_pool;
131 /* A NOP pattern used to emit placeholder insns. */
132 rtx nop_pattern = NULL_RTX;
133 /* A special instruction that resides in EXIT_BLOCK.
134 EXIT_INSN is successor of the insns that lead to EXIT_BLOCK. */
135 rtx exit_insn = NULL_RTX;
137 /* TRUE if while scheduling current region, which is loop, its preheader
139 bool preheader_removed = false;
142 /* Forward static declarations. */
143 static void fence_clear (fence_t);
145 static void deps_init_id (idata_t, insn_t, bool);
146 static void init_id_from_df (idata_t, insn_t, bool);
147 static expr_t set_insn_init (expr_t, vinsn_t, int);
149 static void cfg_preds (basic_block, insn_t **, int *);
150 static void prepare_insn_expr (insn_t, int);
151 static void free_history_vect (VEC (expr_history_def, heap) **);
153 static void move_bb_info (basic_block, basic_block);
154 static void remove_empty_bb (basic_block, bool);
155 static void sel_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, int issue_more,
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_ISSUE_MORE (f) = issue_more;
290 FENCE_EXECUTING_INSNS (f) = executing_insns;
291 FENCE_READY_TICKS (f) = ready_ticks;
292 FENCE_READY_TICKS_SIZE (f) = ready_ticks_size;
293 FENCE_SCHED_NEXT (f) = sched_next;
295 init_fence_for_scheduling (f);
298 /* Remove the head node of the list pointed to by LP. */
300 flist_remove (flist_t *lp)
302 if (FENCE_INSN (FLIST_FENCE (*lp)))
303 fence_clear (FLIST_FENCE (*lp));
307 /* Clear the fence list pointed to by LP. */
309 flist_clear (flist_t *lp)
315 /* Add ORIGINAL_INSN the def list DL honoring CROSSES_CALL. */
317 def_list_add (def_list_t *dl, insn_t original_insn, bool crosses_call)
322 d = DEF_LIST_DEF (*dl);
324 d->orig_insn = original_insn;
325 d->crosses_call = crosses_call;
329 /* Functions to work with target contexts. */
331 /* Bulk target context. It is convenient for debugging purposes to ensure
332 that there are no uninitialized (null) target contexts. */
333 static tc_t bulk_tc = (tc_t) 1;
335 /* Target hooks wrappers. In the future we can provide some default
336 implementations for them. */
338 /* Allocate a store for the target context. */
340 alloc_target_context (void)
342 return (targetm.sched.alloc_sched_context
343 ? targetm.sched.alloc_sched_context () : bulk_tc);
346 /* Init target context TC.
347 If CLEAN_P is true, then make TC as it is beginning of the scheduler.
348 Overwise, copy current backend context to TC. */
350 init_target_context (tc_t tc, bool clean_p)
352 if (targetm.sched.init_sched_context)
353 targetm.sched.init_sched_context (tc, clean_p);
356 /* Allocate and initialize a target context. Meaning of CLEAN_P is the same as
357 int init_target_context (). */
359 create_target_context (bool clean_p)
361 tc_t tc = alloc_target_context ();
363 init_target_context (tc, clean_p);
367 /* Copy TC to the current backend context. */
369 set_target_context (tc_t tc)
371 if (targetm.sched.set_sched_context)
372 targetm.sched.set_sched_context (tc);
375 /* TC is about to be destroyed. Free any internal data. */
377 clear_target_context (tc_t tc)
379 if (targetm.sched.clear_sched_context)
380 targetm.sched.clear_sched_context (tc);
383 /* Clear and free it. */
385 delete_target_context (tc_t tc)
387 clear_target_context (tc);
389 if (targetm.sched.free_sched_context)
390 targetm.sched.free_sched_context (tc);
393 /* Make a copy of FROM in TO.
394 NB: May be this should be a hook. */
396 copy_target_context (tc_t to, tc_t from)
398 tc_t tmp = create_target_context (false);
400 set_target_context (from);
401 init_target_context (to, false);
403 set_target_context (tmp);
404 delete_target_context (tmp);
407 /* Create a copy of TC. */
409 create_copy_of_target_context (tc_t tc)
411 tc_t copy = alloc_target_context ();
413 copy_target_context (copy, tc);
418 /* Clear TC and initialize it according to CLEAN_P. The meaning of CLEAN_P
419 is the same as in init_target_context (). */
421 reset_target_context (tc_t tc, bool clean_p)
423 clear_target_context (tc);
424 init_target_context (tc, clean_p);
427 /* Functions to work with dependence contexts.
428 Dc (aka deps context, aka deps_t, aka struct deps *) is short for dependence
429 context. It accumulates information about processed insns to decide if
430 current insn is dependent on the processed ones. */
432 /* Make a copy of FROM in TO. */
434 copy_deps_context (deps_t to, deps_t from)
436 init_deps (to, false);
437 deps_join (to, from);
440 /* Allocate store for dep context. */
442 alloc_deps_context (void)
444 return XNEW (struct deps);
447 /* Allocate and initialize dep context. */
449 create_deps_context (void)
451 deps_t dc = alloc_deps_context ();
453 init_deps (dc, false);
457 /* Create a copy of FROM. */
459 create_copy_of_deps_context (deps_t from)
461 deps_t to = alloc_deps_context ();
463 copy_deps_context (to, from);
467 /* Clean up internal data of DC. */
469 clear_deps_context (deps_t dc)
474 /* Clear and free DC. */
476 delete_deps_context (deps_t dc)
478 clear_deps_context (dc);
482 /* Clear and init DC. */
484 reset_deps_context (deps_t dc)
486 clear_deps_context (dc);
487 init_deps (dc, false);
490 /* This structure describes the dependence analysis hooks for advancing
491 dependence context. */
492 static struct sched_deps_info_def advance_deps_context_sched_deps_info =
496 NULL, /* start_insn */
497 NULL, /* finish_insn */
498 NULL, /* start_lhs */
499 NULL, /* finish_lhs */
500 NULL, /* start_rhs */
501 NULL, /* finish_rhs */
503 haifa_note_reg_clobber,
505 NULL, /* note_mem_dep */
511 /* Process INSN and add its impact on DC. */
513 advance_deps_context (deps_t dc, insn_t insn)
515 sched_deps_info = &advance_deps_context_sched_deps_info;
516 deps_analyze_insn (dc, insn);
520 /* Functions to work with DFA states. */
522 /* Allocate store for a DFA state. */
526 return xmalloc (dfa_state_size);
529 /* Allocate and initialize DFA state. */
533 state_t state = state_alloc ();
536 advance_state (state);
540 /* Free DFA state. */
542 state_free (state_t state)
547 /* Make a copy of FROM in TO. */
549 state_copy (state_t to, state_t from)
551 memcpy (to, from, dfa_state_size);
554 /* Create a copy of FROM. */
556 state_create_copy (state_t from)
558 state_t to = state_alloc ();
560 state_copy (to, from);
565 /* Functions to work with fences. */
567 /* Clear the fence. */
569 fence_clear (fence_t f)
571 state_t s = FENCE_STATE (f);
572 deps_t dc = FENCE_DC (f);
573 void *tc = FENCE_TC (f);
575 ilist_clear (&FENCE_BNDS (f));
577 gcc_assert ((s != NULL && dc != NULL && tc != NULL)
578 || (s == NULL && dc == NULL && tc == NULL));
584 delete_deps_context (dc);
587 delete_target_context (tc);
588 VEC_free (rtx, gc, FENCE_EXECUTING_INSNS (f));
589 free (FENCE_READY_TICKS (f));
590 FENCE_READY_TICKS (f) = NULL;
593 /* Init a list of fences with successors of OLD_FENCE. */
595 init_fences (insn_t old_fence)
600 int ready_ticks_size = get_max_uid () + 1;
602 FOR_EACH_SUCC_1 (succ, si, old_fence,
603 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
609 gcc_assert (flag_sel_sched_pipelining_outer_loops);
611 flist_add (&fences, succ,
613 create_deps_context () /* dc */,
614 create_target_context (true) /* tc */,
615 NULL_RTX /* last_scheduled_insn */,
616 NULL, /* executing_insns */
617 XCNEWVEC (int, ready_ticks_size), /* ready_ticks */
619 NULL_RTX /* sched_next */,
620 1 /* cycle */, 0 /* cycle_issued_insns */,
621 issue_rate, /* issue_more */
622 1 /* starts_cycle_p */, 0 /* after_stall_p */);
626 /* Merges two fences (filling fields of fence F with resulting values) by
627 following rules: 1) state, target context and last scheduled insn are
628 propagated from fallthrough edge if it is available;
629 2) deps context and cycle is propagated from more probable edge;
630 3) all other fields are set to corresponding constant values.
632 INSN, STATE, DC, TC, LAST_SCHEDULED_INSN, EXECUTING_INSNS,
633 READY_TICKS, READY_TICKS_SIZE, SCHED_NEXT, CYCLE, ISSUE_MORE
634 and AFTER_STALL_P are the corresponding fields of the second fence. */
636 merge_fences (fence_t f, insn_t insn,
637 state_t state, deps_t dc, void *tc,
638 rtx last_scheduled_insn, VEC(rtx, gc) *executing_insns,
639 int *ready_ticks, int ready_ticks_size,
640 rtx sched_next, int cycle, int issue_more, bool after_stall_p)
642 insn_t last_scheduled_insn_old = FENCE_LAST_SCHEDULED_INSN (f);
644 gcc_assert (sel_bb_head_p (FENCE_INSN (f))
645 && !sched_next && !FENCE_SCHED_NEXT (f));
647 /* Check if we can decide which path fences came.
648 If we can't (or don't want to) - reset all. */
649 if (last_scheduled_insn == NULL
650 || last_scheduled_insn_old == NULL
651 /* This is a case when INSN is reachable on several paths from
652 one insn (this can happen when pipelining of outer loops is on and
653 there are two edges: one going around of inner loop and the other -
654 right through it; in such case just reset everything). */
655 || last_scheduled_insn == last_scheduled_insn_old)
657 state_reset (FENCE_STATE (f));
660 reset_deps_context (FENCE_DC (f));
661 delete_deps_context (dc);
663 reset_target_context (FENCE_TC (f), true);
664 delete_target_context (tc);
666 if (cycle > FENCE_CYCLE (f))
667 FENCE_CYCLE (f) = cycle;
669 FENCE_LAST_SCHEDULED_INSN (f) = NULL;
670 FENCE_ISSUE_MORE (f) = issue_rate;
671 VEC_free (rtx, gc, executing_insns);
673 if (FENCE_EXECUTING_INSNS (f))
674 VEC_block_remove (rtx, FENCE_EXECUTING_INSNS (f), 0,
675 VEC_length (rtx, FENCE_EXECUTING_INSNS (f)));
676 if (FENCE_READY_TICKS (f))
677 memset (FENCE_READY_TICKS (f), 0, FENCE_READY_TICKS_SIZE (f));
681 edge edge_old = NULL, edge_new = NULL;
686 /* Find fallthrough edge. */
687 gcc_assert (BLOCK_FOR_INSN (insn)->prev_bb);
688 candidate = find_fallthru_edge (BLOCK_FOR_INSN (insn)->prev_bb);
691 || (candidate->src != BLOCK_FOR_INSN (last_scheduled_insn)
692 && candidate->src != BLOCK_FOR_INSN (last_scheduled_insn_old)))
694 /* No fallthrough edge leading to basic block of INSN. */
695 state_reset (FENCE_STATE (f));
698 reset_target_context (FENCE_TC (f), true);
699 delete_target_context (tc);
701 FENCE_LAST_SCHEDULED_INSN (f) = NULL;
702 FENCE_ISSUE_MORE (f) = issue_rate;
705 if (candidate->src == BLOCK_FOR_INSN (last_scheduled_insn))
707 /* Would be weird if same insn is successor of several fallthrough
709 gcc_assert (BLOCK_FOR_INSN (insn)->prev_bb
710 != BLOCK_FOR_INSN (last_scheduled_insn_old));
712 state_free (FENCE_STATE (f));
713 FENCE_STATE (f) = state;
715 delete_target_context (FENCE_TC (f));
718 FENCE_LAST_SCHEDULED_INSN (f) = last_scheduled_insn;
719 FENCE_ISSUE_MORE (f) = issue_more;
723 /* Leave STATE, TC and LAST_SCHEDULED_INSN fields untouched. */
725 delete_target_context (tc);
727 gcc_assert (BLOCK_FOR_INSN (insn)->prev_bb
728 != BLOCK_FOR_INSN (last_scheduled_insn));
731 /* Find edge of first predecessor (last_scheduled_insn_old->insn). */
732 FOR_EACH_SUCC_1 (succ, si, last_scheduled_insn_old,
733 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
737 /* No same successor allowed from several edges. */
738 gcc_assert (!edge_old);
742 /* Find edge of second predecessor (last_scheduled_insn->insn). */
743 FOR_EACH_SUCC_1 (succ, si, last_scheduled_insn,
744 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
748 /* No same successor allowed from several edges. */
749 gcc_assert (!edge_new);
754 /* Check if we can choose most probable predecessor. */
755 if (edge_old == NULL || edge_new == NULL)
757 reset_deps_context (FENCE_DC (f));
758 delete_deps_context (dc);
759 VEC_free (rtx, gc, executing_insns);
762 FENCE_CYCLE (f) = MAX (FENCE_CYCLE (f), cycle);
763 if (FENCE_EXECUTING_INSNS (f))
764 VEC_block_remove (rtx, FENCE_EXECUTING_INSNS (f), 0,
765 VEC_length (rtx, FENCE_EXECUTING_INSNS (f)));
766 if (FENCE_READY_TICKS (f))
767 memset (FENCE_READY_TICKS (f), 0, FENCE_READY_TICKS_SIZE (f));
770 if (edge_new->probability > edge_old->probability)
772 delete_deps_context (FENCE_DC (f));
774 VEC_free (rtx, gc, FENCE_EXECUTING_INSNS (f));
775 FENCE_EXECUTING_INSNS (f) = executing_insns;
776 free (FENCE_READY_TICKS (f));
777 FENCE_READY_TICKS (f) = ready_ticks;
778 FENCE_READY_TICKS_SIZE (f) = ready_ticks_size;
779 FENCE_CYCLE (f) = cycle;
783 /* Leave DC and CYCLE untouched. */
784 delete_deps_context (dc);
785 VEC_free (rtx, gc, executing_insns);
790 /* Fill remaining invariant fields. */
792 FENCE_AFTER_STALL_P (f) = 1;
794 FENCE_ISSUED_INSNS (f) = 0;
795 FENCE_STARTS_CYCLE_P (f) = 1;
796 FENCE_SCHED_NEXT (f) = NULL;
799 /* Add a new fence to NEW_FENCES list, initializing it from all
802 add_to_fences (flist_tail_t new_fences, insn_t insn,
803 state_t state, deps_t dc, void *tc, rtx last_scheduled_insn,
804 VEC(rtx, gc) *executing_insns, int *ready_ticks,
805 int ready_ticks_size, rtx sched_next, int cycle,
806 int cycle_issued_insns, int issue_rate,
807 bool starts_cycle_p, bool after_stall_p)
809 fence_t f = flist_lookup (FLIST_TAIL_HEAD (new_fences), insn);
813 flist_add (FLIST_TAIL_TAILP (new_fences), insn, state, dc, tc,
814 last_scheduled_insn, executing_insns, ready_ticks,
815 ready_ticks_size, sched_next, cycle, cycle_issued_insns,
816 issue_rate, starts_cycle_p, after_stall_p);
818 FLIST_TAIL_TAILP (new_fences)
819 = &FLIST_NEXT (*FLIST_TAIL_TAILP (new_fences));
823 merge_fences (f, insn, state, dc, tc, last_scheduled_insn,
824 executing_insns, ready_ticks, ready_ticks_size,
825 sched_next, cycle, issue_rate, after_stall_p);
829 /* Move the first fence in the OLD_FENCES list to NEW_FENCES. */
831 move_fence_to_fences (flist_t old_fences, flist_tail_t new_fences)
834 flist_t *tailp = FLIST_TAIL_TAILP (new_fences);
836 old = FLIST_FENCE (old_fences);
837 f = flist_lookup (FLIST_TAIL_HEAD (new_fences),
838 FENCE_INSN (FLIST_FENCE (old_fences)));
841 merge_fences (f, old->insn, old->state, old->dc, old->tc,
842 old->last_scheduled_insn, old->executing_insns,
843 old->ready_ticks, old->ready_ticks_size,
844 old->sched_next, old->cycle, old->issue_more,
850 FLIST_TAIL_TAILP (new_fences) = &FLIST_NEXT (*tailp);
851 *FLIST_FENCE (*tailp) = *old;
852 init_fence_for_scheduling (FLIST_FENCE (*tailp));
854 FENCE_INSN (old) = NULL;
857 /* Add a new fence to NEW_FENCES list and initialize most of its data
860 add_clean_fence_to_fences (flist_tail_t new_fences, insn_t succ, fence_t fence)
862 int ready_ticks_size = get_max_uid () + 1;
864 add_to_fences (new_fences,
865 succ, state_create (), create_deps_context (),
866 create_target_context (true),
868 XCNEWVEC (int, ready_ticks_size), ready_ticks_size,
869 NULL_RTX, FENCE_CYCLE (fence) + 1,
870 0, issue_rate, 1, FENCE_AFTER_STALL_P (fence));
873 /* Add a new fence to NEW_FENCES list and initialize all of its data
874 from FENCE and SUCC. */
876 add_dirty_fence_to_fences (flist_tail_t new_fences, insn_t succ, fence_t fence)
878 int * new_ready_ticks
879 = XNEWVEC (int, FENCE_READY_TICKS_SIZE (fence));
881 memcpy (new_ready_ticks, FENCE_READY_TICKS (fence),
882 FENCE_READY_TICKS_SIZE (fence) * sizeof (int));
883 add_to_fences (new_fences,
884 succ, state_create_copy (FENCE_STATE (fence)),
885 create_copy_of_deps_context (FENCE_DC (fence)),
886 create_copy_of_target_context (FENCE_TC (fence)),
887 FENCE_LAST_SCHEDULED_INSN (fence),
888 VEC_copy (rtx, gc, FENCE_EXECUTING_INSNS (fence)),
890 FENCE_READY_TICKS_SIZE (fence),
891 FENCE_SCHED_NEXT (fence),
893 FENCE_ISSUED_INSNS (fence),
894 FENCE_ISSUE_MORE (fence),
895 FENCE_STARTS_CYCLE_P (fence),
896 FENCE_AFTER_STALL_P (fence));
900 /* Functions to work with regset and nop pools. */
902 /* Returns the new regset from pool. It might have some of the bits set
903 from the previous usage. */
905 get_regset_from_pool (void)
909 if (regset_pool.n != 0)
910 rs = regset_pool.v[--regset_pool.n];
912 /* We need to create the regset. */
914 rs = ALLOC_REG_SET (®_obstack);
916 if (regset_pool.nn == regset_pool.ss)
917 regset_pool.vv = XRESIZEVEC (regset, regset_pool.vv,
918 (regset_pool.ss = 2 * regset_pool.ss + 1));
919 regset_pool.vv[regset_pool.nn++] = rs;
927 /* Same as above, but returns the empty regset. */
929 get_clear_regset_from_pool (void)
931 regset rs = get_regset_from_pool ();
937 /* Return regset RS to the pool for future use. */
939 return_regset_to_pool (regset rs)
943 if (regset_pool.n == regset_pool.s)
944 regset_pool.v = XRESIZEVEC (regset, regset_pool.v,
945 (regset_pool.s = 2 * regset_pool.s + 1));
946 regset_pool.v[regset_pool.n++] = rs;
949 #ifdef ENABLE_CHECKING
950 /* This is used as a qsort callback for sorting regset pool stacks.
951 X and XX are addresses of two regsets. They are never equal. */
953 cmp_v_in_regset_pool (const void *x, const void *xx)
955 return *((const regset *) x) - *((const regset *) xx);
959 /* Free the regset pool possibly checking for memory leaks. */
961 free_regset_pool (void)
963 #ifdef ENABLE_CHECKING
965 regset *v = regset_pool.v;
967 int n = regset_pool.n;
969 regset *vv = regset_pool.vv;
971 int nn = regset_pool.nn;
975 gcc_assert (n <= nn);
977 /* Sort both vectors so it will be possible to compare them. */
978 qsort (v, n, sizeof (*v), cmp_v_in_regset_pool);
979 qsort (vv, nn, sizeof (*vv), cmp_v_in_regset_pool);
986 /* VV[II] was lost. */
992 gcc_assert (diff == regset_pool.diff);
996 /* If not true - we have a memory leak. */
997 gcc_assert (regset_pool.diff == 0);
999 while (regset_pool.n)
1002 FREE_REG_SET (regset_pool.v[regset_pool.n]);
1005 free (regset_pool.v);
1006 regset_pool.v = NULL;
1009 free (regset_pool.vv);
1010 regset_pool.vv = NULL;
1014 regset_pool.diff = 0;
1018 /* Functions to work with nop pools. NOP insns are used as temporary
1019 placeholders of the insns being scheduled to allow correct update of
1020 the data sets. When update is finished, NOPs are deleted. */
1022 /* A vinsn that is used to represent a nop. This vinsn is shared among all
1023 nops sel-sched generates. */
1024 static vinsn_t nop_vinsn = NULL;
1026 /* Emit a nop before INSN, taking it from pool. */
1028 get_nop_from_pool (insn_t insn)
1031 bool old_p = nop_pool.n != 0;
1035 nop = nop_pool.v[--nop_pool.n];
1039 nop = emit_insn_before (nop, insn);
1042 flags = INSN_INIT_TODO_SSID;
1044 flags = INSN_INIT_TODO_LUID | INSN_INIT_TODO_SSID;
1046 set_insn_init (INSN_EXPR (insn), nop_vinsn, INSN_SEQNO (insn));
1047 sel_init_new_insn (nop, flags);
1052 /* Remove NOP from the instruction stream and return it to the pool. */
1054 return_nop_to_pool (insn_t nop)
1056 gcc_assert (INSN_IN_STREAM_P (nop));
1057 sel_remove_insn (nop, false, true);
1059 if (nop_pool.n == nop_pool.s)
1060 nop_pool.v = XRESIZEVEC (rtx, nop_pool.v,
1061 (nop_pool.s = 2 * nop_pool.s + 1));
1062 nop_pool.v[nop_pool.n++] = nop;
1065 /* Free the nop pool. */
1067 free_nop_pool (void)
1076 /* Skip unspec to support ia64 speculation. Called from rtx_equal_p_cb.
1077 The callback is given two rtxes XX and YY and writes the new rtxes
1078 to NX and NY in case some needs to be skipped. */
1080 skip_unspecs_callback (const_rtx *xx, const_rtx *yy, rtx *nx, rtx* ny)
1085 if (GET_CODE (x) == UNSPEC
1086 && (targetm.sched.skip_rtx_p == NULL
1087 || targetm.sched.skip_rtx_p (x)))
1089 *nx = XVECEXP (x, 0, 0);
1090 *ny = CONST_CAST_RTX (y);
1094 if (GET_CODE (y) == UNSPEC
1095 && (targetm.sched.skip_rtx_p == NULL
1096 || targetm.sched.skip_rtx_p (y)))
1098 *nx = CONST_CAST_RTX (x);
1099 *ny = XVECEXP (y, 0, 0);
1106 /* Callback, called from hash_rtx_cb. Helps to hash UNSPEC rtx X in a correct way
1107 to support ia64 speculation. When changes are needed, new rtx X and new mode
1108 NMODE are written, and the callback returns true. */
1110 hash_with_unspec_callback (const_rtx x, enum machine_mode mode ATTRIBUTE_UNUSED,
1111 rtx *nx, enum machine_mode* nmode)
1113 if (GET_CODE (x) == UNSPEC
1114 && targetm.sched.skip_rtx_p
1115 && targetm.sched.skip_rtx_p (x))
1117 *nx = XVECEXP (x, 0 ,0);
1125 /* Returns LHS and RHS are ok to be scheduled separately. */
1127 lhs_and_rhs_separable_p (rtx lhs, rtx rhs)
1129 if (lhs == NULL || rhs == NULL)
1132 /* Do not schedule CONST, CONST_INT and CONST_DOUBLE etc as rhs: no point
1133 to use reg, if const can be used. Moreover, scheduling const as rhs may
1134 lead to mode mismatch cause consts don't have modes but they could be
1135 merged from branches where the same const used in different modes. */
1136 if (CONSTANT_P (rhs))
1139 /* ??? Do not rename predicate registers to avoid ICEs in bundling. */
1140 if (COMPARISON_P (rhs))
1143 /* Do not allow single REG to be an rhs. */
1147 /* See comment at find_used_regs_1 (*1) for explanation of this
1149 /* FIXME: remove this later. */
1153 /* This will filter all tricky things like ZERO_EXTRACT etc.
1154 For now we don't handle it. */
1155 if (!REG_P (lhs) && !MEM_P (lhs))
1161 /* Initialize vinsn VI for INSN. Only for use from vinsn_create (). When
1162 FORCE_UNIQUE_P is true, the resulting vinsn will not be clonable. This is
1163 used e.g. for insns from recovery blocks. */
1165 vinsn_init (vinsn_t vi, insn_t insn, bool force_unique_p)
1167 hash_rtx_callback_function hrcf;
1170 VINSN_INSN_RTX (vi) = insn;
1171 VINSN_COUNT (vi) = 0;
1174 if (DF_INSN_UID_SAFE_GET (INSN_UID (insn)) != NULL)
1175 init_id_from_df (VINSN_ID (vi), insn, force_unique_p);
1177 deps_init_id (VINSN_ID (vi), insn, force_unique_p);
1179 /* Hash vinsn depending on whether it is separable or not. */
1180 hrcf = targetm.sched.skip_rtx_p ? hash_with_unspec_callback : NULL;
1181 if (VINSN_SEPARABLE_P (vi))
1183 rtx rhs = VINSN_RHS (vi);
1185 VINSN_HASH (vi) = hash_rtx_cb (rhs, GET_MODE (rhs),
1186 NULL, NULL, false, hrcf);
1187 VINSN_HASH_RTX (vi) = hash_rtx_cb (VINSN_PATTERN (vi),
1188 VOIDmode, NULL, NULL,
1193 VINSN_HASH (vi) = hash_rtx_cb (VINSN_PATTERN (vi), VOIDmode,
1194 NULL, NULL, false, hrcf);
1195 VINSN_HASH_RTX (vi) = VINSN_HASH (vi);
1198 insn_class = haifa_classify_insn (insn);
1200 && (!targetm.sched.get_insn_spec_ds
1201 || ((targetm.sched.get_insn_spec_ds (insn) & BEGIN_CONTROL)
1203 VINSN_MAY_TRAP_P (vi) = true;
1205 VINSN_MAY_TRAP_P (vi) = false;
1208 /* Indicate that VI has become the part of an rtx object. */
1210 vinsn_attach (vinsn_t vi)
1212 /* Assert that VI is not pending for deletion. */
1213 gcc_assert (VINSN_INSN_RTX (vi));
1218 /* Create and init VI from the INSN. Use UNIQUE_P for determining the correct
1221 vinsn_create (insn_t insn, bool force_unique_p)
1223 vinsn_t vi = XCNEW (struct vinsn_def);
1225 vinsn_init (vi, insn, force_unique_p);
1229 /* Return a copy of VI. When REATTACH_P is true, detach VI and attach
1232 vinsn_copy (vinsn_t vi, bool reattach_p)
1235 bool unique = VINSN_UNIQUE_P (vi);
1238 copy = create_copy_of_insn_rtx (VINSN_INSN_RTX (vi));
1239 new_vi = create_vinsn_from_insn_rtx (copy, unique);
1243 vinsn_attach (new_vi);
1249 /* Delete the VI vinsn and free its data. */
1251 vinsn_delete (vinsn_t vi)
1253 gcc_assert (VINSN_COUNT (vi) == 0);
1255 return_regset_to_pool (VINSN_REG_SETS (vi));
1256 return_regset_to_pool (VINSN_REG_USES (vi));
1257 return_regset_to_pool (VINSN_REG_CLOBBERS (vi));
1262 /* Indicate that VI is no longer a part of some rtx object.
1263 Remove VI if it is no longer needed. */
1265 vinsn_detach (vinsn_t vi)
1267 gcc_assert (VINSN_COUNT (vi) > 0);
1269 if (--VINSN_COUNT (vi) == 0)
1273 /* Returns TRUE if VI is a branch. */
1275 vinsn_cond_branch_p (vinsn_t vi)
1279 if (!VINSN_UNIQUE_P (vi))
1282 insn = VINSN_INSN_RTX (vi);
1283 if (BB_END (BLOCK_FOR_INSN (insn)) != insn)
1286 return control_flow_insn_p (insn);
1289 /* Return latency of INSN. */
1291 sel_insn_rtx_cost (rtx insn)
1295 /* A USE insn, or something else we don't need to
1296 understand. We can't pass these directly to
1297 result_ready_cost or insn_default_latency because it will
1298 trigger a fatal error for unrecognizable insns. */
1299 if (recog_memoized (insn) < 0)
1303 cost = insn_default_latency (insn);
1312 /* Return the cost of the VI.
1313 !!! FIXME: Unify with haifa-sched.c: insn_cost (). */
1315 sel_vinsn_cost (vinsn_t vi)
1317 int cost = vi->cost;
1321 cost = sel_insn_rtx_cost (VINSN_INSN_RTX (vi));
1329 /* Functions for insn emitting. */
1331 /* Emit new insn after AFTER based on PATTERN and initialize its data from
1334 sel_gen_insn_from_rtx_after (rtx pattern, expr_t expr, int seqno, insn_t after)
1338 gcc_assert (EXPR_TARGET_AVAILABLE (expr) == true);
1340 new_insn = emit_insn_after (pattern, after);
1341 set_insn_init (expr, NULL, seqno);
1342 sel_init_new_insn (new_insn, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SSID);
1347 /* Force newly generated vinsns to be unique. */
1348 static bool init_insn_force_unique_p = false;
1350 /* Emit new speculation recovery insn after AFTER based on PATTERN and
1351 initialize its data from EXPR and SEQNO. */
1353 sel_gen_recovery_insn_from_rtx_after (rtx pattern, expr_t expr, int seqno,
1358 gcc_assert (!init_insn_force_unique_p);
1360 init_insn_force_unique_p = true;
1361 insn = sel_gen_insn_from_rtx_after (pattern, expr, seqno, after);
1362 CANT_MOVE (insn) = 1;
1363 init_insn_force_unique_p = false;
1368 /* Emit new insn after AFTER based on EXPR and SEQNO. If VINSN is not NULL,
1369 take it as a new vinsn instead of EXPR's vinsn.
1370 We simplify insns later, after scheduling region in
1371 simplify_changed_insns. */
1373 sel_gen_insn_from_expr_after (expr_t expr, vinsn_t vinsn, int seqno,
1380 emit_expr = set_insn_init (expr, vinsn ? vinsn : EXPR_VINSN (expr),
1382 insn = EXPR_INSN_RTX (emit_expr);
1383 add_insn_after (insn, after, BLOCK_FOR_INSN (insn));
1385 flags = INSN_INIT_TODO_SSID;
1386 if (INSN_LUID (insn) == 0)
1387 flags |= INSN_INIT_TODO_LUID;
1388 sel_init_new_insn (insn, flags);
1393 /* Move insn from EXPR after AFTER. */
1395 sel_move_insn (expr_t expr, int seqno, insn_t after)
1397 insn_t insn = EXPR_INSN_RTX (expr);
1398 basic_block bb = BLOCK_FOR_INSN (after);
1399 insn_t next = NEXT_INSN (after);
1401 /* Assert that in move_op we disconnected this insn properly. */
1402 gcc_assert (EXPR_VINSN (INSN_EXPR (insn)) != NULL);
1403 PREV_INSN (insn) = after;
1404 NEXT_INSN (insn) = next;
1406 NEXT_INSN (after) = insn;
1407 PREV_INSN (next) = insn;
1409 /* Update links from insn to bb and vice versa. */
1410 df_insn_change_bb (insn, bb);
1411 if (BB_END (bb) == after)
1414 prepare_insn_expr (insn, seqno);
1419 /* Functions to work with right-hand sides. */
1421 /* Search for a hash value determined by UID/NEW_VINSN in a sorted vector
1422 VECT and return true when found. Use NEW_VINSN for comparison only when
1423 COMPARE_VINSNS is true. Write to INDP the index on which
1424 the search has stopped, such that inserting the new element at INDP will
1425 retain VECT's sort order. */
1427 find_in_history_vect_1 (VEC(expr_history_def, heap) *vect,
1428 unsigned uid, vinsn_t new_vinsn,
1429 bool compare_vinsns, int *indp)
1431 expr_history_def *arr;
1432 int i, j, len = VEC_length (expr_history_def, vect);
1440 arr = VEC_address (expr_history_def, vect);
1445 unsigned auid = arr[i].uid;
1446 vinsn_t avinsn = arr[i].new_expr_vinsn;
1449 /* When undoing transformation on a bookkeeping copy, the new vinsn
1450 may not be exactly equal to the one that is saved in the vector.
1451 This is because the insn whose copy we're checking was possibly
1452 substituted itself. */
1453 && (! compare_vinsns
1454 || vinsn_equal_p (avinsn, new_vinsn)))
1459 else if (auid > uid)
1468 /* Search for a uid of INSN and NEW_VINSN in a sorted vector VECT. Return
1469 the position found or -1, if no such value is in vector.
1470 Search also for UIDs of insn's originators, if ORIGINATORS_P is true. */
1472 find_in_history_vect (VEC(expr_history_def, heap) *vect, rtx insn,
1473 vinsn_t new_vinsn, bool originators_p)
1477 if (find_in_history_vect_1 (vect, INSN_UID (insn), new_vinsn,
1481 if (INSN_ORIGINATORS (insn) && originators_p)
1486 EXECUTE_IF_SET_IN_BITMAP (INSN_ORIGINATORS (insn), 0, uid, bi)
1487 if (find_in_history_vect_1 (vect, uid, new_vinsn, false, &ind))
1494 /* Insert new element in a sorted history vector pointed to by PVECT,
1495 if it is not there already. The element is searched using
1496 UID/NEW_EXPR_VINSN pair. TYPE, OLD_EXPR_VINSN and SPEC_DS save
1497 the history of a transformation. */
1499 insert_in_history_vect (VEC (expr_history_def, heap) **pvect,
1500 unsigned uid, enum local_trans_type type,
1501 vinsn_t old_expr_vinsn, vinsn_t new_expr_vinsn,
1504 VEC(expr_history_def, heap) *vect = *pvect;
1505 expr_history_def temp;
1509 res = find_in_history_vect_1 (vect, uid, new_expr_vinsn, true, &ind);
1513 expr_history_def *phist = VEC_index (expr_history_def, vect, ind);
1515 /* It is possible that speculation types of expressions that were
1516 propagated through different paths will be different here. In this
1517 case, merge the status to get the correct check later. */
1518 if (phist->spec_ds != spec_ds)
1519 phist->spec_ds = ds_max_merge (phist->spec_ds, spec_ds);
1524 temp.old_expr_vinsn = old_expr_vinsn;
1525 temp.new_expr_vinsn = new_expr_vinsn;
1526 temp.spec_ds = spec_ds;
1529 vinsn_attach (old_expr_vinsn);
1530 vinsn_attach (new_expr_vinsn);
1531 VEC_safe_insert (expr_history_def, heap, vect, ind, &temp);
1535 /* Free history vector PVECT. */
1537 free_history_vect (VEC (expr_history_def, heap) **pvect)
1540 expr_history_def *phist;
1546 VEC_iterate (expr_history_def, *pvect, i, phist);
1549 vinsn_detach (phist->old_expr_vinsn);
1550 vinsn_detach (phist->new_expr_vinsn);
1553 VEC_free (expr_history_def, heap, *pvect);
1558 /* Compare two vinsns as rhses if possible and as vinsns otherwise. */
1560 vinsn_equal_p (vinsn_t x, vinsn_t y)
1562 rtx_equal_p_callback_function repcf;
1567 if (VINSN_TYPE (x) != VINSN_TYPE (y))
1570 if (VINSN_HASH (x) != VINSN_HASH (y))
1573 repcf = targetm.sched.skip_rtx_p ? skip_unspecs_callback : NULL;
1574 if (VINSN_SEPARABLE_P (x))
1576 /* Compare RHSes of VINSNs. */
1577 gcc_assert (VINSN_RHS (x));
1578 gcc_assert (VINSN_RHS (y));
1580 return rtx_equal_p_cb (VINSN_RHS (x), VINSN_RHS (y), repcf);
1583 return rtx_equal_p_cb (VINSN_PATTERN (x), VINSN_PATTERN (y), repcf);
1587 /* Functions for working with expressions. */
1589 /* Initialize EXPR. */
1591 init_expr (expr_t expr, vinsn_t vi, int spec, int use, int priority,
1592 int sched_times, int orig_bb_index, ds_t spec_done_ds,
1593 ds_t spec_to_check_ds, int orig_sched_cycle,
1594 VEC(expr_history_def, heap) *history, bool target_available,
1595 bool was_substituted, bool was_renamed, bool needs_spec_check_p,
1600 EXPR_VINSN (expr) = vi;
1601 EXPR_SPEC (expr) = spec;
1602 EXPR_USEFULNESS (expr) = use;
1603 EXPR_PRIORITY (expr) = priority;
1604 EXPR_PRIORITY_ADJ (expr) = 0;
1605 EXPR_SCHED_TIMES (expr) = sched_times;
1606 EXPR_ORIG_BB_INDEX (expr) = orig_bb_index;
1607 EXPR_ORIG_SCHED_CYCLE (expr) = orig_sched_cycle;
1608 EXPR_SPEC_DONE_DS (expr) = spec_done_ds;
1609 EXPR_SPEC_TO_CHECK_DS (expr) = spec_to_check_ds;
1612 EXPR_HISTORY_OF_CHANGES (expr) = history;
1614 EXPR_HISTORY_OF_CHANGES (expr) = NULL;
1616 EXPR_TARGET_AVAILABLE (expr) = target_available;
1617 EXPR_WAS_SUBSTITUTED (expr) = was_substituted;
1618 EXPR_WAS_RENAMED (expr) = was_renamed;
1619 EXPR_NEEDS_SPEC_CHECK_P (expr) = needs_spec_check_p;
1620 EXPR_CANT_MOVE (expr) = cant_move;
1623 /* Make a copy of the expr FROM into the expr TO. */
1625 copy_expr (expr_t to, expr_t from)
1627 VEC(expr_history_def, heap) *temp = NULL;
1629 if (EXPR_HISTORY_OF_CHANGES (from))
1632 expr_history_def *phist;
1634 temp = VEC_copy (expr_history_def, heap, EXPR_HISTORY_OF_CHANGES (from));
1636 VEC_iterate (expr_history_def, temp, i, phist);
1639 vinsn_attach (phist->old_expr_vinsn);
1640 vinsn_attach (phist->new_expr_vinsn);
1644 init_expr (to, EXPR_VINSN (from), EXPR_SPEC (from),
1645 EXPR_USEFULNESS (from), EXPR_PRIORITY (from),
1646 EXPR_SCHED_TIMES (from), EXPR_ORIG_BB_INDEX (from),
1647 EXPR_SPEC_DONE_DS (from), EXPR_SPEC_TO_CHECK_DS (from),
1648 EXPR_ORIG_SCHED_CYCLE (from), temp,
1649 EXPR_TARGET_AVAILABLE (from), EXPR_WAS_SUBSTITUTED (from),
1650 EXPR_WAS_RENAMED (from), EXPR_NEEDS_SPEC_CHECK_P (from),
1651 EXPR_CANT_MOVE (from));
1654 /* Same, but the final expr will not ever be in av sets, so don't copy
1655 "uninteresting" data such as bitmap cache. */
1657 copy_expr_onside (expr_t to, expr_t from)
1659 init_expr (to, EXPR_VINSN (from), EXPR_SPEC (from), EXPR_USEFULNESS (from),
1660 EXPR_PRIORITY (from), EXPR_SCHED_TIMES (from), 0,
1661 EXPR_SPEC_DONE_DS (from), EXPR_SPEC_TO_CHECK_DS (from), 0, NULL,
1662 EXPR_TARGET_AVAILABLE (from), EXPR_WAS_SUBSTITUTED (from),
1663 EXPR_WAS_RENAMED (from), EXPR_NEEDS_SPEC_CHECK_P (from),
1664 EXPR_CANT_MOVE (from));
1667 /* Prepare the expr of INSN for scheduling. Used when moving insn and when
1668 initializing new insns. */
1670 prepare_insn_expr (insn_t insn, int seqno)
1672 expr_t expr = INSN_EXPR (insn);
1675 INSN_SEQNO (insn) = seqno;
1676 EXPR_ORIG_BB_INDEX (expr) = BLOCK_NUM (insn);
1677 EXPR_SPEC (expr) = 0;
1678 EXPR_ORIG_SCHED_CYCLE (expr) = 0;
1679 EXPR_WAS_SUBSTITUTED (expr) = 0;
1680 EXPR_WAS_RENAMED (expr) = 0;
1681 EXPR_TARGET_AVAILABLE (expr) = 1;
1682 INSN_LIVE_VALID_P (insn) = false;
1684 /* ??? If this expression is speculative, make its dependence
1685 as weak as possible. We can filter this expression later
1686 in process_spec_exprs, because we do not distinguish
1687 between the status we got during compute_av_set and the
1688 existing status. To be fixed. */
1689 ds = EXPR_SPEC_DONE_DS (expr);
1691 EXPR_SPEC_DONE_DS (expr) = ds_get_max_dep_weak (ds);
1693 free_history_vect (&EXPR_HISTORY_OF_CHANGES (expr));
1696 /* Update target_available bits when merging exprs TO and FROM. SPLIT_POINT
1697 is non-null when expressions are merged from different successors at
1700 update_target_availability (expr_t to, expr_t from, insn_t split_point)
1702 if (EXPR_TARGET_AVAILABLE (to) < 0
1703 || EXPR_TARGET_AVAILABLE (from) < 0)
1704 EXPR_TARGET_AVAILABLE (to) = -1;
1707 /* We try to detect the case when one of the expressions
1708 can only be reached through another one. In this case,
1709 we can do better. */
1710 if (split_point == NULL)
1714 toind = EXPR_ORIG_BB_INDEX (to);
1715 fromind = EXPR_ORIG_BB_INDEX (from);
1717 if (toind && toind == fromind)
1718 /* Do nothing -- everything is done in
1719 merge_with_other_exprs. */
1722 EXPR_TARGET_AVAILABLE (to) = -1;
1725 EXPR_TARGET_AVAILABLE (to) &= EXPR_TARGET_AVAILABLE (from);
1729 /* Update speculation bits when merging exprs TO and FROM. SPLIT_POINT
1730 is non-null when expressions are merged from different successors at
1733 update_speculative_bits (expr_t to, expr_t from, insn_t split_point)
1735 ds_t old_to_ds, old_from_ds;
1737 old_to_ds = EXPR_SPEC_DONE_DS (to);
1738 old_from_ds = EXPR_SPEC_DONE_DS (from);
1740 EXPR_SPEC_DONE_DS (to) = ds_max_merge (old_to_ds, old_from_ds);
1741 EXPR_SPEC_TO_CHECK_DS (to) |= EXPR_SPEC_TO_CHECK_DS (from);
1742 EXPR_NEEDS_SPEC_CHECK_P (to) |= EXPR_NEEDS_SPEC_CHECK_P (from);
1744 /* When merging e.g. control & data speculative exprs, or a control
1745 speculative with a control&data speculative one, we really have
1746 to change vinsn too. Also, when speculative status is changed,
1747 we also need to record this as a transformation in expr's history. */
1748 if ((old_to_ds & SPECULATIVE) || (old_from_ds & SPECULATIVE))
1750 old_to_ds = ds_get_speculation_types (old_to_ds);
1751 old_from_ds = ds_get_speculation_types (old_from_ds);
1753 if (old_to_ds != old_from_ds)
1757 /* When both expressions are speculative, we need to change
1759 if ((old_to_ds & SPECULATIVE) && (old_from_ds & SPECULATIVE))
1763 res = speculate_expr (to, EXPR_SPEC_DONE_DS (to));
1764 gcc_assert (res >= 0);
1767 if (split_point != NULL)
1769 /* Record the change with proper status. */
1770 record_ds = EXPR_SPEC_DONE_DS (to) & SPECULATIVE;
1771 record_ds &= ~(old_to_ds & SPECULATIVE);
1772 record_ds &= ~(old_from_ds & SPECULATIVE);
1774 insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (to),
1775 INSN_UID (split_point), TRANS_SPECULATION,
1776 EXPR_VINSN (from), EXPR_VINSN (to),
1784 /* Merge bits of FROM expr to TO expr. When SPLIT_POINT is not NULL,
1785 this is done along different paths. */
1787 merge_expr_data (expr_t to, expr_t from, insn_t split_point)
1790 expr_history_def *phist;
1792 /* For now, we just set the spec of resulting expr to be minimum of the specs
1794 if (EXPR_SPEC (to) > EXPR_SPEC (from))
1795 EXPR_SPEC (to) = EXPR_SPEC (from);
1798 EXPR_USEFULNESS (to) += EXPR_USEFULNESS (from);
1800 EXPR_USEFULNESS (to) = MAX (EXPR_USEFULNESS (to),
1801 EXPR_USEFULNESS (from));
1803 if (EXPR_PRIORITY (to) < EXPR_PRIORITY (from))
1804 EXPR_PRIORITY (to) = EXPR_PRIORITY (from);
1806 if (EXPR_SCHED_TIMES (to) > EXPR_SCHED_TIMES (from))
1807 EXPR_SCHED_TIMES (to) = EXPR_SCHED_TIMES (from);
1809 if (EXPR_ORIG_BB_INDEX (to) != EXPR_ORIG_BB_INDEX (from))
1810 EXPR_ORIG_BB_INDEX (to) = 0;
1812 EXPR_ORIG_SCHED_CYCLE (to) = MIN (EXPR_ORIG_SCHED_CYCLE (to),
1813 EXPR_ORIG_SCHED_CYCLE (from));
1815 /* We keep this vector sorted. */
1817 VEC_iterate (expr_history_def, EXPR_HISTORY_OF_CHANGES (from),
1820 insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (to),
1821 phist->uid, phist->type,
1822 phist->old_expr_vinsn, phist->new_expr_vinsn,
1825 EXPR_WAS_SUBSTITUTED (to) |= EXPR_WAS_SUBSTITUTED (from);
1826 EXPR_WAS_RENAMED (to) |= EXPR_WAS_RENAMED (from);
1827 EXPR_CANT_MOVE (to) |= EXPR_CANT_MOVE (from);
1829 update_target_availability (to, from, split_point);
1830 update_speculative_bits (to, from, split_point);
1833 /* Merge bits of FROM expr to TO expr. Vinsns in the exprs should be equal
1834 in terms of vinsn_equal_p. SPLIT_POINT is non-null when expressions
1835 are merged from different successors at a split point. */
1837 merge_expr (expr_t to, expr_t from, insn_t split_point)
1839 vinsn_t to_vi = EXPR_VINSN (to);
1840 vinsn_t from_vi = EXPR_VINSN (from);
1842 gcc_assert (vinsn_equal_p (to_vi, from_vi));
1844 /* Make sure that speculative pattern is propagated into exprs that
1845 have non-speculative one. This will provide us with consistent
1846 speculative bits and speculative patterns inside expr. */
1847 if (EXPR_SPEC_DONE_DS (to) == 0
1848 && EXPR_SPEC_DONE_DS (from) != 0)
1849 change_vinsn_in_expr (to, EXPR_VINSN (from));
1851 merge_expr_data (to, from, split_point);
1852 gcc_assert (EXPR_USEFULNESS (to) <= REG_BR_PROB_BASE);
1855 /* Clear the information of this EXPR. */
1857 clear_expr (expr_t expr)
1860 vinsn_detach (EXPR_VINSN (expr));
1861 EXPR_VINSN (expr) = NULL;
1863 free_history_vect (&EXPR_HISTORY_OF_CHANGES (expr));
1866 /* For a given LV_SET, mark EXPR having unavailable target register. */
1868 set_unavailable_target_for_expr (expr_t expr, regset lv_set)
1870 if (EXPR_SEPARABLE_P (expr))
1872 if (REG_P (EXPR_LHS (expr))
1873 && bitmap_bit_p (lv_set, REGNO (EXPR_LHS (expr))))
1875 /* If it's an insn like r1 = use (r1, ...), and it exists in
1876 different forms in each of the av_sets being merged, we can't say
1877 whether original destination register is available or not.
1878 However, this still works if destination register is not used
1879 in the original expression: if the branch at which LV_SET we're
1880 looking here is not actually 'other branch' in sense that same
1881 expression is available through it (but it can't be determined
1882 at computation stage because of transformations on one of the
1883 branches), it still won't affect the availability.
1884 Liveness of a register somewhere on a code motion path means
1885 it's either read somewhere on a codemotion path, live on
1886 'other' branch, live at the point immediately following
1887 the original operation, or is read by the original operation.
1888 The latter case is filtered out in the condition below.
1889 It still doesn't cover the case when register is defined and used
1890 somewhere within the code motion path, and in this case we could
1891 miss a unifying code motion along both branches using a renamed
1892 register, but it won't affect a code correctness since upon
1893 an actual code motion a bookkeeping code would be generated. */
1894 if (bitmap_bit_p (VINSN_REG_USES (EXPR_VINSN (expr)),
1895 REGNO (EXPR_LHS (expr))))
1896 EXPR_TARGET_AVAILABLE (expr) = -1;
1898 EXPR_TARGET_AVAILABLE (expr) = false;
1904 reg_set_iterator rsi;
1906 EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_SETS (EXPR_VINSN (expr)),
1908 if (bitmap_bit_p (lv_set, regno))
1910 EXPR_TARGET_AVAILABLE (expr) = false;
1914 EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_CLOBBERS (EXPR_VINSN (expr)),
1916 if (bitmap_bit_p (lv_set, regno))
1918 EXPR_TARGET_AVAILABLE (expr) = false;
1924 /* Try to make EXPR speculative. Return 1 when EXPR's pattern
1925 or dependence status have changed, 2 when also the target register
1926 became unavailable, 0 if nothing had to be changed. */
1928 speculate_expr (expr_t expr, ds_t ds)
1933 ds_t target_ds, current_ds;
1935 /* Obtain the status we need to put on EXPR. */
1936 target_ds = (ds & SPECULATIVE);
1937 current_ds = EXPR_SPEC_DONE_DS (expr);
1938 ds = ds_full_merge (current_ds, target_ds, NULL_RTX, NULL_RTX);
1940 orig_insn_rtx = EXPR_INSN_RTX (expr);
1942 res = sched_speculate_insn (orig_insn_rtx, ds, &spec_pat);
1947 EXPR_SPEC_DONE_DS (expr) = ds;
1948 return current_ds != ds ? 1 : 0;
1952 rtx spec_insn_rtx = create_insn_rtx_from_pattern (spec_pat, NULL_RTX);
1953 vinsn_t spec_vinsn = create_vinsn_from_insn_rtx (spec_insn_rtx, false);
1955 change_vinsn_in_expr (expr, spec_vinsn);
1956 EXPR_SPEC_DONE_DS (expr) = ds;
1957 EXPR_NEEDS_SPEC_CHECK_P (expr) = true;
1959 /* Do not allow clobbering the address register of speculative
1961 if (bitmap_bit_p (VINSN_REG_USES (EXPR_VINSN (expr)),
1962 expr_dest_regno (expr)))
1964 EXPR_TARGET_AVAILABLE (expr) = false;
1980 /* Return a destination register, if any, of EXPR. */
1982 expr_dest_reg (expr_t expr)
1984 rtx dest = VINSN_LHS (EXPR_VINSN (expr));
1986 if (dest != NULL_RTX && REG_P (dest))
1992 /* Returns the REGNO of the R's destination. */
1994 expr_dest_regno (expr_t expr)
1996 rtx dest = expr_dest_reg (expr);
1998 gcc_assert (dest != NULL_RTX);
1999 return REGNO (dest);
2002 /* For a given LV_SET, mark all expressions in JOIN_SET, but not present in
2003 AV_SET having unavailable target register. */
2005 mark_unavailable_targets (av_set_t join_set, av_set_t av_set, regset lv_set)
2008 av_set_iterator avi;
2010 FOR_EACH_EXPR (expr, avi, join_set)
2011 if (av_set_lookup (av_set, EXPR_VINSN (expr)) == NULL)
2012 set_unavailable_target_for_expr (expr, lv_set);
2016 /* Av set functions. */
2018 /* Add a new element to av set SETP.
2019 Return the element added. */
2021 av_set_add_element (av_set_t *setp)
2023 /* Insert at the beginning of the list. */
2028 /* Add EXPR to SETP. */
2030 av_set_add (av_set_t *setp, expr_t expr)
2034 gcc_assert (!INSN_NOP_P (EXPR_INSN_RTX (expr)));
2035 elem = av_set_add_element (setp);
2036 copy_expr (_AV_SET_EXPR (elem), expr);
2039 /* Same, but do not copy EXPR. */
2041 av_set_add_nocopy (av_set_t *setp, expr_t expr)
2045 elem = av_set_add_element (setp);
2046 *_AV_SET_EXPR (elem) = *expr;
2049 /* Remove expr pointed to by IP from the av_set. */
2051 av_set_iter_remove (av_set_iterator *ip)
2053 clear_expr (_AV_SET_EXPR (*ip->lp));
2054 _list_iter_remove (ip);
2057 /* Search for an expr in SET, such that it's equivalent to SOUGHT_VINSN in the
2058 sense of vinsn_equal_p function. Return NULL if no such expr is
2059 in SET was found. */
2061 av_set_lookup (av_set_t set, vinsn_t sought_vinsn)
2066 FOR_EACH_EXPR (expr, i, set)
2067 if (vinsn_equal_p (EXPR_VINSN (expr), sought_vinsn))
2072 /* Same, but also remove the EXPR found. */
2074 av_set_lookup_and_remove (av_set_t *setp, vinsn_t sought_vinsn)
2079 FOR_EACH_EXPR_1 (expr, i, setp)
2080 if (vinsn_equal_p (EXPR_VINSN (expr), sought_vinsn))
2082 _list_iter_remove_nofree (&i);
2088 /* Search for an expr in SET, such that it's equivalent to EXPR in the
2089 sense of vinsn_equal_p function of their vinsns, but not EXPR itself.
2090 Returns NULL if no such expr is in SET was found. */
2092 av_set_lookup_other_equiv_expr (av_set_t set, expr_t expr)
2097 FOR_EACH_EXPR (cur_expr, i, set)
2099 if (cur_expr == expr)
2101 if (vinsn_equal_p (EXPR_VINSN (cur_expr), EXPR_VINSN (expr)))
2108 /* If other expression is already in AVP, remove one of them. */
2110 merge_with_other_exprs (av_set_t *avp, av_set_iterator *ip, expr_t expr)
2114 expr2 = av_set_lookup_other_equiv_expr (*avp, expr);
2117 /* Reset target availability on merge, since taking it only from one
2118 of the exprs would be controversial for different code. */
2119 EXPR_TARGET_AVAILABLE (expr2) = -1;
2120 EXPR_USEFULNESS (expr2) = 0;
2122 merge_expr (expr2, expr, NULL);
2124 /* Fix usefulness as it should be now REG_BR_PROB_BASE. */
2125 EXPR_USEFULNESS (expr2) = REG_BR_PROB_BASE;
2127 av_set_iter_remove (ip);
2134 /* Return true if there is an expr that correlates to VI in SET. */
2136 av_set_is_in_p (av_set_t set, vinsn_t vi)
2138 return av_set_lookup (set, vi) != NULL;
2141 /* Return a copy of SET. */
2143 av_set_copy (av_set_t set)
2147 av_set_t res = NULL;
2149 FOR_EACH_EXPR (expr, i, set)
2150 av_set_add (&res, expr);
2155 /* Join two av sets that do not have common elements by attaching second set
2156 (pointed to by FROMP) to the end of first set (TO_TAILP must point to
2157 _AV_SET_NEXT of first set's last element). */
2159 join_distinct_sets (av_set_t *to_tailp, av_set_t *fromp)
2161 gcc_assert (*to_tailp == NULL);
2166 /* Makes set pointed to by TO to be the union of TO and FROM. Clear av_set
2167 pointed to by FROMP afterwards. */
2169 av_set_union_and_clear (av_set_t *top, av_set_t *fromp, insn_t insn)
2174 /* Delete from TOP all exprs, that present in FROMP. */
2175 FOR_EACH_EXPR_1 (expr1, i, top)
2177 expr_t expr2 = av_set_lookup (*fromp, EXPR_VINSN (expr1));
2181 merge_expr (expr2, expr1, insn);
2182 av_set_iter_remove (&i);
2186 join_distinct_sets (i.lp, fromp);
2189 /* Same as above, but also update availability of target register in
2190 TOP judging by TO_LV_SET and FROM_LV_SET. */
2192 av_set_union_and_live (av_set_t *top, av_set_t *fromp, regset to_lv_set,
2193 regset from_lv_set, insn_t insn)
2197 av_set_t *to_tailp, in_both_set = NULL;
2199 /* Delete from TOP all expres, that present in FROMP. */
2200 FOR_EACH_EXPR_1 (expr1, i, top)
2202 expr_t expr2 = av_set_lookup_and_remove (fromp, EXPR_VINSN (expr1));
2206 /* It may be that the expressions have different destination
2207 registers, in which case we need to check liveness here. */
2208 if (EXPR_SEPARABLE_P (expr1))
2210 int regno1 = (REG_P (EXPR_LHS (expr1))
2211 ? (int) expr_dest_regno (expr1) : -1);
2212 int regno2 = (REG_P (EXPR_LHS (expr2))
2213 ? (int) expr_dest_regno (expr2) : -1);
2215 /* ??? We don't have a way to check restrictions for
2216 *other* register on the current path, we did it only
2217 for the current target register. Give up. */
2218 if (regno1 != regno2)
2219 EXPR_TARGET_AVAILABLE (expr2) = -1;
2221 else if (EXPR_INSN_RTX (expr1) != EXPR_INSN_RTX (expr2))
2222 EXPR_TARGET_AVAILABLE (expr2) = -1;
2224 merge_expr (expr2, expr1, insn);
2225 av_set_add_nocopy (&in_both_set, expr2);
2226 av_set_iter_remove (&i);
2229 /* EXPR1 is present in TOP, but not in FROMP. Check it on
2231 set_unavailable_target_for_expr (expr1, from_lv_set);
2235 /* These expressions are not present in TOP. Check liveness
2236 restrictions on TO_LV_SET. */
2237 FOR_EACH_EXPR (expr1, i, *fromp)
2238 set_unavailable_target_for_expr (expr1, to_lv_set);
2240 join_distinct_sets (i.lp, &in_both_set);
2241 join_distinct_sets (to_tailp, fromp);
2244 /* Clear av_set pointed to by SETP. */
2246 av_set_clear (av_set_t *setp)
2251 FOR_EACH_EXPR_1 (expr, i, setp)
2252 av_set_iter_remove (&i);
2254 gcc_assert (*setp == NULL);
2257 /* Leave only one non-speculative element in the SETP. */
2259 av_set_leave_one_nonspec (av_set_t *setp)
2263 bool has_one_nonspec = false;
2265 /* Keep all speculative exprs, and leave one non-speculative
2267 FOR_EACH_EXPR_1 (expr, i, setp)
2269 if (!EXPR_SPEC_DONE_DS (expr))
2271 if (has_one_nonspec)
2272 av_set_iter_remove (&i);
2274 has_one_nonspec = true;
2279 /* Return the N'th element of the SET. */
2281 av_set_element (av_set_t set, int n)
2286 FOR_EACH_EXPR (expr, i, set)
2294 /* Deletes all expressions from AVP that are conditional branches (IFs). */
2296 av_set_substract_cond_branches (av_set_t *avp)
2301 FOR_EACH_EXPR_1 (expr, i, avp)
2302 if (vinsn_cond_branch_p (EXPR_VINSN (expr)))
2303 av_set_iter_remove (&i);
2306 /* Multiplies usefulness attribute of each member of av-set *AVP by
2307 value PROB / ALL_PROB. */
2309 av_set_split_usefulness (av_set_t av, int prob, int all_prob)
2314 FOR_EACH_EXPR (expr, i, av)
2315 EXPR_USEFULNESS (expr) = (all_prob
2316 ? (EXPR_USEFULNESS (expr) * prob) / all_prob
2320 /* Leave in AVP only those expressions, which are present in AV,
2323 av_set_intersect (av_set_t *avp, av_set_t av)
2328 FOR_EACH_EXPR_1 (expr, i, avp)
2329 if (av_set_lookup (av, EXPR_VINSN (expr)) == NULL)
2330 av_set_iter_remove (&i);
2335 /* Dependence hooks to initialize insn data. */
2337 /* This is used in hooks callable from dependence analysis when initializing
2338 instruction's data. */
2341 /* Where the dependence was found (lhs/rhs). */
2344 /* The actual data object to initialize. */
2347 /* True when the insn should not be made clonable. */
2348 bool force_unique_p;
2350 /* True when insn should be treated as of type USE, i.e. never renamed. */
2352 } deps_init_id_data;
2355 /* Setup ID for INSN. FORCE_UNIQUE_P is true when INSN should not be
2358 setup_id_for_insn (idata_t id, insn_t insn, bool force_unique_p)
2362 /* Determine whether INSN could be cloned and return appropriate vinsn type.
2363 That clonable insns which can be separated into lhs and rhs have type SET.
2364 Other clonable insns have type USE. */
2365 type = GET_CODE (insn);
2367 /* Only regular insns could be cloned. */
2368 if (type == INSN && !force_unique_p)
2370 else if (type == JUMP_INSN && simplejump_p (insn))
2373 IDATA_TYPE (id) = type;
2374 IDATA_REG_SETS (id) = get_clear_regset_from_pool ();
2375 IDATA_REG_USES (id) = get_clear_regset_from_pool ();
2376 IDATA_REG_CLOBBERS (id) = get_clear_regset_from_pool ();
2379 /* Start initializing insn data. */
2381 deps_init_id_start_insn (insn_t insn)
2383 gcc_assert (deps_init_id_data.where == DEPS_IN_NOWHERE);
2385 setup_id_for_insn (deps_init_id_data.id, insn,
2386 deps_init_id_data.force_unique_p);
2387 deps_init_id_data.where = DEPS_IN_INSN;
2390 /* Start initializing lhs data. */
2392 deps_init_id_start_lhs (rtx lhs)
2394 gcc_assert (deps_init_id_data.where == DEPS_IN_INSN);
2395 gcc_assert (IDATA_LHS (deps_init_id_data.id) == NULL);
2397 if (IDATA_TYPE (deps_init_id_data.id) == SET)
2399 IDATA_LHS (deps_init_id_data.id) = lhs;
2400 deps_init_id_data.where = DEPS_IN_LHS;
2404 /* Finish initializing lhs data. */
2406 deps_init_id_finish_lhs (void)
2408 deps_init_id_data.where = DEPS_IN_INSN;
2411 /* Note a set of REGNO. */
2413 deps_init_id_note_reg_set (int regno)
2415 haifa_note_reg_set (regno);
2417 if (deps_init_id_data.where == DEPS_IN_RHS)
2418 deps_init_id_data.force_use_p = true;
2420 if (IDATA_TYPE (deps_init_id_data.id) != PC)
2421 SET_REGNO_REG_SET (IDATA_REG_SETS (deps_init_id_data.id), regno);
2424 /* Make instructions that set stack registers to be ineligible for
2425 renaming to avoid issues with find_used_regs. */
2426 if (IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG))
2427 deps_init_id_data.force_use_p = true;
2431 /* Note a clobber of REGNO. */
2433 deps_init_id_note_reg_clobber (int regno)
2435 haifa_note_reg_clobber (regno);
2437 if (deps_init_id_data.where == DEPS_IN_RHS)
2438 deps_init_id_data.force_use_p = true;
2440 if (IDATA_TYPE (deps_init_id_data.id) != PC)
2441 SET_REGNO_REG_SET (IDATA_REG_CLOBBERS (deps_init_id_data.id), regno);
2444 /* Note a use of REGNO. */
2446 deps_init_id_note_reg_use (int regno)
2448 haifa_note_reg_use (regno);
2450 if (IDATA_TYPE (deps_init_id_data.id) != PC)
2451 SET_REGNO_REG_SET (IDATA_REG_USES (deps_init_id_data.id), regno);
2454 /* Start initializing rhs data. */
2456 deps_init_id_start_rhs (rtx rhs)
2458 gcc_assert (deps_init_id_data.where == DEPS_IN_INSN);
2460 /* And there was no sel_deps_reset_to_insn (). */
2461 if (IDATA_LHS (deps_init_id_data.id) != NULL)
2463 IDATA_RHS (deps_init_id_data.id) = rhs;
2464 deps_init_id_data.where = DEPS_IN_RHS;
2468 /* Finish initializing rhs data. */
2470 deps_init_id_finish_rhs (void)
2472 gcc_assert (deps_init_id_data.where == DEPS_IN_RHS
2473 || deps_init_id_data.where == DEPS_IN_INSN);
2474 deps_init_id_data.where = DEPS_IN_INSN;
2477 /* Finish initializing insn data. */
2479 deps_init_id_finish_insn (void)
2481 gcc_assert (deps_init_id_data.where == DEPS_IN_INSN);
2483 if (IDATA_TYPE (deps_init_id_data.id) == SET)
2485 rtx lhs = IDATA_LHS (deps_init_id_data.id);
2486 rtx rhs = IDATA_RHS (deps_init_id_data.id);
2488 if (lhs == NULL || rhs == NULL || !lhs_and_rhs_separable_p (lhs, rhs)
2489 || deps_init_id_data.force_use_p)
2491 /* This should be a USE, as we don't want to schedule its RHS
2492 separately. However, we still want to have them recorded
2493 for the purposes of substitution. That's why we don't
2494 simply call downgrade_to_use () here. */
2495 gcc_assert (IDATA_TYPE (deps_init_id_data.id) == SET);
2496 gcc_assert (!lhs == !rhs);
2498 IDATA_TYPE (deps_init_id_data.id) = USE;
2502 deps_init_id_data.where = DEPS_IN_NOWHERE;
2505 /* This is dependence info used for initializing insn's data. */
2506 static struct sched_deps_info_def deps_init_id_sched_deps_info;
2508 /* This initializes most of the static part of the above structure. */
2509 static const struct sched_deps_info_def const_deps_init_id_sched_deps_info =
2513 deps_init_id_start_insn,
2514 deps_init_id_finish_insn,
2515 deps_init_id_start_lhs,
2516 deps_init_id_finish_lhs,
2517 deps_init_id_start_rhs,
2518 deps_init_id_finish_rhs,
2519 deps_init_id_note_reg_set,
2520 deps_init_id_note_reg_clobber,
2521 deps_init_id_note_reg_use,
2522 NULL, /* note_mem_dep */
2523 NULL, /* note_dep */
2526 0, /* use_deps_list */
2527 0 /* generate_spec_deps */
2530 /* Initialize INSN's lhs and rhs in ID. When FORCE_UNIQUE_P is true,
2531 we don't actually need information about lhs and rhs. */
2533 setup_id_lhs_rhs (idata_t id, insn_t insn, bool force_unique_p)
2535 rtx pat = PATTERN (insn);
2537 if (GET_CODE (insn) == INSN
2538 && GET_CODE (pat) == SET
2541 IDATA_RHS (id) = SET_SRC (pat);
2542 IDATA_LHS (id) = SET_DEST (pat);
2545 IDATA_LHS (id) = IDATA_RHS (id) = NULL;
2548 /* Possibly downgrade INSN to USE. */
2550 maybe_downgrade_id_to_use (idata_t id, insn_t insn)
2552 bool must_be_use = false;
2553 unsigned uid = INSN_UID (insn);
2555 rtx lhs = IDATA_LHS (id);
2556 rtx rhs = IDATA_RHS (id);
2558 /* We downgrade only SETs. */
2559 if (IDATA_TYPE (id) != SET)
2562 if (!lhs || !lhs_and_rhs_separable_p (lhs, rhs))
2564 IDATA_TYPE (id) = USE;
2568 for (rec = DF_INSN_UID_DEFS (uid); *rec; rec++)
2572 if (DF_REF_INSN (def)
2573 && DF_REF_FLAGS_IS_SET (def, DF_REF_PRE_POST_MODIFY)
2574 && loc_mentioned_in_p (DF_REF_LOC (def), IDATA_RHS (id)))
2581 /* Make instructions that set stack registers to be ineligible for
2582 renaming to avoid issues with find_used_regs. */
2583 if (IN_RANGE (DF_REF_REGNO (def), FIRST_STACK_REG, LAST_STACK_REG))
2592 IDATA_TYPE (id) = USE;
2595 /* Setup register sets describing INSN in ID. */
2597 setup_id_reg_sets (idata_t id, insn_t insn)
2599 unsigned uid = INSN_UID (insn);
2601 regset tmp = get_clear_regset_from_pool ();
2603 for (rec = DF_INSN_UID_DEFS (uid); *rec; rec++)
2606 unsigned int regno = DF_REF_REGNO (def);
2608 /* Post modifies are treated like clobbers by sched-deps.c. */
2609 if (DF_REF_FLAGS_IS_SET (def, (DF_REF_MUST_CLOBBER
2610 | DF_REF_PRE_POST_MODIFY)))
2611 SET_REGNO_REG_SET (IDATA_REG_CLOBBERS (id), regno);
2612 else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
2614 SET_REGNO_REG_SET (IDATA_REG_SETS (id), regno);
2617 /* For stack registers, treat writes to them as writes
2618 to the first one to be consistent with sched-deps.c. */
2619 if (IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG))
2620 SET_REGNO_REG_SET (IDATA_REG_SETS (id), FIRST_STACK_REG);
2623 /* Mark special refs that generate read/write def pair. */
2624 if (DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL)
2625 || regno == STACK_POINTER_REGNUM)
2626 bitmap_set_bit (tmp, regno);
2629 for (rec = DF_INSN_UID_USES (uid); *rec; rec++)
2632 unsigned int regno = DF_REF_REGNO (use);
2634 /* When these refs are met for the first time, skip them, as
2635 these uses are just counterparts of some defs. */
2636 if (bitmap_bit_p (tmp, regno))
2637 bitmap_clear_bit (tmp, regno);
2638 else if (! DF_REF_FLAGS_IS_SET (use, DF_REF_CALL_STACK_USAGE))
2640 SET_REGNO_REG_SET (IDATA_REG_USES (id), regno);
2643 /* For stack registers, treat reads from them as reads from
2644 the first one to be consistent with sched-deps.c. */
2645 if (IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG))
2646 SET_REGNO_REG_SET (IDATA_REG_USES (id), FIRST_STACK_REG);
2651 return_regset_to_pool (tmp);
2654 /* Initialize instruction data for INSN in ID using DF's data. */
2656 init_id_from_df (idata_t id, insn_t insn, bool force_unique_p)
2658 gcc_assert (DF_INSN_UID_SAFE_GET (INSN_UID (insn)) != NULL);
2660 setup_id_for_insn (id, insn, force_unique_p);
2661 setup_id_lhs_rhs (id, insn, force_unique_p);
2663 if (INSN_NOP_P (insn))
2666 maybe_downgrade_id_to_use (id, insn);
2667 setup_id_reg_sets (id, insn);
2670 /* Initialize instruction data for INSN in ID. */
2672 deps_init_id (idata_t id, insn_t insn, bool force_unique_p)
2674 struct deps _dc, *dc = &_dc;
2676 deps_init_id_data.where = DEPS_IN_NOWHERE;
2677 deps_init_id_data.id = id;
2678 deps_init_id_data.force_unique_p = force_unique_p;
2679 deps_init_id_data.force_use_p = false;
2681 init_deps (dc, false);
2683 memcpy (&deps_init_id_sched_deps_info,
2684 &const_deps_init_id_sched_deps_info,
2685 sizeof (deps_init_id_sched_deps_info));
2687 if (spec_info != NULL)
2688 deps_init_id_sched_deps_info.generate_spec_deps = 1;
2690 sched_deps_info = &deps_init_id_sched_deps_info;
2692 deps_analyze_insn (dc, insn);
2696 deps_init_id_data.id = NULL;
2701 /* Implement hooks for collecting fundamental insn properties like if insn is
2702 an ASM or is within a SCHED_GROUP. */
2704 /* True when a "one-time init" data for INSN was already inited. */
2706 first_time_insn_init (insn_t insn)
2708 return INSN_LIVE (insn) == NULL;
2711 /* Hash an entry in a transformed_insns hashtable. */
2713 hash_transformed_insns (const void *p)
2715 return VINSN_HASH_RTX (((const struct transformed_insns *) p)->vinsn_old);
2718 /* Compare the entries in a transformed_insns hashtable. */
2720 eq_transformed_insns (const void *p, const void *q)
2722 rtx i1 = VINSN_INSN_RTX (((const struct transformed_insns *) p)->vinsn_old);
2723 rtx i2 = VINSN_INSN_RTX (((const struct transformed_insns *) q)->vinsn_old);
2725 if (INSN_UID (i1) == INSN_UID (i2))
2727 return rtx_equal_p (PATTERN (i1), PATTERN (i2));
2730 /* Free an entry in a transformed_insns hashtable. */
2732 free_transformed_insns (void *p)
2734 struct transformed_insns *pti = (struct transformed_insns *) p;
2736 vinsn_detach (pti->vinsn_old);
2737 vinsn_detach (pti->vinsn_new);
2741 /* Init the s_i_d data for INSN which should be inited just once, when
2742 we first see the insn. */
2744 init_first_time_insn_data (insn_t insn)
2746 /* This should not be set if this is the first time we init data for
2748 gcc_assert (first_time_insn_init (insn));
2750 /* These are needed for nops too. */
2751 INSN_LIVE (insn) = get_regset_from_pool ();
2752 INSN_LIVE_VALID_P (insn) = false;
2754 if (!INSN_NOP_P (insn))
2756 INSN_ANALYZED_DEPS (insn) = BITMAP_ALLOC (NULL);
2757 INSN_FOUND_DEPS (insn) = BITMAP_ALLOC (NULL);
2758 INSN_TRANSFORMED_INSNS (insn)
2759 = htab_create (16, hash_transformed_insns,
2760 eq_transformed_insns, free_transformed_insns);
2761 init_deps (&INSN_DEPS_CONTEXT (insn), true);
2765 /* Free almost all above data for INSN that is scheduled already.
2766 Used for extra-large basic blocks. */
2768 free_data_for_scheduled_insn (insn_t insn)
2770 gcc_assert (! first_time_insn_init (insn));
2772 if (! INSN_ANALYZED_DEPS (insn))
2775 BITMAP_FREE (INSN_ANALYZED_DEPS (insn));
2776 BITMAP_FREE (INSN_FOUND_DEPS (insn));
2777 htab_delete (INSN_TRANSFORMED_INSNS (insn));
2779 /* This is allocated only for bookkeeping insns. */
2780 if (INSN_ORIGINATORS (insn))
2781 BITMAP_FREE (INSN_ORIGINATORS (insn));
2782 free_deps (&INSN_DEPS_CONTEXT (insn));
2784 INSN_ANALYZED_DEPS (insn) = NULL;
2786 /* Clear the readonly flag so we would ICE when trying to recalculate
2787 the deps context (as we believe that it should not happen). */
2788 (&INSN_DEPS_CONTEXT (insn))->readonly = 0;
2791 /* Free the same data as above for INSN. */
2793 free_first_time_insn_data (insn_t insn)
2795 gcc_assert (! first_time_insn_init (insn));
2797 free_data_for_scheduled_insn (insn);
2798 return_regset_to_pool (INSN_LIVE (insn));
2799 INSN_LIVE (insn) = NULL;
2800 INSN_LIVE_VALID_P (insn) = false;
2803 /* Initialize region-scope data structures for basic blocks. */
2805 init_global_and_expr_for_bb (basic_block bb)
2807 if (sel_bb_empty_p (bb))
2810 invalidate_av_set (bb);
2813 /* Data for global dependency analysis (to initialize CANT_MOVE and
2817 /* Previous insn. */
2821 /* Determine if INSN is in the sched_group, is an asm or should not be
2822 cloned. After that initialize its expr. */
2824 init_global_and_expr_for_insn (insn_t insn)
2829 if (NOTE_INSN_BASIC_BLOCK_P (insn))
2831 init_global_data.prev_insn = NULL_RTX;
2835 gcc_assert (INSN_P (insn));
2837 if (SCHED_GROUP_P (insn))
2838 /* Setup a sched_group. */
2840 insn_t prev_insn = init_global_data.prev_insn;
2843 INSN_SCHED_NEXT (prev_insn) = insn;
2845 init_global_data.prev_insn = insn;
2848 init_global_data.prev_insn = NULL_RTX;
2850 if (GET_CODE (PATTERN (insn)) == ASM_INPUT
2851 || asm_noperands (PATTERN (insn)) >= 0)
2852 /* Mark INSN as an asm. */
2853 INSN_ASM_P (insn) = true;
2856 bool force_unique_p;
2859 /* Certain instructions cannot be cloned. */
2860 if (CANT_MOVE (insn)
2861 || INSN_ASM_P (insn)
2862 || SCHED_GROUP_P (insn)
2863 || prologue_epilogue_contains (insn)
2864 /* Exception handling insns are always unique. */
2865 || (flag_non_call_exceptions && can_throw_internal (insn))
2866 /* TRAP_IF though have an INSN code is control_flow_insn_p (). */
2867 || control_flow_insn_p (insn))
2868 force_unique_p = true;
2870 force_unique_p = false;
2872 if (targetm.sched.get_insn_spec_ds)
2874 spec_done_ds = targetm.sched.get_insn_spec_ds (insn);
2875 spec_done_ds = ds_get_max_dep_weak (spec_done_ds);
2880 /* Initialize INSN's expr. */
2881 init_expr (INSN_EXPR (insn), vinsn_create (insn, force_unique_p), 0,
2882 REG_BR_PROB_BASE, INSN_PRIORITY (insn), 0, BLOCK_NUM (insn),
2883 spec_done_ds, 0, 0, NULL, true, false, false, false,
2887 init_first_time_insn_data (insn);
2890 /* Scan the region and initialize instruction data for basic blocks BBS. */
2892 sel_init_global_and_expr (bb_vec_t bbs)
2894 /* ??? It would be nice to implement push / pop scheme for sched_infos. */
2895 const struct sched_scan_info_def ssi =
2897 NULL, /* extend_bb */
2898 init_global_and_expr_for_bb, /* init_bb */
2899 extend_insn_data, /* extend_insn */
2900 init_global_and_expr_for_insn /* init_insn */
2903 sched_scan (&ssi, bbs, NULL, NULL, NULL);
2906 /* Finalize region-scope data structures for basic blocks. */
2908 finish_global_and_expr_for_bb (basic_block bb)
2910 av_set_clear (&BB_AV_SET (bb));
2911 BB_AV_LEVEL (bb) = 0;
2914 /* Finalize INSN's data. */
2916 finish_global_and_expr_insn (insn_t insn)
2918 if (LABEL_P (insn) || NOTE_INSN_BASIC_BLOCK_P (insn))
2921 gcc_assert (INSN_P (insn));
2923 if (INSN_LUID (insn) > 0)
2925 free_first_time_insn_data (insn);
2926 INSN_WS_LEVEL (insn) = 0;
2927 CANT_MOVE (insn) = 0;
2929 /* We can no longer assert this, as vinsns of this insn could be
2930 easily live in other insn's caches. This should be changed to
2931 a counter-like approach among all vinsns. */
2932 gcc_assert (true || VINSN_COUNT (INSN_VINSN (insn)) == 1);
2933 clear_expr (INSN_EXPR (insn));
2937 /* Finalize per instruction data for the whole region. */
2939 sel_finish_global_and_expr (void)
2945 bbs = VEC_alloc (basic_block, heap, current_nr_blocks);
2947 for (i = 0; i < current_nr_blocks; i++)
2948 VEC_quick_push (basic_block, bbs, BASIC_BLOCK (BB_TO_BLOCK (i)));
2950 /* Clear AV_SETs and INSN_EXPRs. */
2952 const struct sched_scan_info_def ssi =
2954 NULL, /* extend_bb */
2955 finish_global_and_expr_for_bb, /* init_bb */
2956 NULL, /* extend_insn */
2957 finish_global_and_expr_insn /* init_insn */
2960 sched_scan (&ssi, bbs, NULL, NULL, NULL);
2963 VEC_free (basic_block, heap, bbs);
2970 /* In the below hooks, we merely calculate whether or not a dependence
2971 exists, and in what part of insn. However, we will need more data
2972 when we'll start caching dependence requests. */
2974 /* Container to hold information for dependency analysis. */
2979 /* A variable to track which part of rtx we are scanning in
2980 sched-deps.c: sched_analyze_insn (). */
2983 /* Current producer. */
2986 /* Current consumer. */
2989 /* Is SEL_DEPS_HAS_DEP_P[DEPS_IN_X] is true, then X has a dependence.
2990 X is from { INSN, LHS, RHS }. */
2991 ds_t has_dep_p[DEPS_IN_NOWHERE];
2992 } has_dependence_data;
2994 /* Start analyzing dependencies of INSN. */
2996 has_dependence_start_insn (insn_t insn ATTRIBUTE_UNUSED)
2998 gcc_assert (has_dependence_data.where == DEPS_IN_NOWHERE);
3000 has_dependence_data.where = DEPS_IN_INSN;
3003 /* Finish analyzing dependencies of an insn. */
3005 has_dependence_finish_insn (void)
3007 gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
3009 has_dependence_data.where = DEPS_IN_NOWHERE;
3012 /* Start analyzing dependencies of LHS. */
3014 has_dependence_start_lhs (rtx lhs ATTRIBUTE_UNUSED)
3016 gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
3018 if (VINSN_LHS (has_dependence_data.con) != NULL)
3019 has_dependence_data.where = DEPS_IN_LHS;
3022 /* Finish analyzing dependencies of an lhs. */
3024 has_dependence_finish_lhs (void)
3026 has_dependence_data.where = DEPS_IN_INSN;
3029 /* Start analyzing dependencies of RHS. */
3031 has_dependence_start_rhs (rtx rhs ATTRIBUTE_UNUSED)
3033 gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
3035 if (VINSN_RHS (has_dependence_data.con) != NULL)
3036 has_dependence_data.where = DEPS_IN_RHS;
3039 /* Start analyzing dependencies of an rhs. */
3041 has_dependence_finish_rhs (void)
3043 gcc_assert (has_dependence_data.where == DEPS_IN_RHS
3044 || has_dependence_data.where == DEPS_IN_INSN);
3046 has_dependence_data.where = DEPS_IN_INSN;
3049 /* Note a set of REGNO. */
3051 has_dependence_note_reg_set (int regno)
3053 struct deps_reg *reg_last = &has_dependence_data.dc->reg_last[regno];
3055 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3057 (has_dependence_data.con)))
3059 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3061 if (reg_last->sets != NULL
3062 || reg_last->clobbers != NULL)
3063 *dsp = (*dsp & ~SPECULATIVE) | DEP_OUTPUT;
3066 *dsp = (*dsp & ~SPECULATIVE) | DEP_ANTI;
3070 /* Note a clobber of REGNO. */
3072 has_dependence_note_reg_clobber (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_OUTPUT;
3086 *dsp = (*dsp & ~SPECULATIVE) | DEP_ANTI;
3090 /* Note a use of REGNO. */
3092 has_dependence_note_reg_use (int regno)
3094 struct deps_reg *reg_last = &has_dependence_data.dc->reg_last[regno];
3096 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3098 (has_dependence_data.con)))
3100 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3103 *dsp = (*dsp & ~SPECULATIVE) | DEP_TRUE;
3105 if (reg_last->clobbers)
3106 *dsp = (*dsp & ~SPECULATIVE) | DEP_ANTI;
3108 /* Handle BE_IN_SPEC. */
3111 ds_t pro_spec_checked_ds;
3113 pro_spec_checked_ds = INSN_SPEC_CHECKED_DS (has_dependence_data.pro);
3114 pro_spec_checked_ds = ds_get_max_dep_weak (pro_spec_checked_ds);
3116 if (pro_spec_checked_ds != 0)
3117 /* Merge BE_IN_SPEC bits into *DSP. */
3118 *dsp = ds_full_merge (*dsp, pro_spec_checked_ds,
3119 NULL_RTX, NULL_RTX);
3124 /* Note a memory dependence. */
3126 has_dependence_note_mem_dep (rtx mem ATTRIBUTE_UNUSED,
3127 rtx pending_mem ATTRIBUTE_UNUSED,
3128 insn_t pending_insn ATTRIBUTE_UNUSED,
3129 ds_t ds ATTRIBUTE_UNUSED)
3131 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3132 VINSN_INSN_RTX (has_dependence_data.con)))
3134 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3136 *dsp = ds_full_merge (ds, *dsp, pending_mem, mem);
3140 /* Note a dependence. */
3142 has_dependence_note_dep (insn_t pro ATTRIBUTE_UNUSED,
3143 ds_t ds ATTRIBUTE_UNUSED)
3145 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3146 VINSN_INSN_RTX (has_dependence_data.con)))
3148 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3150 *dsp = ds_full_merge (ds, *dsp, NULL_RTX, NULL_RTX);
3154 /* Mark the insn as having a hard dependence that prevents speculation. */
3156 sel_mark_hard_insn (rtx insn)
3160 /* Only work when we're in has_dependence_p mode.
3161 ??? This is a hack, this should actually be a hook. */
3162 if (!has_dependence_data.dc || !has_dependence_data.pro)
3165 gcc_assert (insn == VINSN_INSN_RTX (has_dependence_data.con));
3166 gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
3168 for (i = 0; i < DEPS_IN_NOWHERE; i++)
3169 has_dependence_data.has_dep_p[i] &= ~SPECULATIVE;
3172 /* This structure holds the hooks for the dependency analysis used when
3173 actually processing dependencies in the scheduler. */
3174 static struct sched_deps_info_def has_dependence_sched_deps_info;
3176 /* This initializes most of the fields of the above structure. */
3177 static const struct sched_deps_info_def const_has_dependence_sched_deps_info =
3181 has_dependence_start_insn,
3182 has_dependence_finish_insn,
3183 has_dependence_start_lhs,
3184 has_dependence_finish_lhs,
3185 has_dependence_start_rhs,
3186 has_dependence_finish_rhs,
3187 has_dependence_note_reg_set,
3188 has_dependence_note_reg_clobber,
3189 has_dependence_note_reg_use,
3190 has_dependence_note_mem_dep,
3191 has_dependence_note_dep,
3194 0, /* use_deps_list */
3195 0 /* generate_spec_deps */
3198 /* Initialize has_dependence_sched_deps_info with extra spec field. */
3200 setup_has_dependence_sched_deps_info (void)
3202 memcpy (&has_dependence_sched_deps_info,
3203 &const_has_dependence_sched_deps_info,
3204 sizeof (has_dependence_sched_deps_info));
3206 if (spec_info != NULL)
3207 has_dependence_sched_deps_info.generate_spec_deps = 1;
3209 sched_deps_info = &has_dependence_sched_deps_info;
3212 /* Remove all dependences found and recorded in has_dependence_data array. */
3214 sel_clear_has_dependence (void)
3218 for (i = 0; i < DEPS_IN_NOWHERE; i++)
3219 has_dependence_data.has_dep_p[i] = 0;
3222 /* Return nonzero if EXPR has is dependent upon PRED. Return the pointer
3223 to the dependence information array in HAS_DEP_PP. */
3225 has_dependence_p (expr_t expr, insn_t pred, ds_t **has_dep_pp)
3231 if (INSN_SIMPLEJUMP_P (pred))
3232 /* Unconditional jump is just a transfer of control flow.
3236 dc = &INSN_DEPS_CONTEXT (pred);
3238 /* We init this field lazily. */
3239 if (dc->reg_last == NULL)
3240 init_deps_reg_last (dc);
3244 has_dependence_data.pro = NULL;
3245 /* Initialize empty dep context with information about PRED. */
3246 advance_deps_context (dc, pred);
3250 has_dependence_data.where = DEPS_IN_NOWHERE;
3251 has_dependence_data.pro = pred;
3252 has_dependence_data.con = EXPR_VINSN (expr);
3253 has_dependence_data.dc = dc;
3255 sel_clear_has_dependence ();
3257 /* Now catch all dependencies that would be generated between PRED and
3259 setup_has_dependence_sched_deps_info ();
3260 deps_analyze_insn (dc, EXPR_INSN_RTX (expr));
3261 has_dependence_data.dc = NULL;
3263 /* When a barrier was found, set DEPS_IN_INSN bits. */
3264 if (dc->last_reg_pending_barrier == TRUE_BARRIER)
3265 has_dependence_data.has_dep_p[DEPS_IN_INSN] = DEP_TRUE;
3266 else if (dc->last_reg_pending_barrier == MOVE_BARRIER)
3267 has_dependence_data.has_dep_p[DEPS_IN_INSN] = DEP_ANTI;
3269 /* Do not allow stores to memory to move through checks. Currently
3270 we don't move this to sched-deps.c as the check doesn't have
3271 obvious places to which this dependence can be attached.
3272 FIMXE: this should go to a hook. */
3274 && MEM_P (EXPR_LHS (expr))
3275 && sel_insn_is_speculation_check (pred))
3276 has_dependence_data.has_dep_p[DEPS_IN_INSN] = DEP_ANTI;
3278 *has_dep_pp = has_dependence_data.has_dep_p;
3280 for (i = 0; i < DEPS_IN_NOWHERE; i++)
3281 ds = ds_full_merge (ds, has_dependence_data.has_dep_p[i],
3282 NULL_RTX, NULL_RTX);
3288 /* Dependence hooks implementation that checks dependence latency constraints
3289 on the insns being scheduled. The entry point for these routines is
3290 tick_check_p predicate. */
3294 /* An expr we are currently checking. */
3297 /* A minimal cycle for its scheduling. */
3300 /* Whether we have seen a true dependence while checking. */
3301 bool seen_true_dep_p;
3304 /* Update minimal scheduling cycle for tick_check_insn given that it depends
3305 on PRO with status DS and weight DW. */
3307 tick_check_dep_with_dw (insn_t pro_insn, ds_t ds, dw_t dw)
3309 expr_t con_expr = tick_check_data.expr;
3310 insn_t con_insn = EXPR_INSN_RTX (con_expr);
3312 if (con_insn != pro_insn)
3317 if (/* PROducer was removed from above due to pipelining. */
3318 !INSN_IN_STREAM_P (pro_insn)
3319 /* Or PROducer was originally on the next iteration regarding the
3321 || (INSN_SCHED_TIMES (pro_insn)
3322 - EXPR_SCHED_TIMES (con_expr)) > 1)
3323 /* Don't count this dependence. */
3327 if (dt == REG_DEP_TRUE)
3328 tick_check_data.seen_true_dep_p = true;
3330 gcc_assert (INSN_SCHED_CYCLE (pro_insn) > 0);
3333 dep_def _dep, *dep = &_dep;
3335 init_dep (dep, pro_insn, con_insn, dt);
3337 tick = INSN_SCHED_CYCLE (pro_insn) + dep_cost_1 (dep, dw);
3340 /* When there are several kinds of dependencies between pro and con,
3341 only REG_DEP_TRUE should be taken into account. */
3342 if (tick > tick_check_data.cycle
3343 && (dt == REG_DEP_TRUE || !tick_check_data.seen_true_dep_p))
3344 tick_check_data.cycle = tick;
3348 /* An implementation of note_dep hook. */
3350 tick_check_note_dep (insn_t pro, ds_t ds)
3352 tick_check_dep_with_dw (pro, ds, 0);
3355 /* An implementation of note_mem_dep hook. */
3357 tick_check_note_mem_dep (rtx mem1, rtx mem2, insn_t pro, ds_t ds)
3361 dw = (ds_to_dt (ds) == REG_DEP_TRUE
3362 ? estimate_dep_weak (mem1, mem2)
3365 tick_check_dep_with_dw (pro, ds, dw);
3368 /* This structure contains hooks for dependence analysis used when determining
3369 whether an insn is ready for scheduling. */
3370 static struct sched_deps_info_def tick_check_sched_deps_info =
3381 haifa_note_reg_clobber,
3383 tick_check_note_mem_dep,
3384 tick_check_note_dep,
3389 /* Estimate number of cycles from the current cycle of FENCE until EXPR can be
3390 scheduled. Return 0 if all data from producers in DC is ready. */
3392 tick_check_p (expr_t expr, deps_t dc, fence_t fence)
3395 /* Initialize variables. */
3396 tick_check_data.expr = expr;
3397 tick_check_data.cycle = 0;
3398 tick_check_data.seen_true_dep_p = false;
3399 sched_deps_info = &tick_check_sched_deps_info;
3401 gcc_assert (!dc->readonly);
3403 deps_analyze_insn (dc, EXPR_INSN_RTX (expr));
3406 cycles_left = tick_check_data.cycle - FENCE_CYCLE (fence);
3408 return cycles_left >= 0 ? cycles_left : 0;
3412 /* Functions to work with insns. */
3414 /* Returns true if LHS of INSN is the same as DEST of an insn
3417 lhs_of_insn_equals_to_dest_p (insn_t insn, rtx dest)
3419 rtx lhs = INSN_LHS (insn);
3421 if (lhs == NULL || dest == NULL)
3424 return rtx_equal_p (lhs, dest);
3427 /* Return s_i_d entry of INSN. Callable from debugger. */
3429 insn_sid (insn_t insn)
3434 /* True when INSN is a speculative check. We can tell this by looking
3435 at the data structures of the selective scheduler, not by examining
3438 sel_insn_is_speculation_check (rtx insn)
3440 return s_i_d && !! INSN_SPEC_CHECKED_DS (insn);
3443 /* Extracts machine mode MODE and destination location DST_LOC
3446 get_dest_and_mode (rtx insn, rtx *dst_loc, enum machine_mode *mode)
3448 rtx pat = PATTERN (insn);
3450 gcc_assert (dst_loc);
3451 gcc_assert (GET_CODE (pat) == SET);
3453 *dst_loc = SET_DEST (pat);
3455 gcc_assert (*dst_loc);
3456 gcc_assert (MEM_P (*dst_loc) || REG_P (*dst_loc));
3459 *mode = GET_MODE (*dst_loc);
3462 /* Returns true when moving through JUMP will result in bookkeeping
3465 bookkeeping_can_be_created_if_moved_through_p (insn_t jump)
3470 FOR_EACH_SUCC (succ, si, jump)
3471 if (sel_num_cfg_preds_gt_1 (succ))
3477 /* Return 'true' if INSN is the only one in its basic block. */
3479 insn_is_the_only_one_in_bb_p (insn_t insn)
3481 return sel_bb_head_p (insn) && sel_bb_end_p (insn);
3484 #ifdef ENABLE_CHECKING
3485 /* Check that the region we're scheduling still has at most one
3488 verify_backedges (void)
3496 for (i = 0; i < current_nr_blocks; i++)
3497 FOR_EACH_EDGE (e, ei, BASIC_BLOCK (BB_TO_BLOCK (i))->succs)
3498 if (in_current_region_p (e->dest)
3499 && BLOCK_TO_BB (e->dest->index) < i)
3502 gcc_assert (n <= 1);
3508 /* Functions to work with control flow. */
3510 /* Recompute BLOCK_TO_BB and BB_FOR_BLOCK for current region so that blocks
3511 are sorted in topological order (it might have been invalidated by
3512 redirecting an edge). */
3514 sel_recompute_toporder (void)
3517 int *postorder, n_blocks;
3519 postorder = XALLOCAVEC (int, n_basic_blocks);
3520 n_blocks = post_order_compute (postorder, false, false);
3522 rgn = CONTAINING_RGN (BB_TO_BLOCK (0));
3523 for (n = 0, i = n_blocks - 1; i >= 0; i--)
3524 if (CONTAINING_RGN (postorder[i]) == rgn)
3526 BLOCK_TO_BB (postorder[i]) = n;
3527 BB_TO_BLOCK (n) = postorder[i];
3531 /* Assert that we updated info for all blocks. We may miss some blocks if
3532 this function is called when redirecting an edge made a block
3533 unreachable, but that block is not deleted yet. */
3534 gcc_assert (n == RGN_NR_BLOCKS (rgn));
3537 /* Tidy the possibly empty block BB. */
3539 maybe_tidy_empty_bb (basic_block bb, bool recompute_toporder_p)
3541 basic_block succ_bb, pred_bb;
3546 /* Keep empty bb only if this block immediately precedes EXIT and
3547 has incoming non-fallthrough edge, or it has no predecessors or
3548 successors. Otherwise remove it. */
3549 if (!sel_bb_empty_p (bb)
3550 || (single_succ_p (bb)
3551 && single_succ (bb) == EXIT_BLOCK_PTR
3552 && (!single_pred_p (bb)
3553 || !(single_pred_edge (bb)->flags & EDGE_FALLTHRU)))
3554 || EDGE_COUNT (bb->preds) == 0
3555 || EDGE_COUNT (bb->succs) == 0)
3558 /* Do not attempt to redirect complex edges. */
3559 FOR_EACH_EDGE (e, ei, bb->preds)
3560 if (e->flags & EDGE_COMPLEX)
3563 free_data_sets (bb);
3565 /* Do not delete BB if it has more than one successor.
3566 That can occur when we moving a jump. */
3567 if (!single_succ_p (bb))
3569 gcc_assert (can_merge_blocks_p (bb->prev_bb, bb));
3570 sel_merge_blocks (bb->prev_bb, bb);
3574 succ_bb = single_succ (bb);
3578 /* Redirect all non-fallthru edges to the next bb. */
3583 FOR_EACH_EDGE (e, ei, bb->preds)
3587 if (!(e->flags & EDGE_FALLTHRU))
3589 recompute_toporder_p |= sel_redirect_edge_and_branch (e, succ_bb);
3596 /* If it is possible - merge BB with its predecessor. */
3597 if (can_merge_blocks_p (bb->prev_bb, bb))
3598 sel_merge_blocks (bb->prev_bb, bb);
3600 /* Otherwise this is a block without fallthru predecessor.
3603 gcc_assert (pred_bb != NULL);
3605 if (in_current_region_p (pred_bb))
3606 move_bb_info (pred_bb, bb);
3607 remove_empty_bb (bb, true);
3610 if (recompute_toporder_p)
3611 sel_recompute_toporder ();
3613 #ifdef ENABLE_CHECKING
3614 verify_backedges ();
3620 /* Tidy the control flow after we have removed original insn from
3621 XBB. Return true if we have removed some blocks. When FULL_TIDYING
3622 is true, also try to optimize control flow on non-empty blocks. */
3624 tidy_control_flow (basic_block xbb, bool full_tidying)
3626 bool changed = true;
3628 /* First check whether XBB is empty. */
3629 changed = maybe_tidy_empty_bb (xbb, false);
3630 if (changed || !full_tidying)
3633 /* Check if there is a unnecessary jump after insn left. */
3634 if (jump_leads_only_to_bb_p (BB_END (xbb), xbb->next_bb)
3635 && INSN_SCHED_TIMES (BB_END (xbb)) == 0
3636 && !IN_CURRENT_FENCE_P (BB_END (xbb)))
3638 if (sel_remove_insn (BB_END (xbb), false, false))
3640 tidy_fallthru_edge (EDGE_SUCC (xbb, 0));
3643 /* Check if there is an unnecessary jump in previous basic block leading
3644 to next basic block left after removing INSN from stream.
3645 If it is so, remove that jump and redirect edge to current
3646 basic block (where there was INSN before deletion). This way
3647 when NOP will be deleted several instructions later with its
3648 basic block we will not get a jump to next instruction, which
3650 if (sel_bb_head (xbb) == sel_bb_end (xbb)
3651 && !sel_bb_empty_p (xbb)
3652 && INSN_NOP_P (sel_bb_end (xbb))
3653 /* Flow goes fallthru from current block to the next. */
3654 && EDGE_COUNT (xbb->succs) == 1
3655 && (EDGE_SUCC (xbb, 0)->flags & EDGE_FALLTHRU)
3656 /* When successor is an EXIT block, it may not be the next block. */
3657 && single_succ (xbb) != EXIT_BLOCK_PTR
3658 /* And unconditional jump in previous basic block leads to
3659 next basic block of XBB and this jump can be safely removed. */
3660 && in_current_region_p (xbb->prev_bb)
3661 && jump_leads_only_to_bb_p (BB_END (xbb->prev_bb), xbb->next_bb)
3662 && INSN_SCHED_TIMES (BB_END (xbb->prev_bb)) == 0
3663 /* Also this jump is not at the scheduling boundary. */
3664 && !IN_CURRENT_FENCE_P (BB_END (xbb->prev_bb)))
3666 bool recompute_toporder_p;
3667 /* Clear data structures of jump - jump itself will be removed
3668 by sel_redirect_edge_and_branch. */
3669 clear_expr (INSN_EXPR (BB_END (xbb->prev_bb)));
3670 recompute_toporder_p
3671 = sel_redirect_edge_and_branch (EDGE_SUCC (xbb->prev_bb, 0), xbb);
3673 gcc_assert (EDGE_SUCC (xbb->prev_bb, 0)->flags & EDGE_FALLTHRU);
3675 /* It can turn out that after removing unused jump, basic block
3676 that contained that jump, becomes empty too. In such case
3678 if (sel_bb_empty_p (xbb->prev_bb))
3679 changed = maybe_tidy_empty_bb (xbb->prev_bb, recompute_toporder_p);
3680 else if (recompute_toporder_p)
3681 sel_recompute_toporder ();
3687 /* Purge meaningless empty blocks in the middle of a region. */
3689 purge_empty_blocks (void)
3691 /* Do not attempt to delete preheader. */
3692 int i = sel_is_loop_preheader_p (BASIC_BLOCK (BB_TO_BLOCK (0))) ? 1 : 0;
3694 while (i < current_nr_blocks)
3696 basic_block b = BASIC_BLOCK (BB_TO_BLOCK (i));
3698 if (maybe_tidy_empty_bb (b, false))
3705 /* Rip-off INSN from the insn stream. When ONLY_DISCONNECT is true,
3706 do not delete insn's data, because it will be later re-emitted.
3707 Return true if we have removed some blocks afterwards. */
3709 sel_remove_insn (insn_t insn, bool only_disconnect, bool full_tidying)
3711 basic_block bb = BLOCK_FOR_INSN (insn);
3713 gcc_assert (INSN_IN_STREAM_P (insn));
3715 if (only_disconnect)
3717 insn_t prev = PREV_INSN (insn);
3718 insn_t next = NEXT_INSN (insn);
3719 basic_block bb = BLOCK_FOR_INSN (insn);
3721 NEXT_INSN (prev) = next;
3722 PREV_INSN (next) = prev;
3724 if (BB_HEAD (bb) == insn)
3726 gcc_assert (BLOCK_FOR_INSN (prev) == bb);
3727 BB_HEAD (bb) = prev;
3729 if (BB_END (bb) == insn)
3735 clear_expr (INSN_EXPR (insn));
3738 /* It is necessary to null this fields before calling add_insn (). */
3739 PREV_INSN (insn) = NULL_RTX;
3740 NEXT_INSN (insn) = NULL_RTX;
3742 return tidy_control_flow (bb, full_tidying);
3745 /* Estimate number of the insns in BB. */
3747 sel_estimate_number_of_insns (basic_block bb)
3750 insn_t insn = NEXT_INSN (BB_HEAD (bb)), next_tail = NEXT_INSN (BB_END (bb));
3752 for (; insn != next_tail; insn = NEXT_INSN (insn))
3759 /* We don't need separate luids for notes or labels. */
3761 sel_luid_for_non_insn (rtx x)
3763 gcc_assert (NOTE_P (x) || LABEL_P (x));
3768 /* Return seqno of the only predecessor of INSN. */
3770 get_seqno_of_a_pred (insn_t insn)
3774 gcc_assert (INSN_SIMPLEJUMP_P (insn));
3776 if (!sel_bb_head_p (insn))
3777 seqno = INSN_SEQNO (PREV_INSN (insn));
3780 basic_block bb = BLOCK_FOR_INSN (insn);
3782 if (single_pred_p (bb)
3783 && !in_current_region_p (single_pred (bb)))
3785 /* We can have preds outside a region when splitting edges
3786 for pipelining of an outer loop. Use succ instead.
3787 There should be only one of them. */
3792 gcc_assert (flag_sel_sched_pipelining_outer_loops
3793 && current_loop_nest);
3794 FOR_EACH_SUCC_1 (succ, si, insn,
3795 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
3801 gcc_assert (succ != NULL);
3802 seqno = INSN_SEQNO (succ);
3809 cfg_preds (BLOCK_FOR_INSN (insn), &preds, &n);
3810 gcc_assert (n == 1);
3812 seqno = INSN_SEQNO (preds[0]);
3821 /* Find the proper seqno for inserting at INSN. Returns -1 if no predecessors
3822 with positive seqno exist. */
3824 get_seqno_by_preds (rtx insn)
3826 basic_block bb = BLOCK_FOR_INSN (insn);
3827 rtx tmp = insn, head = BB_HEAD (bb);
3833 return INSN_SEQNO (tmp);
3835 tmp = PREV_INSN (tmp);
3837 cfg_preds (bb, &preds, &n);
3838 for (i = 0, seqno = -1; i < n; i++)
3839 seqno = MAX (seqno, INSN_SEQNO (preds[i]));
3846 /* Extend pass-scope data structures for basic blocks. */
3848 sel_extend_global_bb_info (void)
3850 VEC_safe_grow_cleared (sel_global_bb_info_def, heap, sel_global_bb_info,
3854 /* Extend region-scope data structures for basic blocks. */
3856 extend_region_bb_info (void)
3858 VEC_safe_grow_cleared (sel_region_bb_info_def, heap, sel_region_bb_info,
3862 /* Extend all data structures to fit for all basic blocks. */
3864 extend_bb_info (void)
3866 sel_extend_global_bb_info ();
3867 extend_region_bb_info ();
3870 /* Finalize pass-scope data structures for basic blocks. */
3872 sel_finish_global_bb_info (void)
3874 VEC_free (sel_global_bb_info_def, heap, sel_global_bb_info);
3877 /* Finalize region-scope data structures for basic blocks. */
3879 finish_region_bb_info (void)
3881 VEC_free (sel_region_bb_info_def, heap, sel_region_bb_info);
3885 /* Data for each insn in current region. */
3886 VEC (sel_insn_data_def, heap) *s_i_d = NULL;
3888 /* A vector for the insns we've emitted. */
3889 static insn_vec_t new_insns = NULL;
3891 /* Extend data structures for insns from current region. */
3893 extend_insn_data (void)
3897 sched_extend_target ();
3898 sched_deps_init (false);
3900 /* Extend data structures for insns from current region. */
3901 reserve = (sched_max_luid + 1
3902 - VEC_length (sel_insn_data_def, s_i_d));
3904 && ! VEC_space (sel_insn_data_def, s_i_d, reserve))
3908 if (sched_max_luid / 2 > 1024)
3909 size = sched_max_luid + 1024;
3911 size = 3 * sched_max_luid / 2;
3914 VEC_safe_grow_cleared (sel_insn_data_def, heap, s_i_d, size);
3918 /* Finalize data structures for insns from current region. */
3924 /* Clear here all dependence contexts that may have left from insns that were
3925 removed during the scheduling. */
3926 for (i = 0; i < VEC_length (sel_insn_data_def, s_i_d); i++)
3928 sel_insn_data_def *sid_entry = VEC_index (sel_insn_data_def, s_i_d, i);
3930 if (sid_entry->live)
3931 return_regset_to_pool (sid_entry->live);
3932 if (sid_entry->analyzed_deps)
3934 BITMAP_FREE (sid_entry->analyzed_deps);
3935 BITMAP_FREE (sid_entry->found_deps);
3936 htab_delete (sid_entry->transformed_insns);
3937 free_deps (&sid_entry->deps_context);
3939 if (EXPR_VINSN (&sid_entry->expr))
3941 clear_expr (&sid_entry->expr);
3943 /* Also, clear CANT_MOVE bit here, because we really don't want it
3944 to be passed to the next region. */
3945 CANT_MOVE_BY_LUID (i) = 0;
3949 VEC_free (sel_insn_data_def, heap, s_i_d);
3952 /* A proxy to pass initialization data to init_insn (). */
3953 static sel_insn_data_def _insn_init_ssid;
3954 static sel_insn_data_t insn_init_ssid = &_insn_init_ssid;
3956 /* If true create a new vinsn. Otherwise use the one from EXPR. */
3957 static bool insn_init_create_new_vinsn_p;
3959 /* Set all necessary data for initialization of the new insn[s]. */
3961 set_insn_init (expr_t expr, vinsn_t vi, int seqno)
3963 expr_t x = &insn_init_ssid->expr;
3965 copy_expr_onside (x, expr);
3968 insn_init_create_new_vinsn_p = false;
3969 change_vinsn_in_expr (x, vi);
3972 insn_init_create_new_vinsn_p = true;
3974 insn_init_ssid->seqno = seqno;
3978 /* Init data for INSN. */
3980 init_insn_data (insn_t insn)
3983 sel_insn_data_t ssid = insn_init_ssid;
3985 /* The fields mentioned below are special and hence are not being
3986 propagated to the new insns. */
3987 gcc_assert (!ssid->asm_p && ssid->sched_next == NULL
3988 && !ssid->after_stall_p && ssid->sched_cycle == 0);
3989 gcc_assert (INSN_P (insn) && INSN_LUID (insn) > 0);
3991 expr = INSN_EXPR (insn);
3992 copy_expr (expr, &ssid->expr);
3993 prepare_insn_expr (insn, ssid->seqno);
3995 if (insn_init_create_new_vinsn_p)
3996 change_vinsn_in_expr (expr, vinsn_create (insn, init_insn_force_unique_p));
3998 if (first_time_insn_init (insn))
3999 init_first_time_insn_data (insn);
4002 /* This is used to initialize spurious jumps generated by
4003 sel_redirect_edge (). */
4005 init_simplejump_data (insn_t insn)
4007 init_expr (INSN_EXPR (insn), vinsn_create (insn, false), 0,
4008 REG_BR_PROB_BASE, 0, 0, 0, 0, 0, 0, NULL, true, false, false,
4010 INSN_SEQNO (insn) = get_seqno_of_a_pred (insn);
4011 init_first_time_insn_data (insn);
4014 /* Perform deferred initialization of insns. This is used to process
4015 a new jump that may be created by redirect_edge. */
4017 sel_init_new_insn (insn_t insn, int flags)
4019 /* We create data structures for bb when the first insn is emitted in it. */
4021 && INSN_IN_STREAM_P (insn)
4022 && insn_is_the_only_one_in_bb_p (insn))
4025 create_initial_data_sets (BLOCK_FOR_INSN (insn));
4028 if (flags & INSN_INIT_TODO_LUID)
4029 sched_init_luids (NULL, NULL, NULL, insn);
4031 if (flags & INSN_INIT_TODO_SSID)
4033 extend_insn_data ();
4034 init_insn_data (insn);
4035 clear_expr (&insn_init_ssid->expr);
4038 if (flags & INSN_INIT_TODO_SIMPLEJUMP)
4040 extend_insn_data ();
4041 init_simplejump_data (insn);
4044 gcc_assert (CONTAINING_RGN (BLOCK_NUM (insn))
4045 == CONTAINING_RGN (BB_TO_BLOCK (0)));
4049 /* Functions to init/finish work with lv sets. */
4051 /* Init BB_LV_SET of BB from DF_LR_IN set of BB. */
4053 init_lv_set (basic_block bb)
4055 gcc_assert (!BB_LV_SET_VALID_P (bb));
4057 BB_LV_SET (bb) = get_regset_from_pool ();
4058 COPY_REG_SET (BB_LV_SET (bb), DF_LR_IN (bb));
4059 BB_LV_SET_VALID_P (bb) = true;
4062 /* Copy liveness information to BB from FROM_BB. */
4064 copy_lv_set_from (basic_block bb, basic_block from_bb)
4066 gcc_assert (!BB_LV_SET_VALID_P (bb));
4068 COPY_REG_SET (BB_LV_SET (bb), BB_LV_SET (from_bb));
4069 BB_LV_SET_VALID_P (bb) = true;
4072 /* Initialize lv set of all bb headers. */
4078 /* Initialize of LV sets. */
4082 /* Don't forget EXIT_BLOCK. */
4083 init_lv_set (EXIT_BLOCK_PTR);
4086 /* Release lv set of HEAD. */
4088 free_lv_set (basic_block bb)
4090 gcc_assert (BB_LV_SET (bb) != NULL);
4092 return_regset_to_pool (BB_LV_SET (bb));
4093 BB_LV_SET (bb) = NULL;
4094 BB_LV_SET_VALID_P (bb) = false;
4097 /* Finalize lv sets of all bb headers. */
4103 /* Don't forget EXIT_BLOCK. */
4104 free_lv_set (EXIT_BLOCK_PTR);
4112 /* Initialize an invalid AV_SET for BB.
4113 This set will be updated next time compute_av () process BB. */
4115 invalidate_av_set (basic_block bb)
4117 gcc_assert (BB_AV_LEVEL (bb) <= 0
4118 && BB_AV_SET (bb) == NULL);
4120 BB_AV_LEVEL (bb) = -1;
4123 /* Create initial data sets for BB (they will be invalid). */
4125 create_initial_data_sets (basic_block bb)
4128 BB_LV_SET_VALID_P (bb) = false;
4130 BB_LV_SET (bb) = get_regset_from_pool ();
4131 invalidate_av_set (bb);
4134 /* Free av set of BB. */
4136 free_av_set (basic_block bb)
4138 av_set_clear (&BB_AV_SET (bb));
4139 BB_AV_LEVEL (bb) = 0;
4142 /* Free data sets of BB. */
4144 free_data_sets (basic_block bb)
4150 /* Exchange lv sets of TO and FROM. */
4152 exchange_lv_sets (basic_block to, basic_block from)
4155 regset to_lv_set = BB_LV_SET (to);
4157 BB_LV_SET (to) = BB_LV_SET (from);
4158 BB_LV_SET (from) = to_lv_set;
4162 bool to_lv_set_valid_p = BB_LV_SET_VALID_P (to);
4164 BB_LV_SET_VALID_P (to) = BB_LV_SET_VALID_P (from);
4165 BB_LV_SET_VALID_P (from) = to_lv_set_valid_p;
4170 /* Exchange av sets of TO and FROM. */
4172 exchange_av_sets (basic_block to, basic_block from)
4175 av_set_t to_av_set = BB_AV_SET (to);
4177 BB_AV_SET (to) = BB_AV_SET (from);
4178 BB_AV_SET (from) = to_av_set;
4182 int to_av_level = BB_AV_LEVEL (to);
4184 BB_AV_LEVEL (to) = BB_AV_LEVEL (from);
4185 BB_AV_LEVEL (from) = to_av_level;
4189 /* Exchange data sets of TO and FROM. */
4191 exchange_data_sets (basic_block to, basic_block from)
4193 exchange_lv_sets (to, from);
4194 exchange_av_sets (to, from);
4197 /* Copy data sets of FROM to TO. */
4199 copy_data_sets (basic_block to, basic_block from)
4201 gcc_assert (!BB_LV_SET_VALID_P (to) && !BB_AV_SET_VALID_P (to));
4202 gcc_assert (BB_AV_SET (to) == NULL);
4204 BB_AV_LEVEL (to) = BB_AV_LEVEL (from);
4205 BB_LV_SET_VALID_P (to) = BB_LV_SET_VALID_P (from);
4207 if (BB_AV_SET_VALID_P (from))
4209 BB_AV_SET (to) = av_set_copy (BB_AV_SET (from));
4211 if (BB_LV_SET_VALID_P (from))
4213 gcc_assert (BB_LV_SET (to) != NULL);
4214 COPY_REG_SET (BB_LV_SET (to), BB_LV_SET (from));
4218 /* Return an av set for INSN, if any. */
4220 get_av_set (insn_t insn)
4224 gcc_assert (AV_SET_VALID_P (insn));
4226 if (sel_bb_head_p (insn))
4227 av_set = BB_AV_SET (BLOCK_FOR_INSN (insn));
4234 /* Implementation of AV_LEVEL () macro. Return AV_LEVEL () of INSN. */
4236 get_av_level (insn_t insn)
4240 gcc_assert (INSN_P (insn));
4242 if (sel_bb_head_p (insn))
4243 av_level = BB_AV_LEVEL (BLOCK_FOR_INSN (insn));
4245 av_level = INSN_WS_LEVEL (insn);
4252 /* Variables to work with control-flow graph. */
4254 /* The basic block that already has been processed by the sched_data_update (),
4255 but hasn't been in sel_add_bb () yet. */
4256 static VEC (basic_block, heap) *last_added_blocks = NULL;
4258 /* A pool for allocating successor infos. */
4261 /* A stack for saving succs_info structures. */
4262 struct succs_info *stack;
4267 /* Top of the stack. */
4270 /* Maximal value of the top. */
4274 /* Functions to work with control-flow graph. */
4276 /* Return basic block note of BB. */
4278 sel_bb_head (basic_block bb)
4282 if (bb == EXIT_BLOCK_PTR)
4284 gcc_assert (exit_insn != NULL_RTX);
4291 note = bb_note (bb);
4292 head = next_nonnote_insn (note);
4294 if (head && (BARRIER_P (head) || BLOCK_FOR_INSN (head) != bb))
4301 /* Return true if INSN is a basic block header. */
4303 sel_bb_head_p (insn_t insn)
4305 return sel_bb_head (BLOCK_FOR_INSN (insn)) == insn;
4308 /* Return last insn of BB. */
4310 sel_bb_end (basic_block bb)
4312 if (sel_bb_empty_p (bb))
4315 gcc_assert (bb != EXIT_BLOCK_PTR);
4320 /* Return true if INSN is the last insn in its basic block. */
4322 sel_bb_end_p (insn_t insn)
4324 return insn == sel_bb_end (BLOCK_FOR_INSN (insn));
4327 /* Return true if BB consist of single NOTE_INSN_BASIC_BLOCK. */
4329 sel_bb_empty_p (basic_block bb)
4331 return sel_bb_head (bb) == NULL;
4334 /* True when BB belongs to the current scheduling region. */
4336 in_current_region_p (basic_block bb)
4338 if (bb->index < NUM_FIXED_BLOCKS)
4341 return CONTAINING_RGN (bb->index) == CONTAINING_RGN (BB_TO_BLOCK (0));
4344 /* Return the block which is a fallthru bb of a conditional jump JUMP. */
4346 fallthru_bb_of_jump (rtx jump)
4351 if (any_uncondjump_p (jump))
4352 return single_succ (BLOCK_FOR_INSN (jump));
4354 if (!any_condjump_p (jump))
4357 /* A basic block that ends with a conditional jump may still have one successor
4358 (and be followed by a barrier), we are not interested. */
4359 if (single_succ_p (BLOCK_FOR_INSN (jump)))
4362 return FALLTHRU_EDGE (BLOCK_FOR_INSN (jump))->dest;
4365 /* Remove all notes from BB. */
4367 init_bb (basic_block bb)
4369 remove_notes (bb_note (bb), BB_END (bb));
4370 BB_NOTE_LIST (bb) = note_list;
4374 sel_init_bbs (bb_vec_t bbs, basic_block bb)
4376 const struct sched_scan_info_def ssi =
4378 extend_bb_info, /* extend_bb */
4379 init_bb, /* init_bb */
4380 NULL, /* extend_insn */
4381 NULL /* init_insn */
4384 sched_scan (&ssi, bbs, bb, new_insns, NULL);
4387 /* Restore notes for the whole region. */
4389 sel_restore_notes (void)
4394 for (bb = 0; bb < current_nr_blocks; bb++)
4396 basic_block first, last;
4398 first = EBB_FIRST_BB (bb);
4399 last = EBB_LAST_BB (bb)->next_bb;
4403 note_list = BB_NOTE_LIST (first);
4404 restore_other_notes (NULL, first);
4405 BB_NOTE_LIST (first) = NULL_RTX;
4407 FOR_BB_INSNS (first, insn)
4409 reemit_notes (insn);
4411 first = first->next_bb;
4413 while (first != last);
4417 /* Free per-bb data structures. */
4419 sel_finish_bbs (void)
4421 sel_restore_notes ();
4423 /* Remove current loop preheader from this loop. */
4424 if (current_loop_nest)
4425 sel_remove_loop_preheader ();
4427 finish_region_bb_info ();
4430 /* Return true if INSN has a single successor of type FLAGS. */
4432 sel_insn_has_single_succ_p (insn_t insn, int flags)
4436 bool first_p = true;
4438 FOR_EACH_SUCC_1 (succ, si, insn, flags)
4449 /* Allocate successor's info. */
4450 static struct succs_info *
4451 alloc_succs_info (void)
4453 if (succs_info_pool.top == succs_info_pool.max_top)
4457 if (++succs_info_pool.max_top >= succs_info_pool.size)
4460 i = ++succs_info_pool.top;
4461 succs_info_pool.stack[i].succs_ok = VEC_alloc (rtx, heap, 10);
4462 succs_info_pool.stack[i].succs_other = VEC_alloc (rtx, heap, 10);
4463 succs_info_pool.stack[i].probs_ok = VEC_alloc (int, heap, 10);
4466 succs_info_pool.top++;
4468 return &succs_info_pool.stack[succs_info_pool.top];
4471 /* Free successor's info. */
4473 free_succs_info (struct succs_info * sinfo)
4475 gcc_assert (succs_info_pool.top >= 0
4476 && &succs_info_pool.stack[succs_info_pool.top] == sinfo);
4477 succs_info_pool.top--;
4479 /* Clear stale info. */
4480 VEC_block_remove (rtx, sinfo->succs_ok,
4481 0, VEC_length (rtx, sinfo->succs_ok));
4482 VEC_block_remove (rtx, sinfo->succs_other,
4483 0, VEC_length (rtx, sinfo->succs_other));
4484 VEC_block_remove (int, sinfo->probs_ok,
4485 0, VEC_length (int, sinfo->probs_ok));
4486 sinfo->all_prob = 0;
4487 sinfo->succs_ok_n = 0;
4488 sinfo->all_succs_n = 0;
4491 /* Compute successor info for INSN. FLAGS are the flags passed
4492 to the FOR_EACH_SUCC_1 iterator. */
4494 compute_succs_info (insn_t insn, short flags)
4498 struct succs_info *sinfo = alloc_succs_info ();
4500 /* Traverse *all* successors and decide what to do with each. */
4501 FOR_EACH_SUCC_1 (succ, si, insn, SUCCS_ALL)
4503 /* FIXME: this doesn't work for skipping to loop exits, as we don't
4504 perform code motion through inner loops. */
4505 short current_flags = si.current_flags & ~SUCCS_SKIP_TO_LOOP_EXITS;
4507 if (current_flags & flags)
4509 VEC_safe_push (rtx, heap, sinfo->succs_ok, succ);
4510 VEC_safe_push (int, heap, sinfo->probs_ok,
4511 /* FIXME: Improve calculation when skipping
4512 inner loop to exits. */
4514 ? si.e1->probability
4515 : REG_BR_PROB_BASE));
4516 sinfo->succs_ok_n++;
4519 VEC_safe_push (rtx, heap, sinfo->succs_other, succ);
4521 /* Compute all_prob. */
4523 sinfo->all_prob = REG_BR_PROB_BASE;
4525 sinfo->all_prob += si.e1->probability;
4527 sinfo->all_succs_n++;
4533 /* Return the predecessors of BB in PREDS and their number in N.
4534 Empty blocks are skipped. SIZE is used to allocate PREDS. */
4536 cfg_preds_1 (basic_block bb, insn_t **preds, int *n, int *size)
4541 gcc_assert (BLOCK_TO_BB (bb->index) != 0);
4543 FOR_EACH_EDGE (e, ei, bb->preds)
4545 basic_block pred_bb = e->src;
4546 insn_t bb_end = BB_END (pred_bb);
4548 /* ??? This code is not supposed to walk out of a region. */
4549 gcc_assert (in_current_region_p (pred_bb));
4551 if (sel_bb_empty_p (pred_bb))
4552 cfg_preds_1 (pred_bb, preds, n, size);
4556 *preds = XRESIZEVEC (insn_t, *preds,
4557 (*size = 2 * *size + 1));
4558 (*preds)[(*n)++] = bb_end;
4562 gcc_assert (*n != 0);
4565 /* Find all predecessors of BB and record them in PREDS and their number
4566 in N. Empty blocks are skipped, and only normal (forward in-region)
4567 edges are processed. */
4569 cfg_preds (basic_block bb, insn_t **preds, int *n)
4575 cfg_preds_1 (bb, preds, n, &size);
4578 /* Returns true if we are moving INSN through join point. */
4580 sel_num_cfg_preds_gt_1 (insn_t insn)
4584 if (!sel_bb_head_p (insn) || INSN_BB (insn) == 0)
4587 bb = BLOCK_FOR_INSN (insn);
4591 if (EDGE_COUNT (bb->preds) > 1)
4594 gcc_assert (EDGE_PRED (bb, 0)->dest == bb);
4595 bb = EDGE_PRED (bb, 0)->src;
4597 if (!sel_bb_empty_p (bb))
4604 /* Returns true when BB should be the end of an ebb. Adapted from the
4605 code in sched-ebb.c. */
4607 bb_ends_ebb_p (basic_block bb)
4609 basic_block next_bb = bb_next_bb (bb);
4613 if (next_bb == EXIT_BLOCK_PTR
4614 || bitmap_bit_p (forced_ebb_heads, next_bb->index)
4615 || (LABEL_P (BB_HEAD (next_bb))
4616 /* NB: LABEL_NUSES () is not maintained outside of jump.c.
4617 Work around that. */
4618 && !single_pred_p (next_bb)))
4621 if (!in_current_region_p (next_bb))
4624 FOR_EACH_EDGE (e, ei, bb->succs)
4625 if ((e->flags & EDGE_FALLTHRU) != 0)
4627 gcc_assert (e->dest == next_bb);
4635 /* Returns true when INSN and SUCC are in the same EBB, given that SUCC is a
4636 successor of INSN. */
4638 in_same_ebb_p (insn_t insn, insn_t succ)
4640 basic_block ptr = BLOCK_FOR_INSN (insn);
4644 if (ptr == BLOCK_FOR_INSN (succ))
4647 if (bb_ends_ebb_p (ptr))
4650 ptr = bb_next_bb (ptr);
4657 /* Recomputes the reverse topological order for the function and
4658 saves it in REV_TOP_ORDER_INDEX. REV_TOP_ORDER_INDEX_LEN is also
4659 modified appropriately. */
4661 recompute_rev_top_order (void)
4666 if (!rev_top_order_index || rev_top_order_index_len < last_basic_block)
4668 rev_top_order_index_len = last_basic_block;
4669 rev_top_order_index = XRESIZEVEC (int, rev_top_order_index,
4670 rev_top_order_index_len);
4673 postorder = XNEWVEC (int, n_basic_blocks);
4675 n_blocks = post_order_compute (postorder, true, false);
4676 gcc_assert (n_basic_blocks == n_blocks);
4678 /* Build reverse function: for each basic block with BB->INDEX == K
4679 rev_top_order_index[K] is it's reverse topological sort number. */
4680 for (i = 0; i < n_blocks; i++)
4682 gcc_assert (postorder[i] < rev_top_order_index_len);
4683 rev_top_order_index[postorder[i]] = i;
4689 /* Clear all flags from insns in BB that could spoil its rescheduling. */
4691 clear_outdated_rtx_info (basic_block bb)
4695 FOR_BB_INSNS (bb, insn)
4698 SCHED_GROUP_P (insn) = 0;
4699 INSN_AFTER_STALL_P (insn) = 0;
4700 INSN_SCHED_TIMES (insn) = 0;
4701 EXPR_PRIORITY_ADJ (INSN_EXPR (insn)) = 0;
4703 /* We cannot use the changed caches, as previously we could ignore
4704 the LHS dependence due to enabled renaming and transform
4705 the expression, and currently we'll be unable to do this. */
4706 htab_empty (INSN_TRANSFORMED_INSNS (insn));
4710 /* Add BB_NOTE to the pool of available basic block notes. */
4712 return_bb_to_pool (basic_block bb)
4714 rtx note = bb_note (bb);
4716 gcc_assert (NOTE_BASIC_BLOCK (note) == bb
4717 && bb->aux == NULL);
4719 /* It turns out that current cfg infrastructure does not support
4720 reuse of basic blocks. Don't bother for now. */
4721 /*VEC_safe_push (rtx, heap, bb_note_pool, note);*/
4724 /* Get a bb_note from pool or return NULL_RTX if pool is empty. */
4726 get_bb_note_from_pool (void)
4728 if (VEC_empty (rtx, bb_note_pool))
4732 rtx note = VEC_pop (rtx, bb_note_pool);
4734 PREV_INSN (note) = NULL_RTX;
4735 NEXT_INSN (note) = NULL_RTX;
4741 /* Free bb_note_pool. */
4743 free_bb_note_pool (void)
4745 VEC_free (rtx, heap, bb_note_pool);
4748 /* Setup scheduler pool and successor structure. */
4750 alloc_sched_pools (void)
4754 succs_size = MAX_WS + 1;
4755 succs_info_pool.stack = XCNEWVEC (struct succs_info, succs_size);
4756 succs_info_pool.size = succs_size;
4757 succs_info_pool.top = -1;
4758 succs_info_pool.max_top = -1;
4760 sched_lists_pool = create_alloc_pool ("sel-sched-lists",
4761 sizeof (struct _list_node), 500);
4764 /* Free the pools. */
4766 free_sched_pools (void)
4770 free_alloc_pool (sched_lists_pool);
4771 gcc_assert (succs_info_pool.top == -1);
4772 for (i = 0; i < succs_info_pool.max_top; i++)
4774 VEC_free (rtx, heap, succs_info_pool.stack[i].succs_ok);
4775 VEC_free (rtx, heap, succs_info_pool.stack[i].succs_other);
4776 VEC_free (int, heap, succs_info_pool.stack[i].probs_ok);
4778 free (succs_info_pool.stack);
4782 /* Returns a position in RGN where BB can be inserted retaining
4783 topological order. */
4785 find_place_to_insert_bb (basic_block bb, int rgn)
4787 bool has_preds_outside_rgn = false;
4791 /* Find whether we have preds outside the region. */
4792 FOR_EACH_EDGE (e, ei, bb->preds)
4793 if (!in_current_region_p (e->src))
4795 has_preds_outside_rgn = true;
4799 /* Recompute the top order -- needed when we have > 1 pred
4800 and in case we don't have preds outside. */
4801 if (flag_sel_sched_pipelining_outer_loops
4802 && (has_preds_outside_rgn || EDGE_COUNT (bb->preds) > 1))
4804 int i, bbi = bb->index, cur_bbi;
4806 recompute_rev_top_order ();
4807 for (i = RGN_NR_BLOCKS (rgn) - 1; i >= 0; i--)
4809 cur_bbi = BB_TO_BLOCK (i);
4810 if (rev_top_order_index[bbi]
4811 < rev_top_order_index[cur_bbi])
4815 /* We skipped the right block, so we increase i. We accomodate
4816 it for increasing by step later, so we decrease i. */
4819 else if (has_preds_outside_rgn)
4821 /* This is the case when we generate an extra empty block
4822 to serve as region head during pipelining. */
4823 e = EDGE_SUCC (bb, 0);
4824 gcc_assert (EDGE_COUNT (bb->succs) == 1
4825 && in_current_region_p (EDGE_SUCC (bb, 0)->dest)
4826 && (BLOCK_TO_BB (e->dest->index) == 0));
4830 /* We don't have preds outside the region. We should have
4831 the only pred, because the multiple preds case comes from
4832 the pipelining of outer loops, and that is handled above.
4833 Just take the bbi of this single pred. */
4834 if (EDGE_COUNT (bb->succs) > 0)
4838 gcc_assert (EDGE_COUNT (bb->preds) == 1);
4840 pred_bbi = EDGE_PRED (bb, 0)->src->index;
4841 return BLOCK_TO_BB (pred_bbi);
4844 /* BB has no successors. It is safe to put it in the end. */
4845 return current_nr_blocks - 1;
4848 /* Deletes an empty basic block freeing its data. */
4850 delete_and_free_basic_block (basic_block bb)
4852 gcc_assert (sel_bb_empty_p (bb));
4857 bitmap_clear_bit (blocks_to_reschedule, bb->index);
4859 /* Can't assert av_set properties because we use sel_aremove_bb
4860 when removing loop preheader from the region. At the point of
4861 removing the preheader we already have deallocated sel_region_bb_info. */
4862 gcc_assert (BB_LV_SET (bb) == NULL
4863 && !BB_LV_SET_VALID_P (bb)
4864 && BB_AV_LEVEL (bb) == 0
4865 && BB_AV_SET (bb) == NULL);
4867 delete_basic_block (bb);
4870 /* Add BB to the current region and update the region data. */
4872 add_block_to_current_region (basic_block bb)
4874 int i, pos, bbi = -2, rgn;
4876 rgn = CONTAINING_RGN (BB_TO_BLOCK (0));
4877 bbi = find_place_to_insert_bb (bb, rgn);
4879 pos = RGN_BLOCKS (rgn) + bbi;
4881 gcc_assert (RGN_HAS_REAL_EBB (rgn) == 0
4882 && ebb_head[bbi] == pos);
4884 /* Make a place for the new block. */
4887 for (i = RGN_BLOCKS (rgn + 1) - 1; i >= pos; i--)
4888 BLOCK_TO_BB (rgn_bb_table[i])++;
4890 memmove (rgn_bb_table + pos + 1,
4892 (RGN_BLOCKS (nr_regions) - pos) * sizeof (*rgn_bb_table));
4894 /* Initialize data for BB. */
4895 rgn_bb_table[pos] = bb->index;
4896 BLOCK_TO_BB (bb->index) = bbi;
4897 CONTAINING_RGN (bb->index) = rgn;
4899 RGN_NR_BLOCKS (rgn)++;
4901 for (i = rgn + 1; i <= nr_regions; i++)
4905 /* Remove BB from the current region and update the region data. */
4907 remove_bb_from_region (basic_block bb)
4909 int i, pos, bbi = -2, rgn;
4911 rgn = CONTAINING_RGN (BB_TO_BLOCK (0));
4912 bbi = BLOCK_TO_BB (bb->index);
4913 pos = RGN_BLOCKS (rgn) + bbi;
4915 gcc_assert (RGN_HAS_REAL_EBB (rgn) == 0
4916 && ebb_head[bbi] == pos);
4918 for (i = RGN_BLOCKS (rgn + 1) - 1; i >= pos; i--)
4919 BLOCK_TO_BB (rgn_bb_table[i])--;
4921 memmove (rgn_bb_table + pos,
4922 rgn_bb_table + pos + 1,
4923 (RGN_BLOCKS (nr_regions) - pos) * sizeof (*rgn_bb_table));
4925 RGN_NR_BLOCKS (rgn)--;
4926 for (i = rgn + 1; i <= nr_regions; i++)
4930 /* Add BB to the current region and update all data. If BB is NULL, add all
4931 blocks from last_added_blocks vector. */
4933 sel_add_bb (basic_block bb)
4935 /* Extend luids so that new notes will receive zero luids. */
4936 sched_init_luids (NULL, NULL, NULL, NULL);
4938 sel_init_bbs (last_added_blocks, NULL);
4940 /* When bb is passed explicitly, the vector should contain
4941 the only element that equals to bb; otherwise, the vector
4942 should not be NULL. */
4943 gcc_assert (last_added_blocks != NULL);
4947 gcc_assert (VEC_length (basic_block, last_added_blocks) == 1
4948 && VEC_index (basic_block,
4949 last_added_blocks, 0) == bb);
4950 add_block_to_current_region (bb);
4952 /* We associate creating/deleting data sets with the first insn
4953 appearing / disappearing in the bb. */
4954 if (!sel_bb_empty_p (bb) && BB_LV_SET (bb) == NULL)
4955 create_initial_data_sets (bb);
4957 VEC_free (basic_block, heap, last_added_blocks);
4960 /* BB is NULL - process LAST_ADDED_BLOCKS instead. */
4963 basic_block temp_bb = NULL;
4966 VEC_iterate (basic_block, last_added_blocks, i, bb); i++)
4968 add_block_to_current_region (bb);
4972 /* We need to fetch at least one bb so we know the region
4974 gcc_assert (temp_bb != NULL);
4977 VEC_free (basic_block, heap, last_added_blocks);
4980 rgn_setup_region (CONTAINING_RGN (bb->index));
4983 /* Remove BB from the current region and update all data.
4984 If REMOVE_FROM_CFG_PBB is true, also remove the block cfom cfg. */
4986 sel_remove_bb (basic_block bb, bool remove_from_cfg_p)
4988 gcc_assert (bb != NULL && BB_NOTE_LIST (bb) == NULL_RTX);
4990 remove_bb_from_region (bb);
4991 return_bb_to_pool (bb);
4992 bitmap_clear_bit (blocks_to_reschedule, bb->index);
4994 if (remove_from_cfg_p)
4995 delete_and_free_basic_block (bb);
4997 rgn_setup_region (CONTAINING_RGN (bb->index));
5000 /* Concatenate info of EMPTY_BB to info of MERGE_BB. */
5002 move_bb_info (basic_block merge_bb, basic_block empty_bb)
5004 gcc_assert (in_current_region_p (merge_bb));
5006 concat_note_lists (BB_NOTE_LIST (empty_bb),
5007 &BB_NOTE_LIST (merge_bb));
5008 BB_NOTE_LIST (empty_bb) = NULL_RTX;
5012 /* Remove an empty basic block EMPTY_BB. When MERGE_UP_P is true, we put
5013 EMPTY_BB's note lists into its predecessor instead of putting them
5014 into the successor. When REMOVE_FROM_CFG_P is true, also remove
5017 sel_remove_empty_bb (basic_block empty_bb, bool merge_up_p,
5018 bool remove_from_cfg_p)
5020 basic_block merge_bb;
5022 gcc_assert (sel_bb_empty_p (empty_bb));
5026 merge_bb = empty_bb->prev_bb;
5027 gcc_assert (EDGE_COUNT (empty_bb->preds) == 1
5028 && EDGE_PRED (empty_bb, 0)->src == merge_bb);
5035 merge_bb = bb_next_bb (empty_bb);
5037 /* Redirect incoming edges (except fallthrough one) of EMPTY_BB to its
5039 for (ei = ei_start (empty_bb->preds);
5040 (e = ei_safe_edge (ei)); )
5042 if (! (e->flags & EDGE_FALLTHRU))
5043 sel_redirect_edge_and_branch (e, merge_bb);
5048 gcc_assert (EDGE_COUNT (empty_bb->succs) == 1
5049 && EDGE_SUCC (empty_bb, 0)->dest == merge_bb);
5052 move_bb_info (merge_bb, empty_bb);
5053 remove_empty_bb (empty_bb, remove_from_cfg_p);
5056 /* Remove EMPTY_BB. If REMOVE_FROM_CFG_P is false, remove EMPTY_BB from
5057 region, but keep it in CFG. */
5059 remove_empty_bb (basic_block empty_bb, bool remove_from_cfg_p)
5061 /* The block should contain just a note or a label.
5062 We try to check whether it is unused below. */
5063 gcc_assert (BB_HEAD (empty_bb) == BB_END (empty_bb)
5064 || LABEL_P (BB_HEAD (empty_bb)));
5066 /* If basic block has predecessors or successors, redirect them. */
5067 if (remove_from_cfg_p
5068 && (EDGE_COUNT (empty_bb->preds) > 0
5069 || EDGE_COUNT (empty_bb->succs) > 0))
5074 /* We need to init PRED and SUCC before redirecting edges. */
5075 if (EDGE_COUNT (empty_bb->preds) > 0)
5079 gcc_assert (EDGE_COUNT (empty_bb->preds) == 1);
5081 e = EDGE_PRED (empty_bb, 0);
5082 gcc_assert (e->src == empty_bb->prev_bb
5083 && (e->flags & EDGE_FALLTHRU));
5085 pred = empty_bb->prev_bb;
5090 if (EDGE_COUNT (empty_bb->succs) > 0)
5092 /* We do not check fallthruness here as above, because
5093 after removing a jump the edge may actually be not fallthru. */
5094 gcc_assert (EDGE_COUNT (empty_bb->succs) == 1);
5095 succ = EDGE_SUCC (empty_bb, 0)->dest;
5100 if (EDGE_COUNT (empty_bb->preds) > 0 && succ != NULL)
5102 edge e = EDGE_PRED (empty_bb, 0);
5104 if (e->flags & EDGE_FALLTHRU)
5105 redirect_edge_succ_nodup (e, succ);
5107 sel_redirect_edge_and_branch (EDGE_PRED (empty_bb, 0), succ);
5110 if (EDGE_COUNT (empty_bb->succs) > 0 && pred != NULL)
5112 edge e = EDGE_SUCC (empty_bb, 0);
5114 if (find_edge (pred, e->dest) == NULL)
5115 redirect_edge_pred (e, pred);
5119 /* Finish removing. */
5120 sel_remove_bb (empty_bb, remove_from_cfg_p);
5123 /* An implementation of create_basic_block hook, which additionally updates
5124 per-bb data structures. */
5126 sel_create_basic_block (void *headp, void *endp, basic_block after)
5131 gcc_assert (flag_sel_sched_pipelining_outer_loops
5132 || last_added_blocks == NULL);
5134 new_bb_note = get_bb_note_from_pool ();
5136 if (new_bb_note == NULL_RTX)
5137 new_bb = orig_cfg_hooks.create_basic_block (headp, endp, after);
5140 new_bb = create_basic_block_structure ((rtx) headp, (rtx) endp,
5141 new_bb_note, after);
5145 VEC_safe_push (basic_block, heap, last_added_blocks, new_bb);
5150 /* Implement sched_init_only_bb (). */
5152 sel_init_only_bb (basic_block bb, basic_block after)
5154 gcc_assert (after == NULL);
5157 rgn_make_new_region_out_of_new_block (bb);
5160 /* Update the latch when we've splitted or merged it from FROM block to TO.
5161 This should be checked for all outer loops, too. */
5163 change_loops_latches (basic_block from, basic_block to)
5165 gcc_assert (from != to);
5167 if (current_loop_nest)
5171 for (loop = current_loop_nest; loop; loop = loop_outer (loop))
5172 if (considered_for_pipelining_p (loop) && loop->latch == from)
5174 gcc_assert (loop == current_loop_nest);
5176 gcc_assert (loop_latch_edge (loop));
5181 /* Splits BB on two basic blocks, adding it to the region and extending
5182 per-bb data structures. Returns the newly created bb. */
5184 sel_split_block (basic_block bb, rtx after)
5189 new_bb = sched_split_block_1 (bb, after);
5190 sel_add_bb (new_bb);
5192 /* This should be called after sel_add_bb, because this uses
5193 CONTAINING_RGN for the new block, which is not yet initialized.
5194 FIXME: this function may be a no-op now. */
5195 change_loops_latches (bb, new_bb);
5197 /* Update ORIG_BB_INDEX for insns moved into the new block. */
5198 FOR_BB_INSNS (new_bb, insn)
5200 EXPR_ORIG_BB_INDEX (INSN_EXPR (insn)) = new_bb->index;
5202 if (sel_bb_empty_p (bb))
5204 gcc_assert (!sel_bb_empty_p (new_bb));
5206 /* NEW_BB has data sets that need to be updated and BB holds
5207 data sets that should be removed. Exchange these data sets
5208 so that we won't lose BB's valid data sets. */
5209 exchange_data_sets (new_bb, bb);
5210 free_data_sets (bb);
5213 if (!sel_bb_empty_p (new_bb)
5214 && bitmap_bit_p (blocks_to_reschedule, bb->index))
5215 bitmap_set_bit (blocks_to_reschedule, new_bb->index);
5220 /* If BB ends with a jump insn whose ID is bigger then PREV_MAX_UID, return it.
5221 Otherwise returns NULL. */
5223 check_for_new_jump (basic_block bb, int prev_max_uid)
5227 end = sel_bb_end (bb);
5228 if (end && INSN_UID (end) >= prev_max_uid)
5233 /* Look for a new jump either in FROM_BB block or in newly created JUMP_BB block.
5234 New means having UID at least equal to PREV_MAX_UID. */
5236 find_new_jump (basic_block from, basic_block jump_bb, int prev_max_uid)
5240 /* Return immediately if no new insns were emitted. */
5241 if (get_max_uid () == prev_max_uid)
5244 /* Now check both blocks for new jumps. It will ever be only one. */
5245 if ((jump = check_for_new_jump (from, prev_max_uid)))
5249 && (jump = check_for_new_jump (jump_bb, prev_max_uid)))
5254 /* Splits E and adds the newly created basic block to the current region.
5255 Returns this basic block. */
5257 sel_split_edge (edge e)
5259 basic_block new_bb, src, other_bb = NULL;
5264 prev_max_uid = get_max_uid ();
5265 new_bb = split_edge (e);
5267 if (flag_sel_sched_pipelining_outer_loops
5268 && current_loop_nest)
5273 /* Some of the basic blocks might not have been added to the loop.
5274 Add them here, until this is fixed in force_fallthru. */
5276 VEC_iterate (basic_block, last_added_blocks, i, bb); i++)
5277 if (!bb->loop_father)
5279 add_bb_to_loop (bb, e->dest->loop_father);
5281 gcc_assert (!other_bb && (new_bb->index != bb->index));
5286 /* Add all last_added_blocks to the region. */
5289 jump = find_new_jump (src, new_bb, prev_max_uid);
5291 sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP);
5293 /* Put the correct lv set on this block. */
5294 if (other_bb && !sel_bb_empty_p (other_bb))
5295 compute_live (sel_bb_head (other_bb));
5300 /* Implement sched_create_empty_bb (). */
5302 sel_create_empty_bb (basic_block after)
5306 new_bb = sched_create_empty_bb_1 (after);
5308 /* We'll explicitly initialize NEW_BB via sel_init_only_bb () a bit
5310 gcc_assert (VEC_length (basic_block, last_added_blocks) == 1
5311 && VEC_index (basic_block, last_added_blocks, 0) == new_bb);
5313 VEC_free (basic_block, heap, last_added_blocks);
5317 /* Implement sched_create_recovery_block. ORIG_INSN is where block
5318 will be splitted to insert a check. */
5320 sel_create_recovery_block (insn_t orig_insn)
5322 basic_block first_bb, second_bb, recovery_block;
5323 basic_block before_recovery = NULL;
5326 first_bb = BLOCK_FOR_INSN (orig_insn);
5327 if (sel_bb_end_p (orig_insn))
5329 /* Avoid introducing an empty block while splitting. */
5330 gcc_assert (single_succ_p (first_bb));
5331 second_bb = single_succ (first_bb);
5334 second_bb = sched_split_block (first_bb, orig_insn);
5336 recovery_block = sched_create_recovery_block (&before_recovery);
5337 if (before_recovery)
5338 copy_lv_set_from (before_recovery, EXIT_BLOCK_PTR);
5340 gcc_assert (sel_bb_empty_p (recovery_block));
5341 sched_create_recovery_edges (first_bb, recovery_block, second_bb);
5342 if (current_loops != NULL)
5343 add_bb_to_loop (recovery_block, first_bb->loop_father);
5345 sel_add_bb (recovery_block);
5347 jump = BB_END (recovery_block);
5348 gcc_assert (sel_bb_head (recovery_block) == jump);
5349 sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP);
5351 return recovery_block;
5354 /* Merge basic block B into basic block A. */
5356 sel_merge_blocks (basic_block a, basic_block b)
5358 sel_remove_empty_bb (b, true, false);
5359 merge_blocks (a, b);
5361 change_loops_latches (b, a);
5364 /* A wrapper for redirect_edge_and_branch_force, which also initializes
5365 data structures for possibly created bb and insns. Returns the newly
5366 added bb or NULL, when a bb was not needed. */
5368 sel_redirect_edge_and_branch_force (edge e, basic_block to)
5370 basic_block jump_bb, src;
5374 gcc_assert (!sel_bb_empty_p (e->src));
5377 prev_max_uid = get_max_uid ();
5378 jump_bb = redirect_edge_and_branch_force (e, to);
5380 if (jump_bb != NULL)
5381 sel_add_bb (jump_bb);
5383 /* This function could not be used to spoil the loop structure by now,
5384 thus we don't care to update anything. But check it to be sure. */
5385 if (current_loop_nest
5387 gcc_assert (loop_latch_edge (current_loop_nest));
5389 jump = find_new_jump (src, jump_bb, prev_max_uid);
5391 sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP);
5394 /* A wrapper for redirect_edge_and_branch. Return TRUE if blocks connected by
5395 redirected edge are in reverse topological order. */
5397 sel_redirect_edge_and_branch (edge e, basic_block to)
5404 bool recompute_toporder_p = false;
5406 latch_edge_p = (pipelining_p
5407 && current_loop_nest
5408 && e == loop_latch_edge (current_loop_nest));
5411 prev_max_uid = get_max_uid ();
5413 redirected = redirect_edge_and_branch (e, to);
5415 gcc_assert (redirected && last_added_blocks == NULL);
5417 /* When we've redirected a latch edge, update the header. */
5420 current_loop_nest->header = to;
5421 gcc_assert (loop_latch_edge (current_loop_nest));
5424 /* In rare situations, the topological relation between the blocks connected
5425 by the redirected edge can change (see PR42245 for an example). Update
5426 block_to_bb/bb_to_block. */
5427 if (CONTAINING_RGN (e->src->index) == CONTAINING_RGN (to->index)
5428 && BLOCK_TO_BB (e->src->index) > BLOCK_TO_BB (to->index))
5429 recompute_toporder_p = true;
5431 jump = find_new_jump (src, NULL, prev_max_uid);
5433 sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP);
5435 return recompute_toporder_p;
5438 /* This variable holds the cfg hooks used by the selective scheduler. */
5439 static struct cfg_hooks sel_cfg_hooks;
5441 /* Register sel-sched cfg hooks. */
5443 sel_register_cfg_hooks (void)
5445 sched_split_block = sel_split_block;
5447 orig_cfg_hooks = get_cfg_hooks ();
5448 sel_cfg_hooks = orig_cfg_hooks;
5450 sel_cfg_hooks.create_basic_block = sel_create_basic_block;
5452 set_cfg_hooks (sel_cfg_hooks);
5454 sched_init_only_bb = sel_init_only_bb;
5455 sched_split_block = sel_split_block;
5456 sched_create_empty_bb = sel_create_empty_bb;
5459 /* Unregister sel-sched cfg hooks. */
5461 sel_unregister_cfg_hooks (void)
5463 sched_create_empty_bb = NULL;
5464 sched_split_block = NULL;
5465 sched_init_only_bb = NULL;
5467 set_cfg_hooks (orig_cfg_hooks);
5471 /* Emit an insn rtx based on PATTERN. If a jump insn is wanted,
5472 LABEL is where this jump should be directed. */
5474 create_insn_rtx_from_pattern (rtx pattern, rtx label)
5478 gcc_assert (!INSN_P (pattern));
5482 if (label == NULL_RTX)
5483 insn_rtx = emit_insn (pattern);
5486 insn_rtx = emit_jump_insn (pattern);
5487 JUMP_LABEL (insn_rtx) = label;
5488 ++LABEL_NUSES (label);
5493 sched_init_luids (NULL, NULL, NULL, NULL);
5494 sched_extend_target ();
5495 sched_deps_init (false);
5497 /* Initialize INSN_CODE now. */
5498 recog_memoized (insn_rtx);
5502 /* Create a new vinsn for INSN_RTX. FORCE_UNIQUE_P is true when the vinsn
5503 must not be clonable. */
5505 create_vinsn_from_insn_rtx (rtx insn_rtx, bool force_unique_p)
5507 gcc_assert (INSN_P (insn_rtx) && !INSN_IN_STREAM_P (insn_rtx));
5509 /* If VINSN_TYPE is not USE, retain its uniqueness. */
5510 return vinsn_create (insn_rtx, force_unique_p);
5513 /* Create a copy of INSN_RTX. */
5515 create_copy_of_insn_rtx (rtx insn_rtx)
5519 gcc_assert (NONJUMP_INSN_P (insn_rtx));
5521 res = create_insn_rtx_from_pattern (copy_rtx (PATTERN (insn_rtx)),
5526 /* Change vinsn field of EXPR to hold NEW_VINSN. */
5528 change_vinsn_in_expr (expr_t expr, vinsn_t new_vinsn)
5530 vinsn_detach (EXPR_VINSN (expr));
5532 EXPR_VINSN (expr) = new_vinsn;
5533 vinsn_attach (new_vinsn);
5536 /* Helpers for global init. */
5537 /* This structure is used to be able to call existing bundling mechanism
5538 and calculate insn priorities. */
5539 static struct haifa_sched_info sched_sel_haifa_sched_info =
5541 NULL, /* init_ready_list */
5542 NULL, /* can_schedule_ready_p */
5543 NULL, /* schedule_more_p */
5544 NULL, /* new_ready */
5545 NULL, /* rgn_rank */
5546 sel_print_insn, /* rgn_print_insn */
5547 contributes_to_priority,
5553 NULL, /* add_remove_insn */
5554 NULL, /* begin_schedule_ready */
5555 NULL, /* advance_target_bb */
5559 /* Setup special insns used in the scheduler. */
5561 setup_nop_and_exit_insns (void)
5563 gcc_assert (nop_pattern == NULL_RTX
5564 && exit_insn == NULL_RTX);
5566 nop_pattern = gen_nop ();
5569 emit_insn (nop_pattern);
5570 exit_insn = get_insns ();
5572 set_block_for_insn (exit_insn, EXIT_BLOCK_PTR);
5575 /* Free special insns used in the scheduler. */
5577 free_nop_and_exit_insns (void)
5579 exit_insn = NULL_RTX;
5580 nop_pattern = NULL_RTX;
5583 /* Setup a special vinsn used in new insns initialization. */
5585 setup_nop_vinsn (void)
5587 nop_vinsn = vinsn_create (exit_insn, false);
5588 vinsn_attach (nop_vinsn);
5591 /* Free a special vinsn used in new insns initialization. */
5593 free_nop_vinsn (void)
5595 gcc_assert (VINSN_COUNT (nop_vinsn) == 1);
5596 vinsn_detach (nop_vinsn);
5600 /* Call a set_sched_flags hook. */
5602 sel_set_sched_flags (void)
5604 /* ??? This means that set_sched_flags were called, and we decided to
5605 support speculation. However, set_sched_flags also modifies flags
5606 on current_sched_info, doing this only at global init. And we
5607 sometimes change c_s_i later. So put the correct flags again. */
5608 if (spec_info && targetm.sched.set_sched_flags)
5609 targetm.sched.set_sched_flags (spec_info);
5612 /* Setup pointers to global sched info structures. */
5614 sel_setup_sched_infos (void)
5616 rgn_setup_common_sched_info ();
5618 memcpy (&sel_common_sched_info, common_sched_info,
5619 sizeof (sel_common_sched_info));
5621 sel_common_sched_info.fix_recovery_cfg = NULL;
5622 sel_common_sched_info.add_block = NULL;
5623 sel_common_sched_info.estimate_number_of_insns
5624 = sel_estimate_number_of_insns;
5625 sel_common_sched_info.luid_for_non_insn = sel_luid_for_non_insn;
5626 sel_common_sched_info.sched_pass_id = SCHED_SEL_PASS;
5628 common_sched_info = &sel_common_sched_info;
5630 current_sched_info = &sched_sel_haifa_sched_info;
5631 current_sched_info->sched_max_insns_priority =
5632 get_rgn_sched_max_insns_priority ();
5634 sel_set_sched_flags ();
5638 /* Adds basic block BB to region RGN at the position *BB_ORD_INDEX,
5639 *BB_ORD_INDEX after that is increased. */
5641 sel_add_block_to_region (basic_block bb, int *bb_ord_index, int rgn)
5643 RGN_NR_BLOCKS (rgn) += 1;
5644 RGN_DONT_CALC_DEPS (rgn) = 0;
5645 RGN_HAS_REAL_EBB (rgn) = 0;
5646 CONTAINING_RGN (bb->index) = rgn;
5647 BLOCK_TO_BB (bb->index) = *bb_ord_index;
5648 rgn_bb_table[RGN_BLOCKS (rgn) + *bb_ord_index] = bb->index;
5651 /* FIXME: it is true only when not scheduling ebbs. */
5652 RGN_BLOCKS (rgn + 1) = RGN_BLOCKS (rgn) + RGN_NR_BLOCKS (rgn);
5655 /* Functions to support pipelining of outer loops. */
5657 /* Creates a new empty region and returns it's number. */
5659 sel_create_new_region (void)
5661 int new_rgn_number = nr_regions;
5663 RGN_NR_BLOCKS (new_rgn_number) = 0;
5665 /* FIXME: This will work only when EBBs are not created. */
5666 if (new_rgn_number != 0)
5667 RGN_BLOCKS (new_rgn_number) = RGN_BLOCKS (new_rgn_number - 1) +
5668 RGN_NR_BLOCKS (new_rgn_number - 1);
5670 RGN_BLOCKS (new_rgn_number) = 0;
5672 /* Set the blocks of the next region so the other functions may
5673 calculate the number of blocks in the region. */
5674 RGN_BLOCKS (new_rgn_number + 1) = RGN_BLOCKS (new_rgn_number) +
5675 RGN_NR_BLOCKS (new_rgn_number);
5679 return new_rgn_number;
5682 /* If X has a smaller topological sort number than Y, returns -1;
5683 if greater, returns 1. */
5685 bb_top_order_comparator (const void *x, const void *y)
5687 basic_block bb1 = *(const basic_block *) x;
5688 basic_block bb2 = *(const basic_block *) y;
5690 gcc_assert (bb1 == bb2
5691 || rev_top_order_index[bb1->index]
5692 != rev_top_order_index[bb2->index]);
5694 /* It's a reverse topological order in REV_TOP_ORDER_INDEX, so
5695 bbs with greater number should go earlier. */
5696 if (rev_top_order_index[bb1->index] > rev_top_order_index[bb2->index])
5702 /* Create a region for LOOP and return its number. If we don't want
5703 to pipeline LOOP, return -1. */
5705 make_region_from_loop (struct loop *loop)
5708 int new_rgn_number = -1;
5711 /* Basic block index, to be assigned to BLOCK_TO_BB. */
5712 int bb_ord_index = 0;
5713 basic_block *loop_blocks;
5714 basic_block preheader_block;
5717 > (unsigned) PARAM_VALUE (PARAM_MAX_PIPELINE_REGION_BLOCKS))
5720 /* Don't pipeline loops whose latch belongs to some of its inner loops. */
5721 for (inner = loop->inner; inner; inner = inner->inner)
5722 if (flow_bb_inside_loop_p (inner, loop->latch))
5725 loop->ninsns = num_loop_insns (loop);
5726 if ((int) loop->ninsns > PARAM_VALUE (PARAM_MAX_PIPELINE_REGION_INSNS))
5729 loop_blocks = get_loop_body_in_custom_order (loop, bb_top_order_comparator);
5731 for (i = 0; i < loop->num_nodes; i++)
5732 if (loop_blocks[i]->flags & BB_IRREDUCIBLE_LOOP)
5738 preheader_block = loop_preheader_edge (loop)->src;
5739 gcc_assert (preheader_block);
5740 gcc_assert (loop_blocks[0] == loop->header);
5742 new_rgn_number = sel_create_new_region ();
5744 sel_add_block_to_region (preheader_block, &bb_ord_index, new_rgn_number);
5745 SET_BIT (bbs_in_loop_rgns, preheader_block->index);
5747 for (i = 0; i < loop->num_nodes; i++)
5749 /* Add only those blocks that haven't been scheduled in the inner loop.
5750 The exception is the basic blocks with bookkeeping code - they should
5751 be added to the region (and they actually don't belong to the loop
5752 body, but to the region containing that loop body). */
5754 gcc_assert (new_rgn_number >= 0);
5756 if (! TEST_BIT (bbs_in_loop_rgns, loop_blocks[i]->index))
5758 sel_add_block_to_region (loop_blocks[i], &bb_ord_index,
5760 SET_BIT (bbs_in_loop_rgns, loop_blocks[i]->index);
5765 MARK_LOOP_FOR_PIPELINING (loop);
5767 return new_rgn_number;
5770 /* Create a new region from preheader blocks LOOP_BLOCKS. */
5772 make_region_from_loop_preheader (VEC(basic_block, heap) **loop_blocks)
5775 int new_rgn_number = -1;
5778 /* Basic block index, to be assigned to BLOCK_TO_BB. */
5779 int bb_ord_index = 0;
5781 new_rgn_number = sel_create_new_region ();
5783 for (i = 0; VEC_iterate (basic_block, *loop_blocks, i, bb); i++)
5785 gcc_assert (new_rgn_number >= 0);
5787 sel_add_block_to_region (bb, &bb_ord_index, new_rgn_number);
5790 VEC_free (basic_block, heap, *loop_blocks);
5791 gcc_assert (*loop_blocks == NULL);
5795 /* Create region(s) from loop nest LOOP, such that inner loops will be
5796 pipelined before outer loops. Returns true when a region for LOOP
5799 make_regions_from_loop_nest (struct loop *loop)
5801 struct loop *cur_loop;
5804 /* Traverse all inner nodes of the loop. */
5805 for (cur_loop = loop->inner; cur_loop; cur_loop = cur_loop->next)
5806 if (! TEST_BIT (bbs_in_loop_rgns, cur_loop->header->index))
5809 /* At this moment all regular inner loops should have been pipelined.
5810 Try to create a region from this loop. */
5811 rgn_number = make_region_from_loop (loop);
5816 VEC_safe_push (loop_p, heap, loop_nests, loop);
5820 /* Initalize data structures needed. */
5822 sel_init_pipelining (void)
5824 /* Collect loop information to be used in outer loops pipelining. */
5825 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
5826 | LOOPS_HAVE_FALLTHRU_PREHEADERS
5827 | LOOPS_HAVE_RECORDED_EXITS
5828 | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS);
5829 current_loop_nest = NULL;
5831 bbs_in_loop_rgns = sbitmap_alloc (last_basic_block);
5832 sbitmap_zero (bbs_in_loop_rgns);
5834 recompute_rev_top_order ();
5837 /* Returns a struct loop for region RGN. */
5839 get_loop_nest_for_rgn (unsigned int rgn)
5841 /* Regions created with extend_rgns don't have corresponding loop nests,
5842 because they don't represent loops. */
5843 if (rgn < VEC_length (loop_p, loop_nests))
5844 return VEC_index (loop_p, loop_nests, rgn);
5849 /* True when LOOP was included into pipelining regions. */
5851 considered_for_pipelining_p (struct loop *loop)
5853 if (loop_depth (loop) == 0)
5856 /* Now, the loop could be too large or irreducible. Check whether its
5857 region is in LOOP_NESTS.
5858 We determine the region number of LOOP as the region number of its
5859 latch. We can't use header here, because this header could be
5860 just removed preheader and it will give us the wrong region number.
5861 Latch can't be used because it could be in the inner loop too. */
5862 if (LOOP_MARKED_FOR_PIPELINING_P (loop))
5864 int rgn = CONTAINING_RGN (loop->latch->index);
5866 gcc_assert ((unsigned) rgn < VEC_length (loop_p, loop_nests));
5873 /* Makes regions from the rest of the blocks, after loops are chosen
5876 make_regions_from_the_rest (void)
5888 /* Index in rgn_bb_table where to start allocating new regions. */
5889 cur_rgn_blocks = nr_regions ? RGN_BLOCKS (nr_regions) : 0;
5890 new_regions = nr_regions;
5892 /* Make regions from all the rest basic blocks - those that don't belong to
5893 any loop or belong to irreducible loops. Prepare the data structures
5896 /* LOOP_HDR[I] == -1 if I-th bb doesn't belong to any loop,
5897 LOOP_HDR[I] == LOOP_HDR[J] iff basic blocks I and J reside within the same
5899 loop_hdr = XNEWVEC (int, last_basic_block);
5900 degree = XCNEWVEC (int, last_basic_block);
5903 /* For each basic block that belongs to some loop assign the number
5904 of innermost loop it belongs to. */
5905 for (i = 0; i < last_basic_block; i++)
5910 if (bb->loop_father && !bb->loop_father->num == 0
5911 && !(bb->flags & BB_IRREDUCIBLE_LOOP))
5912 loop_hdr[bb->index] = bb->loop_father->num;
5915 /* For each basic block degree is calculated as the number of incoming
5916 edges, that are going out of bbs that are not yet scheduled.
5917 The basic blocks that are scheduled have degree value of zero. */
5920 degree[bb->index] = 0;
5922 if (!TEST_BIT (bbs_in_loop_rgns, bb->index))
5924 FOR_EACH_EDGE (e, ei, bb->preds)
5925 if (!TEST_BIT (bbs_in_loop_rgns, e->src->index))
5926 degree[bb->index]++;
5929 degree[bb->index] = -1;
5932 extend_rgns (degree, &cur_rgn_blocks, bbs_in_loop_rgns, loop_hdr);
5934 /* Any block that did not end up in a region is placed into a region
5937 if (degree[bb->index] >= 0)
5939 rgn_bb_table[cur_rgn_blocks] = bb->index;
5940 RGN_NR_BLOCKS (nr_regions) = 1;
5941 RGN_BLOCKS (nr_regions) = cur_rgn_blocks++;
5942 RGN_DONT_CALC_DEPS (nr_regions) = 0;
5943 RGN_HAS_REAL_EBB (nr_regions) = 0;
5944 CONTAINING_RGN (bb->index) = nr_regions++;
5945 BLOCK_TO_BB (bb->index) = 0;
5952 /* Free data structures used in pipelining of loops. */
5953 void sel_finish_pipelining (void)
5958 /* Release aux fields so we don't free them later by mistake. */
5959 FOR_EACH_LOOP (li, loop, 0)
5962 loop_optimizer_finalize ();
5964 VEC_free (loop_p, heap, loop_nests);
5966 free (rev_top_order_index);
5967 rev_top_order_index = NULL;
5970 /* This function replaces the find_rgns when
5971 FLAG_SEL_SCHED_PIPELINING_OUTER_LOOPS is set. */
5973 sel_find_rgns (void)
5975 sel_init_pipelining ();
5983 FOR_EACH_LOOP (li, loop, (flag_sel_sched_pipelining_outer_loops
5985 : LI_ONLY_INNERMOST))
5986 make_regions_from_loop_nest (loop);
5989 /* Make regions from all the rest basic blocks and schedule them.
5990 These blocks include blocks that don't belong to any loop or belong
5991 to irreducible loops. */
5992 make_regions_from_the_rest ();
5994 /* We don't need bbs_in_loop_rgns anymore. */
5995 sbitmap_free (bbs_in_loop_rgns);
5996 bbs_in_loop_rgns = NULL;
5999 /* Adds the preheader blocks from previous loop to current region taking
6000 it from LOOP_PREHEADER_BLOCKS (current_loop_nest).
6001 This function is only used with -fsel-sched-pipelining-outer-loops. */
6003 sel_add_loop_preheaders (void)
6007 VEC(basic_block, heap) *preheader_blocks
6008 = LOOP_PREHEADER_BLOCKS (current_loop_nest);
6011 VEC_iterate (basic_block, preheader_blocks, i, bb);
6014 VEC_safe_push (basic_block, heap, last_added_blocks, bb);
6018 VEC_free (basic_block, heap, preheader_blocks);
6021 /* While pipelining outer loops, returns TRUE if BB is a loop preheader.
6022 Please note that the function should also work when pipelining_p is
6023 false, because it is used when deciding whether we should or should
6024 not reschedule pipelined code. */
6026 sel_is_loop_preheader_p (basic_block bb)
6028 if (current_loop_nest)
6032 if (preheader_removed)
6035 /* Preheader is the first block in the region. */
6036 if (BLOCK_TO_BB (bb->index) == 0)
6039 /* We used to find a preheader with the topological information.
6040 Check that the above code is equivalent to what we did before. */
6042 if (in_current_region_p (current_loop_nest->header))
6043 gcc_assert (!(BLOCK_TO_BB (bb->index)
6044 < BLOCK_TO_BB (current_loop_nest->header->index)));
6046 /* Support the situation when the latch block of outer loop
6047 could be from here. */
6048 for (outer = loop_outer (current_loop_nest);
6050 outer = loop_outer (outer))
6051 if (considered_for_pipelining_p (outer) && outer->latch == bb)
6058 /* Checks whether JUMP leads to basic block DEST_BB and no other blocks. */
6060 jump_leads_only_to_bb_p (insn_t jump, basic_block dest_bb)
6062 basic_block jump_bb = BLOCK_FOR_INSN (jump);
6064 /* It is not jump, jump with side-effects or jump can lead to several
6066 if (!onlyjump_p (jump)
6067 || !any_uncondjump_p (jump))
6070 /* Several outgoing edges, abnormal edge or destination of jump is
6072 if (EDGE_COUNT (jump_bb->succs) != 1
6073 || EDGE_SUCC (jump_bb, 0)->flags & EDGE_ABNORMAL
6074 || EDGE_SUCC (jump_bb, 0)->dest != dest_bb)
6077 /* If not anything of the upper. */
6081 /* Removes the loop preheader from the current region and saves it in
6082 PREHEADER_BLOCKS of the father loop, so they will be added later to
6083 region that represents an outer loop. */
6085 sel_remove_loop_preheader (void)
6088 int cur_rgn = CONTAINING_RGN (BB_TO_BLOCK (0));
6090 bool all_empty_p = true;
6091 VEC(basic_block, heap) *preheader_blocks
6092 = LOOP_PREHEADER_BLOCKS (loop_outer (current_loop_nest));
6094 gcc_assert (current_loop_nest);
6095 old_len = VEC_length (basic_block, preheader_blocks);
6097 /* Add blocks that aren't within the current loop to PREHEADER_BLOCKS. */
6098 for (i = 0; i < RGN_NR_BLOCKS (cur_rgn); i++)
6100 bb = BASIC_BLOCK (BB_TO_BLOCK (i));
6102 /* If the basic block belongs to region, but doesn't belong to
6103 corresponding loop, then it should be a preheader. */
6104 if (sel_is_loop_preheader_p (bb))
6106 VEC_safe_push (basic_block, heap, preheader_blocks, bb);
6107 if (BB_END (bb) != bb_note (bb))
6108 all_empty_p = false;
6112 /* Remove these blocks only after iterating over the whole region. */
6113 for (i = VEC_length (basic_block, preheader_blocks) - 1;
6117 bb = VEC_index (basic_block, preheader_blocks, i);
6118 sel_remove_bb (bb, false);
6121 if (!considered_for_pipelining_p (loop_outer (current_loop_nest)))
6124 /* Immediately create new region from preheader. */
6125 make_region_from_loop_preheader (&preheader_blocks);
6128 /* If all preheader blocks are empty - dont create new empty region.
6129 Instead, remove them completely. */
6130 for (i = 0; VEC_iterate (basic_block, preheader_blocks, i, bb); i++)
6134 basic_block prev_bb = bb->prev_bb, next_bb = bb->next_bb;
6136 /* Redirect all incoming edges to next basic block. */
6137 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
6139 if (! (e->flags & EDGE_FALLTHRU))
6140 redirect_edge_and_branch (e, bb->next_bb);
6142 redirect_edge_succ (e, bb->next_bb);
6144 gcc_assert (BB_NOTE_LIST (bb) == NULL);
6145 delete_and_free_basic_block (bb);
6147 /* Check if after deleting preheader there is a nonconditional
6148 jump in PREV_BB that leads to the next basic block NEXT_BB.
6149 If it is so - delete this jump and clear data sets of its
6150 basic block if it becomes empty. */
6151 if (next_bb->prev_bb == prev_bb
6152 && prev_bb != ENTRY_BLOCK_PTR
6153 && jump_leads_only_to_bb_p (BB_END (prev_bb), next_bb))
6155 redirect_edge_and_branch (EDGE_SUCC (prev_bb, 0), next_bb);
6156 if (BB_END (prev_bb) == bb_note (prev_bb))
6157 free_data_sets (prev_bb);
6161 VEC_free (basic_block, heap, preheader_blocks);
6164 /* Store preheader within the father's loop structure. */
6165 SET_LOOP_PREHEADER_BLOCKS (loop_outer (current_loop_nest),