gcc/
[official-gcc.git] / gcc / sel-sched-ir.c
blobf9b7655af121f65fb0b083dc36ff62cae4228ba5
1 /* Instruction scheduling pass. Selective scheduler and pipeliner.
2 Copyright (C) 2006-2015 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
9 version.
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
14 for more details.
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/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "tm.h"
24 #include "diagnostic-core.h"
25 #include "rtl.h"
26 #include "tm_p.h"
27 #include "hard-reg-set.h"
28 #include "regs.h"
29 #include "function.h"
30 #include "predict.h"
31 #include "dominance.h"
32 #include "cfg.h"
33 #include "cfgrtl.h"
34 #include "cfganal.h"
35 #include "cfgbuild.h"
36 #include "basic-block.h"
37 #include "flags.h"
38 #include "insn-config.h"
39 #include "insn-attr.h"
40 #include "except.h"
41 #include "recog.h"
42 #include "params.h"
43 #include "target.h"
44 #include "sched-int.h"
45 #include "symtab.h"
46 #include "tree.h"
47 #include "langhooks.h"
48 #include "rtlhooks-def.h"
49 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
51 #ifdef INSN_SCHEDULING
52 #include "sel-sched-ir.h"
53 /* We don't have to use it except for sel_print_insn. */
54 #include "sel-sched-dump.h"
56 /* A vector holding bb info for whole scheduling pass. */
57 vec<sel_global_bb_info_def>
58 sel_global_bb_info = vNULL;
60 /* A vector holding bb info. */
61 vec<sel_region_bb_info_def>
62 sel_region_bb_info = vNULL;
64 /* A pool for allocating all lists. */
65 pool_allocator<_list_node> sched_lists_pool ("sel-sched-lists", 500);
67 /* This contains information about successors for compute_av_set. */
68 struct succs_info current_succs;
70 /* Data structure to describe interaction with the generic scheduler utils. */
71 static struct common_sched_info_def sel_common_sched_info;
73 /* The loop nest being pipelined. */
74 struct loop *current_loop_nest;
76 /* LOOP_NESTS is a vector containing the corresponding loop nest for
77 each region. */
78 static vec<loop_p> loop_nests = vNULL;
80 /* Saves blocks already in loop regions, indexed by bb->index. */
81 static sbitmap bbs_in_loop_rgns = NULL;
83 /* CFG hooks that are saved before changing create_basic_block hook. */
84 static struct cfg_hooks orig_cfg_hooks;
87 /* Array containing reverse topological index of function basic blocks,
88 indexed by BB->INDEX. */
89 static int *rev_top_order_index = NULL;
91 /* Length of the above array. */
92 static int rev_top_order_index_len = -1;
94 /* A regset pool structure. */
95 static struct
97 /* The stack to which regsets are returned. */
98 regset *v;
100 /* Its pointer. */
101 int n;
103 /* Its size. */
104 int s;
106 /* In VV we save all generated regsets so that, when destructing the
107 pool, we can compare it with V and check that every regset was returned
108 back to pool. */
109 regset *vv;
111 /* The pointer of VV stack. */
112 int nn;
114 /* Its size. */
115 int ss;
117 /* The difference between allocated and returned regsets. */
118 int diff;
119 } regset_pool = { NULL, 0, 0, NULL, 0, 0, 0 };
121 /* This represents the nop pool. */
122 static struct
124 /* The vector which holds previously emitted nops. */
125 insn_t *v;
127 /* Its pointer. */
128 int n;
130 /* Its size. */
131 int s;
132 } nop_pool = { NULL, 0, 0 };
134 /* The pool for basic block notes. */
135 static vec<rtx_note *> bb_note_pool;
137 /* A NOP pattern used to emit placeholder insns. */
138 rtx nop_pattern = NULL_RTX;
139 /* A special instruction that resides in EXIT_BLOCK.
140 EXIT_INSN is successor of the insns that lead to EXIT_BLOCK. */
141 rtx_insn *exit_insn = NULL;
143 /* TRUE if while scheduling current region, which is loop, its preheader
144 was removed. */
145 bool preheader_removed = false;
148 /* Forward static declarations. */
149 static void fence_clear (fence_t);
151 static void deps_init_id (idata_t, insn_t, bool);
152 static void init_id_from_df (idata_t, insn_t, bool);
153 static expr_t set_insn_init (expr_t, vinsn_t, int);
155 static void cfg_preds (basic_block, insn_t **, int *);
156 static void prepare_insn_expr (insn_t, int);
157 static void free_history_vect (vec<expr_history_def> &);
159 static void move_bb_info (basic_block, basic_block);
160 static void remove_empty_bb (basic_block, bool);
161 static void sel_merge_blocks (basic_block, basic_block);
162 static void sel_remove_loop_preheader (void);
163 static bool bb_has_removable_jump_to_p (basic_block, basic_block);
165 static bool insn_is_the_only_one_in_bb_p (insn_t);
166 static void create_initial_data_sets (basic_block);
168 static void free_av_set (basic_block);
169 static void invalidate_av_set (basic_block);
170 static void extend_insn_data (void);
171 static void sel_init_new_insn (insn_t, int, int = -1);
172 static void finish_insns (void);
174 /* Various list functions. */
176 /* Copy an instruction list L. */
177 ilist_t
178 ilist_copy (ilist_t l)
180 ilist_t head = NULL, *tailp = &head;
182 while (l)
184 ilist_add (tailp, ILIST_INSN (l));
185 tailp = &ILIST_NEXT (*tailp);
186 l = ILIST_NEXT (l);
189 return head;
192 /* Invert an instruction list L. */
193 ilist_t
194 ilist_invert (ilist_t l)
196 ilist_t res = NULL;
198 while (l)
200 ilist_add (&res, ILIST_INSN (l));
201 l = ILIST_NEXT (l);
204 return res;
207 /* Add a new boundary to the LP list with parameters TO, PTR, and DC. */
208 void
209 blist_add (blist_t *lp, insn_t to, ilist_t ptr, deps_t dc)
211 bnd_t bnd;
213 _list_add (lp);
214 bnd = BLIST_BND (*lp);
216 BND_TO (bnd) = to;
217 BND_PTR (bnd) = ptr;
218 BND_AV (bnd) = NULL;
219 BND_AV1 (bnd) = NULL;
220 BND_DC (bnd) = dc;
223 /* Remove the list note pointed to by LP. */
224 void
225 blist_remove (blist_t *lp)
227 bnd_t b = BLIST_BND (*lp);
229 av_set_clear (&BND_AV (b));
230 av_set_clear (&BND_AV1 (b));
231 ilist_clear (&BND_PTR (b));
233 _list_remove (lp);
236 /* Init a fence tail L. */
237 void
238 flist_tail_init (flist_tail_t l)
240 FLIST_TAIL_HEAD (l) = NULL;
241 FLIST_TAIL_TAILP (l) = &FLIST_TAIL_HEAD (l);
244 /* Try to find fence corresponding to INSN in L. */
245 fence_t
246 flist_lookup (flist_t l, insn_t insn)
248 while (l)
250 if (FENCE_INSN (FLIST_FENCE (l)) == insn)
251 return FLIST_FENCE (l);
253 l = FLIST_NEXT (l);
256 return NULL;
259 /* Init the fields of F before running fill_insns. */
260 static void
261 init_fence_for_scheduling (fence_t f)
263 FENCE_BNDS (f) = NULL;
264 FENCE_PROCESSED_P (f) = false;
265 FENCE_SCHEDULED_P (f) = false;
268 /* Add new fence consisting of INSN and STATE to the list pointed to by LP. */
269 static void
270 flist_add (flist_t *lp, insn_t insn, state_t state, deps_t dc, void *tc,
271 insn_t last_scheduled_insn, vec<rtx_insn *, va_gc> *executing_insns,
272 int *ready_ticks, int ready_ticks_size, insn_t sched_next,
273 int cycle, int cycle_issued_insns, int issue_more,
274 bool starts_cycle_p, bool after_stall_p)
276 fence_t f;
278 _list_add (lp);
279 f = FLIST_FENCE (*lp);
281 FENCE_INSN (f) = insn;
283 gcc_assert (state != NULL);
284 FENCE_STATE (f) = state;
286 FENCE_CYCLE (f) = cycle;
287 FENCE_ISSUED_INSNS (f) = cycle_issued_insns;
288 FENCE_STARTS_CYCLE_P (f) = starts_cycle_p;
289 FENCE_AFTER_STALL_P (f) = after_stall_p;
291 gcc_assert (dc != NULL);
292 FENCE_DC (f) = dc;
294 gcc_assert (tc != NULL || targetm.sched.alloc_sched_context == NULL);
295 FENCE_TC (f) = tc;
297 FENCE_LAST_SCHEDULED_INSN (f) = last_scheduled_insn;
298 FENCE_ISSUE_MORE (f) = issue_more;
299 FENCE_EXECUTING_INSNS (f) = executing_insns;
300 FENCE_READY_TICKS (f) = ready_ticks;
301 FENCE_READY_TICKS_SIZE (f) = ready_ticks_size;
302 FENCE_SCHED_NEXT (f) = sched_next;
304 init_fence_for_scheduling (f);
307 /* Remove the head node of the list pointed to by LP. */
308 static void
309 flist_remove (flist_t *lp)
311 if (FENCE_INSN (FLIST_FENCE (*lp)))
312 fence_clear (FLIST_FENCE (*lp));
313 _list_remove (lp);
316 /* Clear the fence list pointed to by LP. */
317 void
318 flist_clear (flist_t *lp)
320 while (*lp)
321 flist_remove (lp);
324 /* Add ORIGINAL_INSN the def list DL honoring CROSSES_CALL. */
325 void
326 def_list_add (def_list_t *dl, insn_t original_insn, bool crosses_call)
328 def_t d;
330 _list_add (dl);
331 d = DEF_LIST_DEF (*dl);
333 d->orig_insn = original_insn;
334 d->crosses_call = crosses_call;
338 /* Functions to work with target contexts. */
340 /* Bulk target context. It is convenient for debugging purposes to ensure
341 that there are no uninitialized (null) target contexts. */
342 static tc_t bulk_tc = (tc_t) 1;
344 /* Target hooks wrappers. In the future we can provide some default
345 implementations for them. */
347 /* Allocate a store for the target context. */
348 static tc_t
349 alloc_target_context (void)
351 return (targetm.sched.alloc_sched_context
352 ? targetm.sched.alloc_sched_context () : bulk_tc);
355 /* Init target context TC.
356 If CLEAN_P is true, then make TC as it is beginning of the scheduler.
357 Overwise, copy current backend context to TC. */
358 static void
359 init_target_context (tc_t tc, bool clean_p)
361 if (targetm.sched.init_sched_context)
362 targetm.sched.init_sched_context (tc, clean_p);
365 /* Allocate and initialize a target context. Meaning of CLEAN_P is the same as
366 int init_target_context (). */
367 tc_t
368 create_target_context (bool clean_p)
370 tc_t tc = alloc_target_context ();
372 init_target_context (tc, clean_p);
373 return tc;
376 /* Copy TC to the current backend context. */
377 void
378 set_target_context (tc_t tc)
380 if (targetm.sched.set_sched_context)
381 targetm.sched.set_sched_context (tc);
384 /* TC is about to be destroyed. Free any internal data. */
385 static void
386 clear_target_context (tc_t tc)
388 if (targetm.sched.clear_sched_context)
389 targetm.sched.clear_sched_context (tc);
392 /* Clear and free it. */
393 static void
394 delete_target_context (tc_t tc)
396 clear_target_context (tc);
398 if (targetm.sched.free_sched_context)
399 targetm.sched.free_sched_context (tc);
402 /* Make a copy of FROM in TO.
403 NB: May be this should be a hook. */
404 static void
405 copy_target_context (tc_t to, tc_t from)
407 tc_t tmp = create_target_context (false);
409 set_target_context (from);
410 init_target_context (to, false);
412 set_target_context (tmp);
413 delete_target_context (tmp);
416 /* Create a copy of TC. */
417 static tc_t
418 create_copy_of_target_context (tc_t tc)
420 tc_t copy = alloc_target_context ();
422 copy_target_context (copy, tc);
424 return copy;
427 /* Clear TC and initialize it according to CLEAN_P. The meaning of CLEAN_P
428 is the same as in init_target_context (). */
429 void
430 reset_target_context (tc_t tc, bool clean_p)
432 clear_target_context (tc);
433 init_target_context (tc, clean_p);
436 /* Functions to work with dependence contexts.
437 Dc (aka deps context, aka deps_t, aka struct deps_desc *) is short for dependence
438 context. It accumulates information about processed insns to decide if
439 current insn is dependent on the processed ones. */
441 /* Make a copy of FROM in TO. */
442 static void
443 copy_deps_context (deps_t to, deps_t from)
445 init_deps (to, false);
446 deps_join (to, from);
449 /* Allocate store for dep context. */
450 static deps_t
451 alloc_deps_context (void)
453 return XNEW (struct deps_desc);
456 /* Allocate and initialize dep context. */
457 static deps_t
458 create_deps_context (void)
460 deps_t dc = alloc_deps_context ();
462 init_deps (dc, false);
463 return dc;
466 /* Create a copy of FROM. */
467 static deps_t
468 create_copy_of_deps_context (deps_t from)
470 deps_t to = alloc_deps_context ();
472 copy_deps_context (to, from);
473 return to;
476 /* Clean up internal data of DC. */
477 static void
478 clear_deps_context (deps_t dc)
480 free_deps (dc);
483 /* Clear and free DC. */
484 static void
485 delete_deps_context (deps_t dc)
487 clear_deps_context (dc);
488 free (dc);
491 /* Clear and init DC. */
492 static void
493 reset_deps_context (deps_t dc)
495 clear_deps_context (dc);
496 init_deps (dc, false);
499 /* This structure describes the dependence analysis hooks for advancing
500 dependence context. */
501 static struct sched_deps_info_def advance_deps_context_sched_deps_info =
503 NULL,
505 NULL, /* start_insn */
506 NULL, /* finish_insn */
507 NULL, /* start_lhs */
508 NULL, /* finish_lhs */
509 NULL, /* start_rhs */
510 NULL, /* finish_rhs */
511 haifa_note_reg_set,
512 haifa_note_reg_clobber,
513 haifa_note_reg_use,
514 NULL, /* note_mem_dep */
515 NULL, /* note_dep */
517 0, 0, 0
520 /* Process INSN and add its impact on DC. */
521 void
522 advance_deps_context (deps_t dc, insn_t insn)
524 sched_deps_info = &advance_deps_context_sched_deps_info;
525 deps_analyze_insn (dc, insn);
529 /* Functions to work with DFA states. */
531 /* Allocate store for a DFA state. */
532 static state_t
533 state_alloc (void)
535 return xmalloc (dfa_state_size);
538 /* Allocate and initialize DFA state. */
539 static state_t
540 state_create (void)
542 state_t state = state_alloc ();
544 state_reset (state);
545 advance_state (state);
546 return state;
549 /* Free DFA state. */
550 static void
551 state_free (state_t state)
553 free (state);
556 /* Make a copy of FROM in TO. */
557 static void
558 state_copy (state_t to, state_t from)
560 memcpy (to, from, dfa_state_size);
563 /* Create a copy of FROM. */
564 static state_t
565 state_create_copy (state_t from)
567 state_t to = state_alloc ();
569 state_copy (to, from);
570 return to;
574 /* Functions to work with fences. */
576 /* Clear the fence. */
577 static void
578 fence_clear (fence_t f)
580 state_t s = FENCE_STATE (f);
581 deps_t dc = FENCE_DC (f);
582 void *tc = FENCE_TC (f);
584 ilist_clear (&FENCE_BNDS (f));
586 gcc_assert ((s != NULL && dc != NULL && tc != NULL)
587 || (s == NULL && dc == NULL && tc == NULL));
589 free (s);
591 if (dc != NULL)
592 delete_deps_context (dc);
594 if (tc != NULL)
595 delete_target_context (tc);
596 vec_free (FENCE_EXECUTING_INSNS (f));
597 free (FENCE_READY_TICKS (f));
598 FENCE_READY_TICKS (f) = NULL;
601 /* Init a list of fences with successors of OLD_FENCE. */
602 void
603 init_fences (insn_t old_fence)
605 insn_t succ;
606 succ_iterator si;
607 bool first = true;
608 int ready_ticks_size = get_max_uid () + 1;
610 FOR_EACH_SUCC_1 (succ, si, old_fence,
611 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
614 if (first)
615 first = false;
616 else
617 gcc_assert (flag_sel_sched_pipelining_outer_loops);
619 flist_add (&fences, succ,
620 state_create (),
621 create_deps_context () /* dc */,
622 create_target_context (true) /* tc */,
623 NULL /* last_scheduled_insn */,
624 NULL, /* executing_insns */
625 XCNEWVEC (int, ready_ticks_size), /* ready_ticks */
626 ready_ticks_size,
627 NULL /* sched_next */,
628 1 /* cycle */, 0 /* cycle_issued_insns */,
629 issue_rate, /* issue_more */
630 1 /* starts_cycle_p */, 0 /* after_stall_p */);
634 /* Merges two fences (filling fields of fence F with resulting values) by
635 following rules: 1) state, target context and last scheduled insn are
636 propagated from fallthrough edge if it is available;
637 2) deps context and cycle is propagated from more probable edge;
638 3) all other fields are set to corresponding constant values.
640 INSN, STATE, DC, TC, LAST_SCHEDULED_INSN, EXECUTING_INSNS,
641 READY_TICKS, READY_TICKS_SIZE, SCHED_NEXT, CYCLE, ISSUE_MORE
642 and AFTER_STALL_P are the corresponding fields of the second fence. */
643 static void
644 merge_fences (fence_t f, insn_t insn,
645 state_t state, deps_t dc, void *tc,
646 rtx_insn *last_scheduled_insn,
647 vec<rtx_insn *, va_gc> *executing_insns,
648 int *ready_ticks, int ready_ticks_size,
649 rtx sched_next, int cycle, int issue_more, bool after_stall_p)
651 insn_t last_scheduled_insn_old = FENCE_LAST_SCHEDULED_INSN (f);
653 gcc_assert (sel_bb_head_p (FENCE_INSN (f))
654 && !sched_next && !FENCE_SCHED_NEXT (f));
656 /* Check if we can decide which path fences came.
657 If we can't (or don't want to) - reset all. */
658 if (last_scheduled_insn == NULL
659 || last_scheduled_insn_old == NULL
660 /* This is a case when INSN is reachable on several paths from
661 one insn (this can happen when pipelining of outer loops is on and
662 there are two edges: one going around of inner loop and the other -
663 right through it; in such case just reset everything). */
664 || last_scheduled_insn == last_scheduled_insn_old)
666 state_reset (FENCE_STATE (f));
667 state_free (state);
669 reset_deps_context (FENCE_DC (f));
670 delete_deps_context (dc);
672 reset_target_context (FENCE_TC (f), true);
673 delete_target_context (tc);
675 if (cycle > FENCE_CYCLE (f))
676 FENCE_CYCLE (f) = cycle;
678 FENCE_LAST_SCHEDULED_INSN (f) = NULL;
679 FENCE_ISSUE_MORE (f) = issue_rate;
680 vec_free (executing_insns);
681 free (ready_ticks);
682 if (FENCE_EXECUTING_INSNS (f))
683 FENCE_EXECUTING_INSNS (f)->block_remove (0,
684 FENCE_EXECUTING_INSNS (f)->length ());
685 if (FENCE_READY_TICKS (f))
686 memset (FENCE_READY_TICKS (f), 0, FENCE_READY_TICKS_SIZE (f));
688 else
690 edge edge_old = NULL, edge_new = NULL;
691 edge candidate;
692 succ_iterator si;
693 insn_t succ;
695 /* Find fallthrough edge. */
696 gcc_assert (BLOCK_FOR_INSN (insn)->prev_bb);
697 candidate = find_fallthru_edge_from (BLOCK_FOR_INSN (insn)->prev_bb);
699 if (!candidate
700 || (candidate->src != BLOCK_FOR_INSN (last_scheduled_insn)
701 && candidate->src != BLOCK_FOR_INSN (last_scheduled_insn_old)))
703 /* No fallthrough edge leading to basic block of INSN. */
704 state_reset (FENCE_STATE (f));
705 state_free (state);
707 reset_target_context (FENCE_TC (f), true);
708 delete_target_context (tc);
710 FENCE_LAST_SCHEDULED_INSN (f) = NULL;
711 FENCE_ISSUE_MORE (f) = issue_rate;
713 else
714 if (candidate->src == BLOCK_FOR_INSN (last_scheduled_insn))
716 /* Would be weird if same insn is successor of several fallthrough
717 edges. */
718 gcc_assert (BLOCK_FOR_INSN (insn)->prev_bb
719 != BLOCK_FOR_INSN (last_scheduled_insn_old));
721 state_free (FENCE_STATE (f));
722 FENCE_STATE (f) = state;
724 delete_target_context (FENCE_TC (f));
725 FENCE_TC (f) = tc;
727 FENCE_LAST_SCHEDULED_INSN (f) = last_scheduled_insn;
728 FENCE_ISSUE_MORE (f) = issue_more;
730 else
732 /* Leave STATE, TC and LAST_SCHEDULED_INSN fields untouched. */
733 state_free (state);
734 delete_target_context (tc);
736 gcc_assert (BLOCK_FOR_INSN (insn)->prev_bb
737 != BLOCK_FOR_INSN (last_scheduled_insn));
740 /* Find edge of first predecessor (last_scheduled_insn_old->insn). */
741 FOR_EACH_SUCC_1 (succ, si, last_scheduled_insn_old,
742 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
744 if (succ == insn)
746 /* No same successor allowed from several edges. */
747 gcc_assert (!edge_old);
748 edge_old = si.e1;
751 /* Find edge of second predecessor (last_scheduled_insn->insn). */
752 FOR_EACH_SUCC_1 (succ, si, last_scheduled_insn,
753 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
755 if (succ == insn)
757 /* No same successor allowed from several edges. */
758 gcc_assert (!edge_new);
759 edge_new = si.e1;
763 /* Check if we can choose most probable predecessor. */
764 if (edge_old == NULL || edge_new == NULL)
766 reset_deps_context (FENCE_DC (f));
767 delete_deps_context (dc);
768 vec_free (executing_insns);
769 free (ready_ticks);
771 FENCE_CYCLE (f) = MAX (FENCE_CYCLE (f), cycle);
772 if (FENCE_EXECUTING_INSNS (f))
773 FENCE_EXECUTING_INSNS (f)->block_remove (0,
774 FENCE_EXECUTING_INSNS (f)->length ());
775 if (FENCE_READY_TICKS (f))
776 memset (FENCE_READY_TICKS (f), 0, FENCE_READY_TICKS_SIZE (f));
778 else
779 if (edge_new->probability > edge_old->probability)
781 delete_deps_context (FENCE_DC (f));
782 FENCE_DC (f) = dc;
783 vec_free (FENCE_EXECUTING_INSNS (f));
784 FENCE_EXECUTING_INSNS (f) = executing_insns;
785 free (FENCE_READY_TICKS (f));
786 FENCE_READY_TICKS (f) = ready_ticks;
787 FENCE_READY_TICKS_SIZE (f) = ready_ticks_size;
788 FENCE_CYCLE (f) = cycle;
790 else
792 /* Leave DC and CYCLE untouched. */
793 delete_deps_context (dc);
794 vec_free (executing_insns);
795 free (ready_ticks);
799 /* Fill remaining invariant fields. */
800 if (after_stall_p)
801 FENCE_AFTER_STALL_P (f) = 1;
803 FENCE_ISSUED_INSNS (f) = 0;
804 FENCE_STARTS_CYCLE_P (f) = 1;
805 FENCE_SCHED_NEXT (f) = NULL;
808 /* Add a new fence to NEW_FENCES list, initializing it from all
809 other parameters. */
810 static void
811 add_to_fences (flist_tail_t new_fences, insn_t insn,
812 state_t state, deps_t dc, void *tc,
813 rtx_insn *last_scheduled_insn,
814 vec<rtx_insn *, va_gc> *executing_insns, int *ready_ticks,
815 int ready_ticks_size, rtx_insn *sched_next, int cycle,
816 int cycle_issued_insns, int issue_rate,
817 bool starts_cycle_p, bool after_stall_p)
819 fence_t f = flist_lookup (FLIST_TAIL_HEAD (new_fences), insn);
821 if (! f)
823 flist_add (FLIST_TAIL_TAILP (new_fences), insn, state, dc, tc,
824 last_scheduled_insn, executing_insns, ready_ticks,
825 ready_ticks_size, sched_next, cycle, cycle_issued_insns,
826 issue_rate, starts_cycle_p, after_stall_p);
828 FLIST_TAIL_TAILP (new_fences)
829 = &FLIST_NEXT (*FLIST_TAIL_TAILP (new_fences));
831 else
833 merge_fences (f, insn, state, dc, tc, last_scheduled_insn,
834 executing_insns, ready_ticks, ready_ticks_size,
835 sched_next, cycle, issue_rate, after_stall_p);
839 /* Move the first fence in the OLD_FENCES list to NEW_FENCES. */
840 void
841 move_fence_to_fences (flist_t old_fences, flist_tail_t new_fences)
843 fence_t f, old;
844 flist_t *tailp = FLIST_TAIL_TAILP (new_fences);
846 old = FLIST_FENCE (old_fences);
847 f = flist_lookup (FLIST_TAIL_HEAD (new_fences),
848 FENCE_INSN (FLIST_FENCE (old_fences)));
849 if (f)
851 merge_fences (f, old->insn, old->state, old->dc, old->tc,
852 old->last_scheduled_insn, old->executing_insns,
853 old->ready_ticks, old->ready_ticks_size,
854 old->sched_next, old->cycle, old->issue_more,
855 old->after_stall_p);
857 else
859 _list_add (tailp);
860 FLIST_TAIL_TAILP (new_fences) = &FLIST_NEXT (*tailp);
861 *FLIST_FENCE (*tailp) = *old;
862 init_fence_for_scheduling (FLIST_FENCE (*tailp));
864 FENCE_INSN (old) = NULL;
867 /* Add a new fence to NEW_FENCES list and initialize most of its data
868 as a clean one. */
869 void
870 add_clean_fence_to_fences (flist_tail_t new_fences, insn_t succ, fence_t fence)
872 int ready_ticks_size = get_max_uid () + 1;
874 add_to_fences (new_fences,
875 succ, state_create (), create_deps_context (),
876 create_target_context (true),
877 NULL, NULL,
878 XCNEWVEC (int, ready_ticks_size), ready_ticks_size,
879 NULL, FENCE_CYCLE (fence) + 1,
880 0, issue_rate, 1, FENCE_AFTER_STALL_P (fence));
883 /* Add a new fence to NEW_FENCES list and initialize all of its data
884 from FENCE and SUCC. */
885 void
886 add_dirty_fence_to_fences (flist_tail_t new_fences, insn_t succ, fence_t fence)
888 int * new_ready_ticks
889 = XNEWVEC (int, FENCE_READY_TICKS_SIZE (fence));
891 memcpy (new_ready_ticks, FENCE_READY_TICKS (fence),
892 FENCE_READY_TICKS_SIZE (fence) * sizeof (int));
893 add_to_fences (new_fences,
894 succ, state_create_copy (FENCE_STATE (fence)),
895 create_copy_of_deps_context (FENCE_DC (fence)),
896 create_copy_of_target_context (FENCE_TC (fence)),
897 FENCE_LAST_SCHEDULED_INSN (fence),
898 vec_safe_copy (FENCE_EXECUTING_INSNS (fence)),
899 new_ready_ticks,
900 FENCE_READY_TICKS_SIZE (fence),
901 FENCE_SCHED_NEXT (fence),
902 FENCE_CYCLE (fence),
903 FENCE_ISSUED_INSNS (fence),
904 FENCE_ISSUE_MORE (fence),
905 FENCE_STARTS_CYCLE_P (fence),
906 FENCE_AFTER_STALL_P (fence));
910 /* Functions to work with regset and nop pools. */
912 /* Returns the new regset from pool. It might have some of the bits set
913 from the previous usage. */
914 regset
915 get_regset_from_pool (void)
917 regset rs;
919 if (regset_pool.n != 0)
920 rs = regset_pool.v[--regset_pool.n];
921 else
922 /* We need to create the regset. */
924 rs = ALLOC_REG_SET (&reg_obstack);
926 if (regset_pool.nn == regset_pool.ss)
927 regset_pool.vv = XRESIZEVEC (regset, regset_pool.vv,
928 (regset_pool.ss = 2 * regset_pool.ss + 1));
929 regset_pool.vv[regset_pool.nn++] = rs;
932 regset_pool.diff++;
934 return rs;
937 /* Same as above, but returns the empty regset. */
938 regset
939 get_clear_regset_from_pool (void)
941 regset rs = get_regset_from_pool ();
943 CLEAR_REG_SET (rs);
944 return rs;
947 /* Return regset RS to the pool for future use. */
948 void
949 return_regset_to_pool (regset rs)
951 gcc_assert (rs);
952 regset_pool.diff--;
954 if (regset_pool.n == regset_pool.s)
955 regset_pool.v = XRESIZEVEC (regset, regset_pool.v,
956 (regset_pool.s = 2 * regset_pool.s + 1));
957 regset_pool.v[regset_pool.n++] = rs;
960 #ifdef ENABLE_CHECKING
961 /* This is used as a qsort callback for sorting regset pool stacks.
962 X and XX are addresses of two regsets. They are never equal. */
963 static int
964 cmp_v_in_regset_pool (const void *x, const void *xx)
966 uintptr_t r1 = (uintptr_t) *((const regset *) x);
967 uintptr_t r2 = (uintptr_t) *((const regset *) xx);
968 if (r1 > r2)
969 return 1;
970 else if (r1 < r2)
971 return -1;
972 gcc_unreachable ();
974 #endif
976 /* Free the regset pool possibly checking for memory leaks. */
977 void
978 free_regset_pool (void)
980 #ifdef ENABLE_CHECKING
982 regset *v = regset_pool.v;
983 int i = 0;
984 int n = regset_pool.n;
986 regset *vv = regset_pool.vv;
987 int ii = 0;
988 int nn = regset_pool.nn;
990 int diff = 0;
992 gcc_assert (n <= nn);
994 /* Sort both vectors so it will be possible to compare them. */
995 qsort (v, n, sizeof (*v), cmp_v_in_regset_pool);
996 qsort (vv, nn, sizeof (*vv), cmp_v_in_regset_pool);
998 while (ii < nn)
1000 if (v[i] == vv[ii])
1001 i++;
1002 else
1003 /* VV[II] was lost. */
1004 diff++;
1006 ii++;
1009 gcc_assert (diff == regset_pool.diff);
1011 #endif
1013 /* If not true - we have a memory leak. */
1014 gcc_assert (regset_pool.diff == 0);
1016 while (regset_pool.n)
1018 --regset_pool.n;
1019 FREE_REG_SET (regset_pool.v[regset_pool.n]);
1022 free (regset_pool.v);
1023 regset_pool.v = NULL;
1024 regset_pool.s = 0;
1026 free (regset_pool.vv);
1027 regset_pool.vv = NULL;
1028 regset_pool.nn = 0;
1029 regset_pool.ss = 0;
1031 regset_pool.diff = 0;
1035 /* Functions to work with nop pools. NOP insns are used as temporary
1036 placeholders of the insns being scheduled to allow correct update of
1037 the data sets. When update is finished, NOPs are deleted. */
1039 /* A vinsn that is used to represent a nop. This vinsn is shared among all
1040 nops sel-sched generates. */
1041 static vinsn_t nop_vinsn = NULL;
1043 /* Emit a nop before INSN, taking it from pool. */
1044 insn_t
1045 get_nop_from_pool (insn_t insn)
1047 rtx nop_pat;
1048 insn_t nop;
1049 bool old_p = nop_pool.n != 0;
1050 int flags;
1052 if (old_p)
1053 nop_pat = nop_pool.v[--nop_pool.n];
1054 else
1055 nop_pat = nop_pattern;
1057 nop = emit_insn_before (nop_pat, insn);
1059 if (old_p)
1060 flags = INSN_INIT_TODO_SSID;
1061 else
1062 flags = INSN_INIT_TODO_LUID | INSN_INIT_TODO_SSID;
1064 set_insn_init (INSN_EXPR (insn), nop_vinsn, INSN_SEQNO (insn));
1065 sel_init_new_insn (nop, flags);
1067 return nop;
1070 /* Remove NOP from the instruction stream and return it to the pool. */
1071 void
1072 return_nop_to_pool (insn_t nop, bool full_tidying)
1074 gcc_assert (INSN_IN_STREAM_P (nop));
1075 sel_remove_insn (nop, false, full_tidying);
1077 /* We'll recycle this nop. */
1078 nop->set_undeleted ();
1080 if (nop_pool.n == nop_pool.s)
1081 nop_pool.v = XRESIZEVEC (rtx_insn *, nop_pool.v,
1082 (nop_pool.s = 2 * nop_pool.s + 1));
1083 nop_pool.v[nop_pool.n++] = nop;
1086 /* Free the nop pool. */
1087 void
1088 free_nop_pool (void)
1090 nop_pool.n = 0;
1091 nop_pool.s = 0;
1092 free (nop_pool.v);
1093 nop_pool.v = NULL;
1097 /* Skip unspec to support ia64 speculation. Called from rtx_equal_p_cb.
1098 The callback is given two rtxes XX and YY and writes the new rtxes
1099 to NX and NY in case some needs to be skipped. */
1100 static int
1101 skip_unspecs_callback (const_rtx *xx, const_rtx *yy, rtx *nx, rtx* ny)
1103 const_rtx x = *xx;
1104 const_rtx y = *yy;
1106 if (GET_CODE (x) == UNSPEC
1107 && (targetm.sched.skip_rtx_p == NULL
1108 || targetm.sched.skip_rtx_p (x)))
1110 *nx = XVECEXP (x, 0, 0);
1111 *ny = CONST_CAST_RTX (y);
1112 return 1;
1115 if (GET_CODE (y) == UNSPEC
1116 && (targetm.sched.skip_rtx_p == NULL
1117 || targetm.sched.skip_rtx_p (y)))
1119 *nx = CONST_CAST_RTX (x);
1120 *ny = XVECEXP (y, 0, 0);
1121 return 1;
1124 return 0;
1127 /* Callback, called from hash_rtx_cb. Helps to hash UNSPEC rtx X in a correct way
1128 to support ia64 speculation. When changes are needed, new rtx X and new mode
1129 NMODE are written, and the callback returns true. */
1130 static int
1131 hash_with_unspec_callback (const_rtx x, machine_mode mode ATTRIBUTE_UNUSED,
1132 rtx *nx, machine_mode* nmode)
1134 if (GET_CODE (x) == UNSPEC
1135 && targetm.sched.skip_rtx_p
1136 && targetm.sched.skip_rtx_p (x))
1138 *nx = XVECEXP (x, 0 ,0);
1139 *nmode = VOIDmode;
1140 return 1;
1143 return 0;
1146 /* Returns LHS and RHS are ok to be scheduled separately. */
1147 static bool
1148 lhs_and_rhs_separable_p (rtx lhs, rtx rhs)
1150 if (lhs == NULL || rhs == NULL)
1151 return false;
1153 /* Do not schedule constants as rhs: no point to use reg, if const
1154 can be used. Moreover, scheduling const as rhs may lead to mode
1155 mismatch cause consts don't have modes but they could be merged
1156 from branches where the same const used in different modes. */
1157 if (CONSTANT_P (rhs))
1158 return false;
1160 /* ??? Do not rename predicate registers to avoid ICEs in bundling. */
1161 if (COMPARISON_P (rhs))
1162 return false;
1164 /* Do not allow single REG to be an rhs. */
1165 if (REG_P (rhs))
1166 return false;
1168 /* See comment at find_used_regs_1 (*1) for explanation of this
1169 restriction. */
1170 /* FIXME: remove this later. */
1171 if (MEM_P (lhs))
1172 return false;
1174 /* This will filter all tricky things like ZERO_EXTRACT etc.
1175 For now we don't handle it. */
1176 if (!REG_P (lhs) && !MEM_P (lhs))
1177 return false;
1179 return true;
1182 /* Initialize vinsn VI for INSN. Only for use from vinsn_create (). When
1183 FORCE_UNIQUE_P is true, the resulting vinsn will not be clonable. This is
1184 used e.g. for insns from recovery blocks. */
1185 static void
1186 vinsn_init (vinsn_t vi, insn_t insn, bool force_unique_p)
1188 hash_rtx_callback_function hrcf;
1189 int insn_class;
1191 VINSN_INSN_RTX (vi) = insn;
1192 VINSN_COUNT (vi) = 0;
1193 vi->cost = -1;
1195 if (INSN_NOP_P (insn))
1196 return;
1198 if (DF_INSN_UID_SAFE_GET (INSN_UID (insn)) != NULL)
1199 init_id_from_df (VINSN_ID (vi), insn, force_unique_p);
1200 else
1201 deps_init_id (VINSN_ID (vi), insn, force_unique_p);
1203 /* Hash vinsn depending on whether it is separable or not. */
1204 hrcf = targetm.sched.skip_rtx_p ? hash_with_unspec_callback : NULL;
1205 if (VINSN_SEPARABLE_P (vi))
1207 rtx rhs = VINSN_RHS (vi);
1209 VINSN_HASH (vi) = hash_rtx_cb (rhs, GET_MODE (rhs),
1210 NULL, NULL, false, hrcf);
1211 VINSN_HASH_RTX (vi) = hash_rtx_cb (VINSN_PATTERN (vi),
1212 VOIDmode, NULL, NULL,
1213 false, hrcf);
1215 else
1217 VINSN_HASH (vi) = hash_rtx_cb (VINSN_PATTERN (vi), VOIDmode,
1218 NULL, NULL, false, hrcf);
1219 VINSN_HASH_RTX (vi) = VINSN_HASH (vi);
1222 insn_class = haifa_classify_insn (insn);
1223 if (insn_class >= 2
1224 && (!targetm.sched.get_insn_spec_ds
1225 || ((targetm.sched.get_insn_spec_ds (insn) & BEGIN_CONTROL)
1226 == 0)))
1227 VINSN_MAY_TRAP_P (vi) = true;
1228 else
1229 VINSN_MAY_TRAP_P (vi) = false;
1232 /* Indicate that VI has become the part of an rtx object. */
1233 void
1234 vinsn_attach (vinsn_t vi)
1236 /* Assert that VI is not pending for deletion. */
1237 gcc_assert (VINSN_INSN_RTX (vi));
1239 VINSN_COUNT (vi)++;
1242 /* Create and init VI from the INSN. Use UNIQUE_P for determining the correct
1243 VINSN_TYPE (VI). */
1244 static vinsn_t
1245 vinsn_create (insn_t insn, bool force_unique_p)
1247 vinsn_t vi = XCNEW (struct vinsn_def);
1249 vinsn_init (vi, insn, force_unique_p);
1250 return vi;
1253 /* Return a copy of VI. When REATTACH_P is true, detach VI and attach
1254 the copy. */
1255 vinsn_t
1256 vinsn_copy (vinsn_t vi, bool reattach_p)
1258 rtx_insn *copy;
1259 bool unique = VINSN_UNIQUE_P (vi);
1260 vinsn_t new_vi;
1262 copy = create_copy_of_insn_rtx (VINSN_INSN_RTX (vi));
1263 new_vi = create_vinsn_from_insn_rtx (copy, unique);
1264 if (reattach_p)
1266 vinsn_detach (vi);
1267 vinsn_attach (new_vi);
1270 return new_vi;
1273 /* Delete the VI vinsn and free its data. */
1274 static void
1275 vinsn_delete (vinsn_t vi)
1277 gcc_assert (VINSN_COUNT (vi) == 0);
1279 if (!INSN_NOP_P (VINSN_INSN_RTX (vi)))
1281 return_regset_to_pool (VINSN_REG_SETS (vi));
1282 return_regset_to_pool (VINSN_REG_USES (vi));
1283 return_regset_to_pool (VINSN_REG_CLOBBERS (vi));
1286 free (vi);
1289 /* Indicate that VI is no longer a part of some rtx object.
1290 Remove VI if it is no longer needed. */
1291 void
1292 vinsn_detach (vinsn_t vi)
1294 gcc_assert (VINSN_COUNT (vi) > 0);
1296 if (--VINSN_COUNT (vi) == 0)
1297 vinsn_delete (vi);
1300 /* Returns TRUE if VI is a branch. */
1301 bool
1302 vinsn_cond_branch_p (vinsn_t vi)
1304 insn_t insn;
1306 if (!VINSN_UNIQUE_P (vi))
1307 return false;
1309 insn = VINSN_INSN_RTX (vi);
1310 if (BB_END (BLOCK_FOR_INSN (insn)) != insn)
1311 return false;
1313 return control_flow_insn_p (insn);
1316 /* Return latency of INSN. */
1317 static int
1318 sel_insn_rtx_cost (rtx_insn *insn)
1320 int cost;
1322 /* A USE insn, or something else we don't need to
1323 understand. We can't pass these directly to
1324 result_ready_cost or insn_default_latency because it will
1325 trigger a fatal error for unrecognizable insns. */
1326 if (recog_memoized (insn) < 0)
1327 cost = 0;
1328 else
1330 cost = insn_default_latency (insn);
1332 if (cost < 0)
1333 cost = 0;
1336 return cost;
1339 /* Return the cost of the VI.
1340 !!! FIXME: Unify with haifa-sched.c: insn_cost (). */
1342 sel_vinsn_cost (vinsn_t vi)
1344 int cost = vi->cost;
1346 if (cost < 0)
1348 cost = sel_insn_rtx_cost (VINSN_INSN_RTX (vi));
1349 vi->cost = cost;
1352 return cost;
1356 /* Functions for insn emitting. */
1358 /* Emit new insn after AFTER based on PATTERN and initialize its data from
1359 EXPR and SEQNO. */
1360 insn_t
1361 sel_gen_insn_from_rtx_after (rtx pattern, expr_t expr, int seqno, insn_t after)
1363 insn_t new_insn;
1365 gcc_assert (EXPR_TARGET_AVAILABLE (expr) == true);
1367 new_insn = emit_insn_after (pattern, after);
1368 set_insn_init (expr, NULL, seqno);
1369 sel_init_new_insn (new_insn, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SSID);
1371 return new_insn;
1374 /* Force newly generated vinsns to be unique. */
1375 static bool init_insn_force_unique_p = false;
1377 /* Emit new speculation recovery insn after AFTER based on PATTERN and
1378 initialize its data from EXPR and SEQNO. */
1379 insn_t
1380 sel_gen_recovery_insn_from_rtx_after (rtx pattern, expr_t expr, int seqno,
1381 insn_t after)
1383 insn_t insn;
1385 gcc_assert (!init_insn_force_unique_p);
1387 init_insn_force_unique_p = true;
1388 insn = sel_gen_insn_from_rtx_after (pattern, expr, seqno, after);
1389 CANT_MOVE (insn) = 1;
1390 init_insn_force_unique_p = false;
1392 return insn;
1395 /* Emit new insn after AFTER based on EXPR and SEQNO. If VINSN is not NULL,
1396 take it as a new vinsn instead of EXPR's vinsn.
1397 We simplify insns later, after scheduling region in
1398 simplify_changed_insns. */
1399 insn_t
1400 sel_gen_insn_from_expr_after (expr_t expr, vinsn_t vinsn, int seqno,
1401 insn_t after)
1403 expr_t emit_expr;
1404 insn_t insn;
1405 int flags;
1407 emit_expr = set_insn_init (expr, vinsn ? vinsn : EXPR_VINSN (expr),
1408 seqno);
1409 insn = EXPR_INSN_RTX (emit_expr);
1411 /* The insn may come from the transformation cache, which may hold already
1412 deleted insns, so mark it as not deleted. */
1413 insn->set_undeleted ();
1415 add_insn_after (insn, after, BLOCK_FOR_INSN (insn));
1417 flags = INSN_INIT_TODO_SSID;
1418 if (INSN_LUID (insn) == 0)
1419 flags |= INSN_INIT_TODO_LUID;
1420 sel_init_new_insn (insn, flags);
1422 return insn;
1425 /* Move insn from EXPR after AFTER. */
1426 insn_t
1427 sel_move_insn (expr_t expr, int seqno, insn_t after)
1429 insn_t insn = EXPR_INSN_RTX (expr);
1430 basic_block bb = BLOCK_FOR_INSN (after);
1431 insn_t next = NEXT_INSN (after);
1433 /* Assert that in move_op we disconnected this insn properly. */
1434 gcc_assert (EXPR_VINSN (INSN_EXPR (insn)) != NULL);
1435 SET_PREV_INSN (insn) = after;
1436 SET_NEXT_INSN (insn) = next;
1438 SET_NEXT_INSN (after) = insn;
1439 SET_PREV_INSN (next) = insn;
1441 /* Update links from insn to bb and vice versa. */
1442 df_insn_change_bb (insn, bb);
1443 if (BB_END (bb) == after)
1444 BB_END (bb) = insn;
1446 prepare_insn_expr (insn, seqno);
1447 return insn;
1451 /* Functions to work with right-hand sides. */
1453 /* Search for a hash value determined by UID/NEW_VINSN in a sorted vector
1454 VECT and return true when found. Use NEW_VINSN for comparison only when
1455 COMPARE_VINSNS is true. Write to INDP the index on which
1456 the search has stopped, such that inserting the new element at INDP will
1457 retain VECT's sort order. */
1458 static bool
1459 find_in_history_vect_1 (vec<expr_history_def> vect,
1460 unsigned uid, vinsn_t new_vinsn,
1461 bool compare_vinsns, int *indp)
1463 expr_history_def *arr;
1464 int i, j, len = vect.length ();
1466 if (len == 0)
1468 *indp = 0;
1469 return false;
1472 arr = vect.address ();
1473 i = 0, j = len - 1;
1475 while (i <= j)
1477 unsigned auid = arr[i].uid;
1478 vinsn_t avinsn = arr[i].new_expr_vinsn;
1480 if (auid == uid
1481 /* When undoing transformation on a bookkeeping copy, the new vinsn
1482 may not be exactly equal to the one that is saved in the vector.
1483 This is because the insn whose copy we're checking was possibly
1484 substituted itself. */
1485 && (! compare_vinsns
1486 || vinsn_equal_p (avinsn, new_vinsn)))
1488 *indp = i;
1489 return true;
1491 else if (auid > uid)
1492 break;
1493 i++;
1496 *indp = i;
1497 return false;
1500 /* Search for a uid of INSN and NEW_VINSN in a sorted vector VECT. Return
1501 the position found or -1, if no such value is in vector.
1502 Search also for UIDs of insn's originators, if ORIGINATORS_P is true. */
1504 find_in_history_vect (vec<expr_history_def> vect, rtx insn,
1505 vinsn_t new_vinsn, bool originators_p)
1507 int ind;
1509 if (find_in_history_vect_1 (vect, INSN_UID (insn), new_vinsn,
1510 false, &ind))
1511 return ind;
1513 if (INSN_ORIGINATORS (insn) && originators_p)
1515 unsigned uid;
1516 bitmap_iterator bi;
1518 EXECUTE_IF_SET_IN_BITMAP (INSN_ORIGINATORS (insn), 0, uid, bi)
1519 if (find_in_history_vect_1 (vect, uid, new_vinsn, false, &ind))
1520 return ind;
1523 return -1;
1526 /* Insert new element in a sorted history vector pointed to by PVECT,
1527 if it is not there already. The element is searched using
1528 UID/NEW_EXPR_VINSN pair. TYPE, OLD_EXPR_VINSN and SPEC_DS save
1529 the history of a transformation. */
1530 void
1531 insert_in_history_vect (vec<expr_history_def> *pvect,
1532 unsigned uid, enum local_trans_type type,
1533 vinsn_t old_expr_vinsn, vinsn_t new_expr_vinsn,
1534 ds_t spec_ds)
1536 vec<expr_history_def> vect = *pvect;
1537 expr_history_def temp;
1538 bool res;
1539 int ind;
1541 res = find_in_history_vect_1 (vect, uid, new_expr_vinsn, true, &ind);
1543 if (res)
1545 expr_history_def *phist = &vect[ind];
1547 /* It is possible that speculation types of expressions that were
1548 propagated through different paths will be different here. In this
1549 case, merge the status to get the correct check later. */
1550 if (phist->spec_ds != spec_ds)
1551 phist->spec_ds = ds_max_merge (phist->spec_ds, spec_ds);
1552 return;
1555 temp.uid = uid;
1556 temp.old_expr_vinsn = old_expr_vinsn;
1557 temp.new_expr_vinsn = new_expr_vinsn;
1558 temp.spec_ds = spec_ds;
1559 temp.type = type;
1561 vinsn_attach (old_expr_vinsn);
1562 vinsn_attach (new_expr_vinsn);
1563 vect.safe_insert (ind, temp);
1564 *pvect = vect;
1567 /* Free history vector PVECT. */
1568 static void
1569 free_history_vect (vec<expr_history_def> &pvect)
1571 unsigned i;
1572 expr_history_def *phist;
1574 if (! pvect.exists ())
1575 return;
1577 for (i = 0; pvect.iterate (i, &phist); i++)
1579 vinsn_detach (phist->old_expr_vinsn);
1580 vinsn_detach (phist->new_expr_vinsn);
1583 pvect.release ();
1586 /* Merge vector FROM to PVECT. */
1587 static void
1588 merge_history_vect (vec<expr_history_def> *pvect,
1589 vec<expr_history_def> from)
1591 expr_history_def *phist;
1592 int i;
1594 /* We keep this vector sorted. */
1595 for (i = 0; from.iterate (i, &phist); i++)
1596 insert_in_history_vect (pvect, phist->uid, phist->type,
1597 phist->old_expr_vinsn, phist->new_expr_vinsn,
1598 phist->spec_ds);
1601 /* Compare two vinsns as rhses if possible and as vinsns otherwise. */
1602 bool
1603 vinsn_equal_p (vinsn_t x, vinsn_t y)
1605 rtx_equal_p_callback_function repcf;
1607 if (x == y)
1608 return true;
1610 if (VINSN_TYPE (x) != VINSN_TYPE (y))
1611 return false;
1613 if (VINSN_HASH (x) != VINSN_HASH (y))
1614 return false;
1616 repcf = targetm.sched.skip_rtx_p ? skip_unspecs_callback : NULL;
1617 if (VINSN_SEPARABLE_P (x))
1619 /* Compare RHSes of VINSNs. */
1620 gcc_assert (VINSN_RHS (x));
1621 gcc_assert (VINSN_RHS (y));
1623 return rtx_equal_p_cb (VINSN_RHS (x), VINSN_RHS (y), repcf);
1626 return rtx_equal_p_cb (VINSN_PATTERN (x), VINSN_PATTERN (y), repcf);
1630 /* Functions for working with expressions. */
1632 /* Initialize EXPR. */
1633 static void
1634 init_expr (expr_t expr, vinsn_t vi, int spec, int use, int priority,
1635 int sched_times, int orig_bb_index, ds_t spec_done_ds,
1636 ds_t spec_to_check_ds, int orig_sched_cycle,
1637 vec<expr_history_def> history,
1638 signed char target_available,
1639 bool was_substituted, bool was_renamed, bool needs_spec_check_p,
1640 bool cant_move)
1642 vinsn_attach (vi);
1644 EXPR_VINSN (expr) = vi;
1645 EXPR_SPEC (expr) = spec;
1646 EXPR_USEFULNESS (expr) = use;
1647 EXPR_PRIORITY (expr) = priority;
1648 EXPR_PRIORITY_ADJ (expr) = 0;
1649 EXPR_SCHED_TIMES (expr) = sched_times;
1650 EXPR_ORIG_BB_INDEX (expr) = orig_bb_index;
1651 EXPR_ORIG_SCHED_CYCLE (expr) = orig_sched_cycle;
1652 EXPR_SPEC_DONE_DS (expr) = spec_done_ds;
1653 EXPR_SPEC_TO_CHECK_DS (expr) = spec_to_check_ds;
1655 if (history.exists ())
1656 EXPR_HISTORY_OF_CHANGES (expr) = history;
1657 else
1658 EXPR_HISTORY_OF_CHANGES (expr).create (0);
1660 EXPR_TARGET_AVAILABLE (expr) = target_available;
1661 EXPR_WAS_SUBSTITUTED (expr) = was_substituted;
1662 EXPR_WAS_RENAMED (expr) = was_renamed;
1663 EXPR_NEEDS_SPEC_CHECK_P (expr) = needs_spec_check_p;
1664 EXPR_CANT_MOVE (expr) = cant_move;
1667 /* Make a copy of the expr FROM into the expr TO. */
1668 void
1669 copy_expr (expr_t to, expr_t from)
1671 vec<expr_history_def> temp = vNULL;
1673 if (EXPR_HISTORY_OF_CHANGES (from).exists ())
1675 unsigned i;
1676 expr_history_def *phist;
1678 temp = EXPR_HISTORY_OF_CHANGES (from).copy ();
1679 for (i = 0;
1680 temp.iterate (i, &phist);
1681 i++)
1683 vinsn_attach (phist->old_expr_vinsn);
1684 vinsn_attach (phist->new_expr_vinsn);
1688 init_expr (to, EXPR_VINSN (from), EXPR_SPEC (from),
1689 EXPR_USEFULNESS (from), EXPR_PRIORITY (from),
1690 EXPR_SCHED_TIMES (from), EXPR_ORIG_BB_INDEX (from),
1691 EXPR_SPEC_DONE_DS (from), EXPR_SPEC_TO_CHECK_DS (from),
1692 EXPR_ORIG_SCHED_CYCLE (from), temp,
1693 EXPR_TARGET_AVAILABLE (from), EXPR_WAS_SUBSTITUTED (from),
1694 EXPR_WAS_RENAMED (from), EXPR_NEEDS_SPEC_CHECK_P (from),
1695 EXPR_CANT_MOVE (from));
1698 /* Same, but the final expr will not ever be in av sets, so don't copy
1699 "uninteresting" data such as bitmap cache. */
1700 void
1701 copy_expr_onside (expr_t to, expr_t from)
1703 init_expr (to, EXPR_VINSN (from), EXPR_SPEC (from), EXPR_USEFULNESS (from),
1704 EXPR_PRIORITY (from), EXPR_SCHED_TIMES (from), 0,
1705 EXPR_SPEC_DONE_DS (from), EXPR_SPEC_TO_CHECK_DS (from), 0,
1706 vNULL,
1707 EXPR_TARGET_AVAILABLE (from), EXPR_WAS_SUBSTITUTED (from),
1708 EXPR_WAS_RENAMED (from), EXPR_NEEDS_SPEC_CHECK_P (from),
1709 EXPR_CANT_MOVE (from));
1712 /* Prepare the expr of INSN for scheduling. Used when moving insn and when
1713 initializing new insns. */
1714 static void
1715 prepare_insn_expr (insn_t insn, int seqno)
1717 expr_t expr = INSN_EXPR (insn);
1718 ds_t ds;
1720 INSN_SEQNO (insn) = seqno;
1721 EXPR_ORIG_BB_INDEX (expr) = BLOCK_NUM (insn);
1722 EXPR_SPEC (expr) = 0;
1723 EXPR_ORIG_SCHED_CYCLE (expr) = 0;
1724 EXPR_WAS_SUBSTITUTED (expr) = 0;
1725 EXPR_WAS_RENAMED (expr) = 0;
1726 EXPR_TARGET_AVAILABLE (expr) = 1;
1727 INSN_LIVE_VALID_P (insn) = false;
1729 /* ??? If this expression is speculative, make its dependence
1730 as weak as possible. We can filter this expression later
1731 in process_spec_exprs, because we do not distinguish
1732 between the status we got during compute_av_set and the
1733 existing status. To be fixed. */
1734 ds = EXPR_SPEC_DONE_DS (expr);
1735 if (ds)
1736 EXPR_SPEC_DONE_DS (expr) = ds_get_max_dep_weak (ds);
1738 free_history_vect (EXPR_HISTORY_OF_CHANGES (expr));
1741 /* Update target_available bits when merging exprs TO and FROM. SPLIT_POINT
1742 is non-null when expressions are merged from different successors at
1743 a split point. */
1744 static void
1745 update_target_availability (expr_t to, expr_t from, insn_t split_point)
1747 if (EXPR_TARGET_AVAILABLE (to) < 0
1748 || EXPR_TARGET_AVAILABLE (from) < 0)
1749 EXPR_TARGET_AVAILABLE (to) = -1;
1750 else
1752 /* We try to detect the case when one of the expressions
1753 can only be reached through another one. In this case,
1754 we can do better. */
1755 if (split_point == NULL)
1757 int toind, fromind;
1759 toind = EXPR_ORIG_BB_INDEX (to);
1760 fromind = EXPR_ORIG_BB_INDEX (from);
1762 if (toind && toind == fromind)
1763 /* Do nothing -- everything is done in
1764 merge_with_other_exprs. */
1766 else
1767 EXPR_TARGET_AVAILABLE (to) = -1;
1769 else if (EXPR_TARGET_AVAILABLE (from) == 0
1770 && EXPR_LHS (from)
1771 && REG_P (EXPR_LHS (from))
1772 && REGNO (EXPR_LHS (to)) != REGNO (EXPR_LHS (from)))
1773 EXPR_TARGET_AVAILABLE (to) = -1;
1774 else
1775 EXPR_TARGET_AVAILABLE (to) &= EXPR_TARGET_AVAILABLE (from);
1779 /* Update speculation bits when merging exprs TO and FROM. SPLIT_POINT
1780 is non-null when expressions are merged from different successors at
1781 a split point. */
1782 static void
1783 update_speculative_bits (expr_t to, expr_t from, insn_t split_point)
1785 ds_t old_to_ds, old_from_ds;
1787 old_to_ds = EXPR_SPEC_DONE_DS (to);
1788 old_from_ds = EXPR_SPEC_DONE_DS (from);
1790 EXPR_SPEC_DONE_DS (to) = ds_max_merge (old_to_ds, old_from_ds);
1791 EXPR_SPEC_TO_CHECK_DS (to) |= EXPR_SPEC_TO_CHECK_DS (from);
1792 EXPR_NEEDS_SPEC_CHECK_P (to) |= EXPR_NEEDS_SPEC_CHECK_P (from);
1794 /* When merging e.g. control & data speculative exprs, or a control
1795 speculative with a control&data speculative one, we really have
1796 to change vinsn too. Also, when speculative status is changed,
1797 we also need to record this as a transformation in expr's history. */
1798 if ((old_to_ds & SPECULATIVE) || (old_from_ds & SPECULATIVE))
1800 old_to_ds = ds_get_speculation_types (old_to_ds);
1801 old_from_ds = ds_get_speculation_types (old_from_ds);
1803 if (old_to_ds != old_from_ds)
1805 ds_t record_ds;
1807 /* When both expressions are speculative, we need to change
1808 the vinsn first. */
1809 if ((old_to_ds & SPECULATIVE) && (old_from_ds & SPECULATIVE))
1811 int res;
1813 res = speculate_expr (to, EXPR_SPEC_DONE_DS (to));
1814 gcc_assert (res >= 0);
1817 if (split_point != NULL)
1819 /* Record the change with proper status. */
1820 record_ds = EXPR_SPEC_DONE_DS (to) & SPECULATIVE;
1821 record_ds &= ~(old_to_ds & SPECULATIVE);
1822 record_ds &= ~(old_from_ds & SPECULATIVE);
1824 insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (to),
1825 INSN_UID (split_point), TRANS_SPECULATION,
1826 EXPR_VINSN (from), EXPR_VINSN (to),
1827 record_ds);
1834 /* Merge bits of FROM expr to TO expr. When SPLIT_POINT is not NULL,
1835 this is done along different paths. */
1836 void
1837 merge_expr_data (expr_t to, expr_t from, insn_t split_point)
1839 /* Choose the maximum of the specs of merged exprs. This is required
1840 for correctness of bookkeeping. */
1841 if (EXPR_SPEC (to) < EXPR_SPEC (from))
1842 EXPR_SPEC (to) = EXPR_SPEC (from);
1844 if (split_point)
1845 EXPR_USEFULNESS (to) += EXPR_USEFULNESS (from);
1846 else
1847 EXPR_USEFULNESS (to) = MAX (EXPR_USEFULNESS (to),
1848 EXPR_USEFULNESS (from));
1850 if (EXPR_PRIORITY (to) < EXPR_PRIORITY (from))
1851 EXPR_PRIORITY (to) = EXPR_PRIORITY (from);
1853 if (EXPR_SCHED_TIMES (to) > EXPR_SCHED_TIMES (from))
1854 EXPR_SCHED_TIMES (to) = EXPR_SCHED_TIMES (from);
1856 if (EXPR_ORIG_BB_INDEX (to) != EXPR_ORIG_BB_INDEX (from))
1857 EXPR_ORIG_BB_INDEX (to) = 0;
1859 EXPR_ORIG_SCHED_CYCLE (to) = MIN (EXPR_ORIG_SCHED_CYCLE (to),
1860 EXPR_ORIG_SCHED_CYCLE (from));
1862 EXPR_WAS_SUBSTITUTED (to) |= EXPR_WAS_SUBSTITUTED (from);
1863 EXPR_WAS_RENAMED (to) |= EXPR_WAS_RENAMED (from);
1864 EXPR_CANT_MOVE (to) |= EXPR_CANT_MOVE (from);
1866 merge_history_vect (&EXPR_HISTORY_OF_CHANGES (to),
1867 EXPR_HISTORY_OF_CHANGES (from));
1868 update_target_availability (to, from, split_point);
1869 update_speculative_bits (to, from, split_point);
1872 /* Merge bits of FROM expr to TO expr. Vinsns in the exprs should be equal
1873 in terms of vinsn_equal_p. SPLIT_POINT is non-null when expressions
1874 are merged from different successors at a split point. */
1875 void
1876 merge_expr (expr_t to, expr_t from, insn_t split_point)
1878 vinsn_t to_vi = EXPR_VINSN (to);
1879 vinsn_t from_vi = EXPR_VINSN (from);
1881 gcc_assert (vinsn_equal_p (to_vi, from_vi));
1883 /* Make sure that speculative pattern is propagated into exprs that
1884 have non-speculative one. This will provide us with consistent
1885 speculative bits and speculative patterns inside expr. */
1886 if ((EXPR_SPEC_DONE_DS (from) != 0
1887 && EXPR_SPEC_DONE_DS (to) == 0)
1888 /* Do likewise for volatile insns, so that we always retain
1889 the may_trap_p bit on the resulting expression. */
1890 || (VINSN_MAY_TRAP_P (EXPR_VINSN (from))
1891 && !VINSN_MAY_TRAP_P (EXPR_VINSN (to))))
1892 change_vinsn_in_expr (to, EXPR_VINSN (from));
1894 merge_expr_data (to, from, split_point);
1895 gcc_assert (EXPR_USEFULNESS (to) <= REG_BR_PROB_BASE);
1898 /* Clear the information of this EXPR. */
1899 void
1900 clear_expr (expr_t expr)
1903 vinsn_detach (EXPR_VINSN (expr));
1904 EXPR_VINSN (expr) = NULL;
1906 free_history_vect (EXPR_HISTORY_OF_CHANGES (expr));
1909 /* For a given LV_SET, mark EXPR having unavailable target register. */
1910 static void
1911 set_unavailable_target_for_expr (expr_t expr, regset lv_set)
1913 if (EXPR_SEPARABLE_P (expr))
1915 if (REG_P (EXPR_LHS (expr))
1916 && register_unavailable_p (lv_set, EXPR_LHS (expr)))
1918 /* If it's an insn like r1 = use (r1, ...), and it exists in
1919 different forms in each of the av_sets being merged, we can't say
1920 whether original destination register is available or not.
1921 However, this still works if destination register is not used
1922 in the original expression: if the branch at which LV_SET we're
1923 looking here is not actually 'other branch' in sense that same
1924 expression is available through it (but it can't be determined
1925 at computation stage because of transformations on one of the
1926 branches), it still won't affect the availability.
1927 Liveness of a register somewhere on a code motion path means
1928 it's either read somewhere on a codemotion path, live on
1929 'other' branch, live at the point immediately following
1930 the original operation, or is read by the original operation.
1931 The latter case is filtered out in the condition below.
1932 It still doesn't cover the case when register is defined and used
1933 somewhere within the code motion path, and in this case we could
1934 miss a unifying code motion along both branches using a renamed
1935 register, but it won't affect a code correctness since upon
1936 an actual code motion a bookkeeping code would be generated. */
1937 if (register_unavailable_p (VINSN_REG_USES (EXPR_VINSN (expr)),
1938 EXPR_LHS (expr)))
1939 EXPR_TARGET_AVAILABLE (expr) = -1;
1940 else
1941 EXPR_TARGET_AVAILABLE (expr) = false;
1944 else
1946 unsigned regno;
1947 reg_set_iterator rsi;
1949 EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_SETS (EXPR_VINSN (expr)),
1950 0, regno, rsi)
1951 if (bitmap_bit_p (lv_set, regno))
1953 EXPR_TARGET_AVAILABLE (expr) = false;
1954 break;
1957 EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_CLOBBERS (EXPR_VINSN (expr)),
1958 0, regno, rsi)
1959 if (bitmap_bit_p (lv_set, regno))
1961 EXPR_TARGET_AVAILABLE (expr) = false;
1962 break;
1967 /* Try to make EXPR speculative. Return 1 when EXPR's pattern
1968 or dependence status have changed, 2 when also the target register
1969 became unavailable, 0 if nothing had to be changed. */
1971 speculate_expr (expr_t expr, ds_t ds)
1973 int res;
1974 rtx_insn *orig_insn_rtx;
1975 rtx spec_pat;
1976 ds_t target_ds, current_ds;
1978 /* Obtain the status we need to put on EXPR. */
1979 target_ds = (ds & SPECULATIVE);
1980 current_ds = EXPR_SPEC_DONE_DS (expr);
1981 ds = ds_full_merge (current_ds, target_ds, NULL_RTX, NULL_RTX);
1983 orig_insn_rtx = EXPR_INSN_RTX (expr);
1985 res = sched_speculate_insn (orig_insn_rtx, ds, &spec_pat);
1987 switch (res)
1989 case 0:
1990 EXPR_SPEC_DONE_DS (expr) = ds;
1991 return current_ds != ds ? 1 : 0;
1993 case 1:
1995 rtx_insn *spec_insn_rtx =
1996 create_insn_rtx_from_pattern (spec_pat, NULL_RTX);
1997 vinsn_t spec_vinsn = create_vinsn_from_insn_rtx (spec_insn_rtx, false);
1999 change_vinsn_in_expr (expr, spec_vinsn);
2000 EXPR_SPEC_DONE_DS (expr) = ds;
2001 EXPR_NEEDS_SPEC_CHECK_P (expr) = true;
2003 /* Do not allow clobbering the address register of speculative
2004 insns. */
2005 if (register_unavailable_p (VINSN_REG_USES (EXPR_VINSN (expr)),
2006 expr_dest_reg (expr)))
2008 EXPR_TARGET_AVAILABLE (expr) = false;
2009 return 2;
2012 return 1;
2015 case -1:
2016 return -1;
2018 default:
2019 gcc_unreachable ();
2020 return -1;
2024 /* Return a destination register, if any, of EXPR. */
2026 expr_dest_reg (expr_t expr)
2028 rtx dest = VINSN_LHS (EXPR_VINSN (expr));
2030 if (dest != NULL_RTX && REG_P (dest))
2031 return dest;
2033 return NULL_RTX;
2036 /* Returns the REGNO of the R's destination. */
2037 unsigned
2038 expr_dest_regno (expr_t expr)
2040 rtx dest = expr_dest_reg (expr);
2042 gcc_assert (dest != NULL_RTX);
2043 return REGNO (dest);
2046 /* For a given LV_SET, mark all expressions in JOIN_SET, but not present in
2047 AV_SET having unavailable target register. */
2048 void
2049 mark_unavailable_targets (av_set_t join_set, av_set_t av_set, regset lv_set)
2051 expr_t expr;
2052 av_set_iterator avi;
2054 FOR_EACH_EXPR (expr, avi, join_set)
2055 if (av_set_lookup (av_set, EXPR_VINSN (expr)) == NULL)
2056 set_unavailable_target_for_expr (expr, lv_set);
2060 /* Returns true if REG (at least partially) is present in REGS. */
2061 bool
2062 register_unavailable_p (regset regs, rtx reg)
2064 unsigned regno, end_regno;
2066 regno = REGNO (reg);
2067 if (bitmap_bit_p (regs, regno))
2068 return true;
2070 end_regno = END_REGNO (reg);
2072 while (++regno < end_regno)
2073 if (bitmap_bit_p (regs, regno))
2074 return true;
2076 return false;
2079 /* Av set functions. */
2081 /* Add a new element to av set SETP.
2082 Return the element added. */
2083 static av_set_t
2084 av_set_add_element (av_set_t *setp)
2086 /* Insert at the beginning of the list. */
2087 _list_add (setp);
2088 return *setp;
2091 /* Add EXPR to SETP. */
2092 void
2093 av_set_add (av_set_t *setp, expr_t expr)
2095 av_set_t elem;
2097 gcc_assert (!INSN_NOP_P (EXPR_INSN_RTX (expr)));
2098 elem = av_set_add_element (setp);
2099 copy_expr (_AV_SET_EXPR (elem), expr);
2102 /* Same, but do not copy EXPR. */
2103 static void
2104 av_set_add_nocopy (av_set_t *setp, expr_t expr)
2106 av_set_t elem;
2108 elem = av_set_add_element (setp);
2109 *_AV_SET_EXPR (elem) = *expr;
2112 /* Remove expr pointed to by IP from the av_set. */
2113 void
2114 av_set_iter_remove (av_set_iterator *ip)
2116 clear_expr (_AV_SET_EXPR (*ip->lp));
2117 _list_iter_remove (ip);
2120 /* Search for an expr in SET, such that it's equivalent to SOUGHT_VINSN in the
2121 sense of vinsn_equal_p function. Return NULL if no such expr is
2122 in SET was found. */
2123 expr_t
2124 av_set_lookup (av_set_t set, vinsn_t sought_vinsn)
2126 expr_t expr;
2127 av_set_iterator i;
2129 FOR_EACH_EXPR (expr, i, set)
2130 if (vinsn_equal_p (EXPR_VINSN (expr), sought_vinsn))
2131 return expr;
2132 return NULL;
2135 /* Same, but also remove the EXPR found. */
2136 static expr_t
2137 av_set_lookup_and_remove (av_set_t *setp, vinsn_t sought_vinsn)
2139 expr_t expr;
2140 av_set_iterator i;
2142 FOR_EACH_EXPR_1 (expr, i, setp)
2143 if (vinsn_equal_p (EXPR_VINSN (expr), sought_vinsn))
2145 _list_iter_remove_nofree (&i);
2146 return expr;
2148 return NULL;
2151 /* Search for an expr in SET, such that it's equivalent to EXPR in the
2152 sense of vinsn_equal_p function of their vinsns, but not EXPR itself.
2153 Returns NULL if no such expr is in SET was found. */
2154 static expr_t
2155 av_set_lookup_other_equiv_expr (av_set_t set, expr_t expr)
2157 expr_t cur_expr;
2158 av_set_iterator i;
2160 FOR_EACH_EXPR (cur_expr, i, set)
2162 if (cur_expr == expr)
2163 continue;
2164 if (vinsn_equal_p (EXPR_VINSN (cur_expr), EXPR_VINSN (expr)))
2165 return cur_expr;
2168 return NULL;
2171 /* If other expression is already in AVP, remove one of them. */
2172 expr_t
2173 merge_with_other_exprs (av_set_t *avp, av_set_iterator *ip, expr_t expr)
2175 expr_t expr2;
2177 expr2 = av_set_lookup_other_equiv_expr (*avp, expr);
2178 if (expr2 != NULL)
2180 /* Reset target availability on merge, since taking it only from one
2181 of the exprs would be controversial for different code. */
2182 EXPR_TARGET_AVAILABLE (expr2) = -1;
2183 EXPR_USEFULNESS (expr2) = 0;
2185 merge_expr (expr2, expr, NULL);
2187 /* Fix usefulness as it should be now REG_BR_PROB_BASE. */
2188 EXPR_USEFULNESS (expr2) = REG_BR_PROB_BASE;
2190 av_set_iter_remove (ip);
2191 return expr2;
2194 return expr;
2197 /* Return true if there is an expr that correlates to VI in SET. */
2198 bool
2199 av_set_is_in_p (av_set_t set, vinsn_t vi)
2201 return av_set_lookup (set, vi) != NULL;
2204 /* Return a copy of SET. */
2205 av_set_t
2206 av_set_copy (av_set_t set)
2208 expr_t expr;
2209 av_set_iterator i;
2210 av_set_t res = NULL;
2212 FOR_EACH_EXPR (expr, i, set)
2213 av_set_add (&res, expr);
2215 return res;
2218 /* Join two av sets that do not have common elements by attaching second set
2219 (pointed to by FROMP) to the end of first set (TO_TAILP must point to
2220 _AV_SET_NEXT of first set's last element). */
2221 static void
2222 join_distinct_sets (av_set_t *to_tailp, av_set_t *fromp)
2224 gcc_assert (*to_tailp == NULL);
2225 *to_tailp = *fromp;
2226 *fromp = NULL;
2229 /* Makes set pointed to by TO to be the union of TO and FROM. Clear av_set
2230 pointed to by FROMP afterwards. */
2231 void
2232 av_set_union_and_clear (av_set_t *top, av_set_t *fromp, insn_t insn)
2234 expr_t expr1;
2235 av_set_iterator i;
2237 /* Delete from TOP all exprs, that present in FROMP. */
2238 FOR_EACH_EXPR_1 (expr1, i, top)
2240 expr_t expr2 = av_set_lookup (*fromp, EXPR_VINSN (expr1));
2242 if (expr2)
2244 merge_expr (expr2, expr1, insn);
2245 av_set_iter_remove (&i);
2249 join_distinct_sets (i.lp, fromp);
2252 /* Same as above, but also update availability of target register in
2253 TOP judging by TO_LV_SET and FROM_LV_SET. */
2254 void
2255 av_set_union_and_live (av_set_t *top, av_set_t *fromp, regset to_lv_set,
2256 regset from_lv_set, insn_t insn)
2258 expr_t expr1;
2259 av_set_iterator i;
2260 av_set_t *to_tailp, in_both_set = NULL;
2262 /* Delete from TOP all expres, that present in FROMP. */
2263 FOR_EACH_EXPR_1 (expr1, i, top)
2265 expr_t expr2 = av_set_lookup_and_remove (fromp, EXPR_VINSN (expr1));
2267 if (expr2)
2269 /* It may be that the expressions have different destination
2270 registers, in which case we need to check liveness here. */
2271 if (EXPR_SEPARABLE_P (expr1))
2273 int regno1 = (REG_P (EXPR_LHS (expr1))
2274 ? (int) expr_dest_regno (expr1) : -1);
2275 int regno2 = (REG_P (EXPR_LHS (expr2))
2276 ? (int) expr_dest_regno (expr2) : -1);
2278 /* ??? We don't have a way to check restrictions for
2279 *other* register on the current path, we did it only
2280 for the current target register. Give up. */
2281 if (regno1 != regno2)
2282 EXPR_TARGET_AVAILABLE (expr2) = -1;
2284 else if (EXPR_INSN_RTX (expr1) != EXPR_INSN_RTX (expr2))
2285 EXPR_TARGET_AVAILABLE (expr2) = -1;
2287 merge_expr (expr2, expr1, insn);
2288 av_set_add_nocopy (&in_both_set, expr2);
2289 av_set_iter_remove (&i);
2291 else
2292 /* EXPR1 is present in TOP, but not in FROMP. Check it on
2293 FROM_LV_SET. */
2294 set_unavailable_target_for_expr (expr1, from_lv_set);
2296 to_tailp = i.lp;
2298 /* These expressions are not present in TOP. Check liveness
2299 restrictions on TO_LV_SET. */
2300 FOR_EACH_EXPR (expr1, i, *fromp)
2301 set_unavailable_target_for_expr (expr1, to_lv_set);
2303 join_distinct_sets (i.lp, &in_both_set);
2304 join_distinct_sets (to_tailp, fromp);
2307 /* Clear av_set pointed to by SETP. */
2308 void
2309 av_set_clear (av_set_t *setp)
2311 expr_t expr;
2312 av_set_iterator i;
2314 FOR_EACH_EXPR_1 (expr, i, setp)
2315 av_set_iter_remove (&i);
2317 gcc_assert (*setp == NULL);
2320 /* Leave only one non-speculative element in the SETP. */
2321 void
2322 av_set_leave_one_nonspec (av_set_t *setp)
2324 expr_t expr;
2325 av_set_iterator i;
2326 bool has_one_nonspec = false;
2328 /* Keep all speculative exprs, and leave one non-speculative
2329 (the first one). */
2330 FOR_EACH_EXPR_1 (expr, i, setp)
2332 if (!EXPR_SPEC_DONE_DS (expr))
2334 if (has_one_nonspec)
2335 av_set_iter_remove (&i);
2336 else
2337 has_one_nonspec = true;
2342 /* Return the N'th element of the SET. */
2343 expr_t
2344 av_set_element (av_set_t set, int n)
2346 expr_t expr;
2347 av_set_iterator i;
2349 FOR_EACH_EXPR (expr, i, set)
2350 if (n-- == 0)
2351 return expr;
2353 gcc_unreachable ();
2354 return NULL;
2357 /* Deletes all expressions from AVP that are conditional branches (IFs). */
2358 void
2359 av_set_substract_cond_branches (av_set_t *avp)
2361 av_set_iterator i;
2362 expr_t expr;
2364 FOR_EACH_EXPR_1 (expr, i, avp)
2365 if (vinsn_cond_branch_p (EXPR_VINSN (expr)))
2366 av_set_iter_remove (&i);
2369 /* Multiplies usefulness attribute of each member of av-set *AVP by
2370 value PROB / ALL_PROB. */
2371 void
2372 av_set_split_usefulness (av_set_t av, int prob, int all_prob)
2374 av_set_iterator i;
2375 expr_t expr;
2377 FOR_EACH_EXPR (expr, i, av)
2378 EXPR_USEFULNESS (expr) = (all_prob
2379 ? (EXPR_USEFULNESS (expr) * prob) / all_prob
2380 : 0);
2383 /* Leave in AVP only those expressions, which are present in AV,
2384 and return it, merging history expressions. */
2385 void
2386 av_set_code_motion_filter (av_set_t *avp, av_set_t av)
2388 av_set_iterator i;
2389 expr_t expr, expr2;
2391 FOR_EACH_EXPR_1 (expr, i, avp)
2392 if ((expr2 = av_set_lookup (av, EXPR_VINSN (expr))) == NULL)
2393 av_set_iter_remove (&i);
2394 else
2395 /* When updating av sets in bookkeeping blocks, we can add more insns
2396 there which will be transformed but the upper av sets will not
2397 reflect those transformations. We then fail to undo those
2398 when searching for such insns. So merge the history saved
2399 in the av set of the block we are processing. */
2400 merge_history_vect (&EXPR_HISTORY_OF_CHANGES (expr),
2401 EXPR_HISTORY_OF_CHANGES (expr2));
2406 /* Dependence hooks to initialize insn data. */
2408 /* This is used in hooks callable from dependence analysis when initializing
2409 instruction's data. */
2410 static struct
2412 /* Where the dependence was found (lhs/rhs). */
2413 deps_where_t where;
2415 /* The actual data object to initialize. */
2416 idata_t id;
2418 /* True when the insn should not be made clonable. */
2419 bool force_unique_p;
2421 /* True when insn should be treated as of type USE, i.e. never renamed. */
2422 bool force_use_p;
2423 } deps_init_id_data;
2426 /* Setup ID for INSN. FORCE_UNIQUE_P is true when INSN should not be
2427 clonable. */
2428 static void
2429 setup_id_for_insn (idata_t id, insn_t insn, bool force_unique_p)
2431 int type;
2433 /* Determine whether INSN could be cloned and return appropriate vinsn type.
2434 That clonable insns which can be separated into lhs and rhs have type SET.
2435 Other clonable insns have type USE. */
2436 type = GET_CODE (insn);
2438 /* Only regular insns could be cloned. */
2439 if (type == INSN && !force_unique_p)
2440 type = SET;
2441 else if (type == JUMP_INSN && simplejump_p (insn))
2442 type = PC;
2443 else if (type == DEBUG_INSN)
2444 type = !force_unique_p ? USE : INSN;
2446 IDATA_TYPE (id) = type;
2447 IDATA_REG_SETS (id) = get_clear_regset_from_pool ();
2448 IDATA_REG_USES (id) = get_clear_regset_from_pool ();
2449 IDATA_REG_CLOBBERS (id) = get_clear_regset_from_pool ();
2452 /* Start initializing insn data. */
2453 static void
2454 deps_init_id_start_insn (insn_t insn)
2456 gcc_assert (deps_init_id_data.where == DEPS_IN_NOWHERE);
2458 setup_id_for_insn (deps_init_id_data.id, insn,
2459 deps_init_id_data.force_unique_p);
2460 deps_init_id_data.where = DEPS_IN_INSN;
2463 /* Start initializing lhs data. */
2464 static void
2465 deps_init_id_start_lhs (rtx lhs)
2467 gcc_assert (deps_init_id_data.where == DEPS_IN_INSN);
2468 gcc_assert (IDATA_LHS (deps_init_id_data.id) == NULL);
2470 if (IDATA_TYPE (deps_init_id_data.id) == SET)
2472 IDATA_LHS (deps_init_id_data.id) = lhs;
2473 deps_init_id_data.where = DEPS_IN_LHS;
2477 /* Finish initializing lhs data. */
2478 static void
2479 deps_init_id_finish_lhs (void)
2481 deps_init_id_data.where = DEPS_IN_INSN;
2484 /* Note a set of REGNO. */
2485 static void
2486 deps_init_id_note_reg_set (int regno)
2488 haifa_note_reg_set (regno);
2490 if (deps_init_id_data.where == DEPS_IN_RHS)
2491 deps_init_id_data.force_use_p = true;
2493 if (IDATA_TYPE (deps_init_id_data.id) != PC)
2494 SET_REGNO_REG_SET (IDATA_REG_SETS (deps_init_id_data.id), regno);
2496 #ifdef STACK_REGS
2497 /* Make instructions that set stack registers to be ineligible for
2498 renaming to avoid issues with find_used_regs. */
2499 if (IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG))
2500 deps_init_id_data.force_use_p = true;
2501 #endif
2504 /* Note a clobber of REGNO. */
2505 static void
2506 deps_init_id_note_reg_clobber (int regno)
2508 haifa_note_reg_clobber (regno);
2510 if (deps_init_id_data.where == DEPS_IN_RHS)
2511 deps_init_id_data.force_use_p = true;
2513 if (IDATA_TYPE (deps_init_id_data.id) != PC)
2514 SET_REGNO_REG_SET (IDATA_REG_CLOBBERS (deps_init_id_data.id), regno);
2517 /* Note a use of REGNO. */
2518 static void
2519 deps_init_id_note_reg_use (int regno)
2521 haifa_note_reg_use (regno);
2523 if (IDATA_TYPE (deps_init_id_data.id) != PC)
2524 SET_REGNO_REG_SET (IDATA_REG_USES (deps_init_id_data.id), regno);
2527 /* Start initializing rhs data. */
2528 static void
2529 deps_init_id_start_rhs (rtx rhs)
2531 gcc_assert (deps_init_id_data.where == DEPS_IN_INSN);
2533 /* And there was no sel_deps_reset_to_insn (). */
2534 if (IDATA_LHS (deps_init_id_data.id) != NULL)
2536 IDATA_RHS (deps_init_id_data.id) = rhs;
2537 deps_init_id_data.where = DEPS_IN_RHS;
2541 /* Finish initializing rhs data. */
2542 static void
2543 deps_init_id_finish_rhs (void)
2545 gcc_assert (deps_init_id_data.where == DEPS_IN_RHS
2546 || deps_init_id_data.where == DEPS_IN_INSN);
2547 deps_init_id_data.where = DEPS_IN_INSN;
2550 /* Finish initializing insn data. */
2551 static void
2552 deps_init_id_finish_insn (void)
2554 gcc_assert (deps_init_id_data.where == DEPS_IN_INSN);
2556 if (IDATA_TYPE (deps_init_id_data.id) == SET)
2558 rtx lhs = IDATA_LHS (deps_init_id_data.id);
2559 rtx rhs = IDATA_RHS (deps_init_id_data.id);
2561 if (lhs == NULL || rhs == NULL || !lhs_and_rhs_separable_p (lhs, rhs)
2562 || deps_init_id_data.force_use_p)
2564 /* This should be a USE, as we don't want to schedule its RHS
2565 separately. However, we still want to have them recorded
2566 for the purposes of substitution. That's why we don't
2567 simply call downgrade_to_use () here. */
2568 gcc_assert (IDATA_TYPE (deps_init_id_data.id) == SET);
2569 gcc_assert (!lhs == !rhs);
2571 IDATA_TYPE (deps_init_id_data.id) = USE;
2575 deps_init_id_data.where = DEPS_IN_NOWHERE;
2578 /* This is dependence info used for initializing insn's data. */
2579 static struct sched_deps_info_def deps_init_id_sched_deps_info;
2581 /* This initializes most of the static part of the above structure. */
2582 static const struct sched_deps_info_def const_deps_init_id_sched_deps_info =
2584 NULL,
2586 deps_init_id_start_insn,
2587 deps_init_id_finish_insn,
2588 deps_init_id_start_lhs,
2589 deps_init_id_finish_lhs,
2590 deps_init_id_start_rhs,
2591 deps_init_id_finish_rhs,
2592 deps_init_id_note_reg_set,
2593 deps_init_id_note_reg_clobber,
2594 deps_init_id_note_reg_use,
2595 NULL, /* note_mem_dep */
2596 NULL, /* note_dep */
2598 0, /* use_cselib */
2599 0, /* use_deps_list */
2600 0 /* generate_spec_deps */
2603 /* Initialize INSN's lhs and rhs in ID. When FORCE_UNIQUE_P is true,
2604 we don't actually need information about lhs and rhs. */
2605 static void
2606 setup_id_lhs_rhs (idata_t id, insn_t insn, bool force_unique_p)
2608 rtx pat = PATTERN (insn);
2610 if (NONJUMP_INSN_P (insn)
2611 && GET_CODE (pat) == SET
2612 && !force_unique_p)
2614 IDATA_RHS (id) = SET_SRC (pat);
2615 IDATA_LHS (id) = SET_DEST (pat);
2617 else
2618 IDATA_LHS (id) = IDATA_RHS (id) = NULL;
2621 /* Possibly downgrade INSN to USE. */
2622 static void
2623 maybe_downgrade_id_to_use (idata_t id, insn_t insn)
2625 bool must_be_use = false;
2626 df_ref def;
2627 rtx lhs = IDATA_LHS (id);
2628 rtx rhs = IDATA_RHS (id);
2630 /* We downgrade only SETs. */
2631 if (IDATA_TYPE (id) != SET)
2632 return;
2634 if (!lhs || !lhs_and_rhs_separable_p (lhs, rhs))
2636 IDATA_TYPE (id) = USE;
2637 return;
2640 FOR_EACH_INSN_DEF (def, insn)
2642 if (DF_REF_INSN (def)
2643 && DF_REF_FLAGS_IS_SET (def, DF_REF_PRE_POST_MODIFY)
2644 && loc_mentioned_in_p (DF_REF_LOC (def), IDATA_RHS (id)))
2646 must_be_use = true;
2647 break;
2650 #ifdef STACK_REGS
2651 /* Make instructions that set stack registers to be ineligible for
2652 renaming to avoid issues with find_used_regs. */
2653 if (IN_RANGE (DF_REF_REGNO (def), FIRST_STACK_REG, LAST_STACK_REG))
2655 must_be_use = true;
2656 break;
2658 #endif
2661 if (must_be_use)
2662 IDATA_TYPE (id) = USE;
2665 /* Setup register sets describing INSN in ID. */
2666 static void
2667 setup_id_reg_sets (idata_t id, insn_t insn)
2669 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2670 df_ref def, use;
2671 regset tmp = get_clear_regset_from_pool ();
2673 FOR_EACH_INSN_INFO_DEF (def, insn_info)
2675 unsigned int regno = DF_REF_REGNO (def);
2677 /* Post modifies are treated like clobbers by sched-deps.c. */
2678 if (DF_REF_FLAGS_IS_SET (def, (DF_REF_MUST_CLOBBER
2679 | DF_REF_PRE_POST_MODIFY)))
2680 SET_REGNO_REG_SET (IDATA_REG_CLOBBERS (id), regno);
2681 else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
2683 SET_REGNO_REG_SET (IDATA_REG_SETS (id), regno);
2685 #ifdef STACK_REGS
2686 /* For stack registers, treat writes to them as writes
2687 to the first one to be consistent with sched-deps.c. */
2688 if (IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG))
2689 SET_REGNO_REG_SET (IDATA_REG_SETS (id), FIRST_STACK_REG);
2690 #endif
2692 /* Mark special refs that generate read/write def pair. */
2693 if (DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL)
2694 || regno == STACK_POINTER_REGNUM)
2695 bitmap_set_bit (tmp, regno);
2698 FOR_EACH_INSN_INFO_USE (use, insn_info)
2700 unsigned int regno = DF_REF_REGNO (use);
2702 /* When these refs are met for the first time, skip them, as
2703 these uses are just counterparts of some defs. */
2704 if (bitmap_bit_p (tmp, regno))
2705 bitmap_clear_bit (tmp, regno);
2706 else if (! DF_REF_FLAGS_IS_SET (use, DF_REF_CALL_STACK_USAGE))
2708 SET_REGNO_REG_SET (IDATA_REG_USES (id), regno);
2710 #ifdef STACK_REGS
2711 /* For stack registers, treat reads from them as reads from
2712 the first one to be consistent with sched-deps.c. */
2713 if (IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG))
2714 SET_REGNO_REG_SET (IDATA_REG_USES (id), FIRST_STACK_REG);
2715 #endif
2719 return_regset_to_pool (tmp);
2722 /* Initialize instruction data for INSN in ID using DF's data. */
2723 static void
2724 init_id_from_df (idata_t id, insn_t insn, bool force_unique_p)
2726 gcc_assert (DF_INSN_UID_SAFE_GET (INSN_UID (insn)) != NULL);
2728 setup_id_for_insn (id, insn, force_unique_p);
2729 setup_id_lhs_rhs (id, insn, force_unique_p);
2731 if (INSN_NOP_P (insn))
2732 return;
2734 maybe_downgrade_id_to_use (id, insn);
2735 setup_id_reg_sets (id, insn);
2738 /* Initialize instruction data for INSN in ID. */
2739 static void
2740 deps_init_id (idata_t id, insn_t insn, bool force_unique_p)
2742 struct deps_desc _dc, *dc = &_dc;
2744 deps_init_id_data.where = DEPS_IN_NOWHERE;
2745 deps_init_id_data.id = id;
2746 deps_init_id_data.force_unique_p = force_unique_p;
2747 deps_init_id_data.force_use_p = false;
2749 init_deps (dc, false);
2751 memcpy (&deps_init_id_sched_deps_info,
2752 &const_deps_init_id_sched_deps_info,
2753 sizeof (deps_init_id_sched_deps_info));
2755 if (spec_info != NULL)
2756 deps_init_id_sched_deps_info.generate_spec_deps = 1;
2758 sched_deps_info = &deps_init_id_sched_deps_info;
2760 deps_analyze_insn (dc, insn);
2762 free_deps (dc);
2764 deps_init_id_data.id = NULL;
2768 struct sched_scan_info_def
2770 /* This hook notifies scheduler frontend to extend its internal per basic
2771 block data structures. This hook should be called once before a series of
2772 calls to bb_init (). */
2773 void (*extend_bb) (void);
2775 /* This hook makes scheduler frontend to initialize its internal data
2776 structures for the passed basic block. */
2777 void (*init_bb) (basic_block);
2779 /* This hook notifies scheduler frontend to extend its internal per insn data
2780 structures. This hook should be called once before a series of calls to
2781 insn_init (). */
2782 void (*extend_insn) (void);
2784 /* This hook makes scheduler frontend to initialize its internal data
2785 structures for the passed insn. */
2786 void (*init_insn) (insn_t);
2789 /* A driver function to add a set of basic blocks (BBS) to the
2790 scheduling region. */
2791 static void
2792 sched_scan (const struct sched_scan_info_def *ssi, bb_vec_t bbs)
2794 unsigned i;
2795 basic_block bb;
2797 if (ssi->extend_bb)
2798 ssi->extend_bb ();
2800 if (ssi->init_bb)
2801 FOR_EACH_VEC_ELT (bbs, i, bb)
2802 ssi->init_bb (bb);
2804 if (ssi->extend_insn)
2805 ssi->extend_insn ();
2807 if (ssi->init_insn)
2808 FOR_EACH_VEC_ELT (bbs, i, bb)
2810 rtx_insn *insn;
2812 FOR_BB_INSNS (bb, insn)
2813 ssi->init_insn (insn);
2817 /* Implement hooks for collecting fundamental insn properties like if insn is
2818 an ASM or is within a SCHED_GROUP. */
2820 /* True when a "one-time init" data for INSN was already inited. */
2821 static bool
2822 first_time_insn_init (insn_t insn)
2824 return INSN_LIVE (insn) == NULL;
2827 /* Hash an entry in a transformed_insns hashtable. */
2828 static hashval_t
2829 hash_transformed_insns (const void *p)
2831 return VINSN_HASH_RTX (((const struct transformed_insns *) p)->vinsn_old);
2834 /* Compare the entries in a transformed_insns hashtable. */
2835 static int
2836 eq_transformed_insns (const void *p, const void *q)
2838 rtx_insn *i1 =
2839 VINSN_INSN_RTX (((const struct transformed_insns *) p)->vinsn_old);
2840 rtx_insn *i2 =
2841 VINSN_INSN_RTX (((const struct transformed_insns *) q)->vinsn_old);
2843 if (INSN_UID (i1) == INSN_UID (i2))
2844 return 1;
2845 return rtx_equal_p (PATTERN (i1), PATTERN (i2));
2848 /* Free an entry in a transformed_insns hashtable. */
2849 static void
2850 free_transformed_insns (void *p)
2852 struct transformed_insns *pti = (struct transformed_insns *) p;
2854 vinsn_detach (pti->vinsn_old);
2855 vinsn_detach (pti->vinsn_new);
2856 free (pti);
2859 /* Init the s_i_d data for INSN which should be inited just once, when
2860 we first see the insn. */
2861 static void
2862 init_first_time_insn_data (insn_t insn)
2864 /* This should not be set if this is the first time we init data for
2865 insn. */
2866 gcc_assert (first_time_insn_init (insn));
2868 /* These are needed for nops too. */
2869 INSN_LIVE (insn) = get_regset_from_pool ();
2870 INSN_LIVE_VALID_P (insn) = false;
2872 if (!INSN_NOP_P (insn))
2874 INSN_ANALYZED_DEPS (insn) = BITMAP_ALLOC (NULL);
2875 INSN_FOUND_DEPS (insn) = BITMAP_ALLOC (NULL);
2876 INSN_TRANSFORMED_INSNS (insn)
2877 = htab_create (16, hash_transformed_insns,
2878 eq_transformed_insns, free_transformed_insns);
2879 init_deps (&INSN_DEPS_CONTEXT (insn), true);
2883 /* Free almost all above data for INSN that is scheduled already.
2884 Used for extra-large basic blocks. */
2885 void
2886 free_data_for_scheduled_insn (insn_t insn)
2888 gcc_assert (! first_time_insn_init (insn));
2890 if (! INSN_ANALYZED_DEPS (insn))
2891 return;
2893 BITMAP_FREE (INSN_ANALYZED_DEPS (insn));
2894 BITMAP_FREE (INSN_FOUND_DEPS (insn));
2895 htab_delete (INSN_TRANSFORMED_INSNS (insn));
2897 /* This is allocated only for bookkeeping insns. */
2898 if (INSN_ORIGINATORS (insn))
2899 BITMAP_FREE (INSN_ORIGINATORS (insn));
2900 free_deps (&INSN_DEPS_CONTEXT (insn));
2902 INSN_ANALYZED_DEPS (insn) = NULL;
2904 /* Clear the readonly flag so we would ICE when trying to recalculate
2905 the deps context (as we believe that it should not happen). */
2906 (&INSN_DEPS_CONTEXT (insn))->readonly = 0;
2909 /* Free the same data as above for INSN. */
2910 static void
2911 free_first_time_insn_data (insn_t insn)
2913 gcc_assert (! first_time_insn_init (insn));
2915 free_data_for_scheduled_insn (insn);
2916 return_regset_to_pool (INSN_LIVE (insn));
2917 INSN_LIVE (insn) = NULL;
2918 INSN_LIVE_VALID_P (insn) = false;
2921 /* Initialize region-scope data structures for basic blocks. */
2922 static void
2923 init_global_and_expr_for_bb (basic_block bb)
2925 if (sel_bb_empty_p (bb))
2926 return;
2928 invalidate_av_set (bb);
2931 /* Data for global dependency analysis (to initialize CANT_MOVE and
2932 SCHED_GROUP_P). */
2933 static struct
2935 /* Previous insn. */
2936 insn_t prev_insn;
2937 } init_global_data;
2939 /* Determine if INSN is in the sched_group, is an asm or should not be
2940 cloned. After that initialize its expr. */
2941 static void
2942 init_global_and_expr_for_insn (insn_t insn)
2944 if (LABEL_P (insn))
2945 return;
2947 if (NOTE_INSN_BASIC_BLOCK_P (insn))
2949 init_global_data.prev_insn = NULL;
2950 return;
2953 gcc_assert (INSN_P (insn));
2955 if (SCHED_GROUP_P (insn))
2956 /* Setup a sched_group. */
2958 insn_t prev_insn = init_global_data.prev_insn;
2960 if (prev_insn)
2961 INSN_SCHED_NEXT (prev_insn) = insn;
2963 init_global_data.prev_insn = insn;
2965 else
2966 init_global_data.prev_insn = NULL;
2968 if (GET_CODE (PATTERN (insn)) == ASM_INPUT
2969 || asm_noperands (PATTERN (insn)) >= 0)
2970 /* Mark INSN as an asm. */
2971 INSN_ASM_P (insn) = true;
2974 bool force_unique_p;
2975 ds_t spec_done_ds;
2977 /* Certain instructions cannot be cloned, and frame related insns and
2978 the insn adjacent to NOTE_INSN_EPILOGUE_BEG cannot be moved out of
2979 their block. */
2980 if (prologue_epilogue_contains (insn))
2982 if (RTX_FRAME_RELATED_P (insn))
2983 CANT_MOVE (insn) = 1;
2984 else
2986 rtx note;
2987 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
2988 if (REG_NOTE_KIND (note) == REG_SAVE_NOTE
2989 && ((enum insn_note) INTVAL (XEXP (note, 0))
2990 == NOTE_INSN_EPILOGUE_BEG))
2992 CANT_MOVE (insn) = 1;
2993 break;
2996 force_unique_p = true;
2998 else
2999 if (CANT_MOVE (insn)
3000 || INSN_ASM_P (insn)
3001 || SCHED_GROUP_P (insn)
3002 || CALL_P (insn)
3003 /* Exception handling insns are always unique. */
3004 || (cfun->can_throw_non_call_exceptions && can_throw_internal (insn))
3005 /* TRAP_IF though have an INSN code is control_flow_insn_p (). */
3006 || control_flow_insn_p (insn)
3007 || volatile_insn_p (PATTERN (insn))
3008 || (targetm.cannot_copy_insn_p
3009 && targetm.cannot_copy_insn_p (insn)))
3010 force_unique_p = true;
3011 else
3012 force_unique_p = false;
3014 if (targetm.sched.get_insn_spec_ds)
3016 spec_done_ds = targetm.sched.get_insn_spec_ds (insn);
3017 spec_done_ds = ds_get_max_dep_weak (spec_done_ds);
3019 else
3020 spec_done_ds = 0;
3022 /* Initialize INSN's expr. */
3023 init_expr (INSN_EXPR (insn), vinsn_create (insn, force_unique_p), 0,
3024 REG_BR_PROB_BASE, INSN_PRIORITY (insn), 0, BLOCK_NUM (insn),
3025 spec_done_ds, 0, 0, vNULL, true,
3026 false, false, false, CANT_MOVE (insn));
3029 init_first_time_insn_data (insn);
3032 /* Scan the region and initialize instruction data for basic blocks BBS. */
3033 void
3034 sel_init_global_and_expr (bb_vec_t bbs)
3036 /* ??? It would be nice to implement push / pop scheme for sched_infos. */
3037 const struct sched_scan_info_def ssi =
3039 NULL, /* extend_bb */
3040 init_global_and_expr_for_bb, /* init_bb */
3041 extend_insn_data, /* extend_insn */
3042 init_global_and_expr_for_insn /* init_insn */
3045 sched_scan (&ssi, bbs);
3048 /* Finalize region-scope data structures for basic blocks. */
3049 static void
3050 finish_global_and_expr_for_bb (basic_block bb)
3052 av_set_clear (&BB_AV_SET (bb));
3053 BB_AV_LEVEL (bb) = 0;
3056 /* Finalize INSN's data. */
3057 static void
3058 finish_global_and_expr_insn (insn_t insn)
3060 if (LABEL_P (insn) || NOTE_INSN_BASIC_BLOCK_P (insn))
3061 return;
3063 gcc_assert (INSN_P (insn));
3065 if (INSN_LUID (insn) > 0)
3067 free_first_time_insn_data (insn);
3068 INSN_WS_LEVEL (insn) = 0;
3069 CANT_MOVE (insn) = 0;
3071 /* We can no longer assert this, as vinsns of this insn could be
3072 easily live in other insn's caches. This should be changed to
3073 a counter-like approach among all vinsns. */
3074 gcc_assert (true || VINSN_COUNT (INSN_VINSN (insn)) == 1);
3075 clear_expr (INSN_EXPR (insn));
3079 /* Finalize per instruction data for the whole region. */
3080 void
3081 sel_finish_global_and_expr (void)
3084 bb_vec_t bbs;
3085 int i;
3087 bbs.create (current_nr_blocks);
3089 for (i = 0; i < current_nr_blocks; i++)
3090 bbs.quick_push (BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (i)));
3092 /* Clear AV_SETs and INSN_EXPRs. */
3094 const struct sched_scan_info_def ssi =
3096 NULL, /* extend_bb */
3097 finish_global_and_expr_for_bb, /* init_bb */
3098 NULL, /* extend_insn */
3099 finish_global_and_expr_insn /* init_insn */
3102 sched_scan (&ssi, bbs);
3105 bbs.release ();
3108 finish_insns ();
3112 /* In the below hooks, we merely calculate whether or not a dependence
3113 exists, and in what part of insn. However, we will need more data
3114 when we'll start caching dependence requests. */
3116 /* Container to hold information for dependency analysis. */
3117 static struct
3119 deps_t dc;
3121 /* A variable to track which part of rtx we are scanning in
3122 sched-deps.c: sched_analyze_insn (). */
3123 deps_where_t where;
3125 /* Current producer. */
3126 insn_t pro;
3128 /* Current consumer. */
3129 vinsn_t con;
3131 /* Is SEL_DEPS_HAS_DEP_P[DEPS_IN_X] is true, then X has a dependence.
3132 X is from { INSN, LHS, RHS }. */
3133 ds_t has_dep_p[DEPS_IN_NOWHERE];
3134 } has_dependence_data;
3136 /* Start analyzing dependencies of INSN. */
3137 static void
3138 has_dependence_start_insn (insn_t insn ATTRIBUTE_UNUSED)
3140 gcc_assert (has_dependence_data.where == DEPS_IN_NOWHERE);
3142 has_dependence_data.where = DEPS_IN_INSN;
3145 /* Finish analyzing dependencies of an insn. */
3146 static void
3147 has_dependence_finish_insn (void)
3149 gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
3151 has_dependence_data.where = DEPS_IN_NOWHERE;
3154 /* Start analyzing dependencies of LHS. */
3155 static void
3156 has_dependence_start_lhs (rtx lhs ATTRIBUTE_UNUSED)
3158 gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
3160 if (VINSN_LHS (has_dependence_data.con) != NULL)
3161 has_dependence_data.where = DEPS_IN_LHS;
3164 /* Finish analyzing dependencies of an lhs. */
3165 static void
3166 has_dependence_finish_lhs (void)
3168 has_dependence_data.where = DEPS_IN_INSN;
3171 /* Start analyzing dependencies of RHS. */
3172 static void
3173 has_dependence_start_rhs (rtx rhs ATTRIBUTE_UNUSED)
3175 gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
3177 if (VINSN_RHS (has_dependence_data.con) != NULL)
3178 has_dependence_data.where = DEPS_IN_RHS;
3181 /* Start analyzing dependencies of an rhs. */
3182 static void
3183 has_dependence_finish_rhs (void)
3185 gcc_assert (has_dependence_data.where == DEPS_IN_RHS
3186 || has_dependence_data.where == DEPS_IN_INSN);
3188 has_dependence_data.where = DEPS_IN_INSN;
3191 /* Note a set of REGNO. */
3192 static void
3193 has_dependence_note_reg_set (int regno)
3195 struct deps_reg *reg_last = &has_dependence_data.dc->reg_last[regno];
3197 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3198 VINSN_INSN_RTX
3199 (has_dependence_data.con)))
3201 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3203 if (reg_last->sets != NULL
3204 || reg_last->clobbers != NULL)
3205 *dsp = (*dsp & ~SPECULATIVE) | DEP_OUTPUT;
3207 if (reg_last->uses || reg_last->implicit_sets)
3208 *dsp = (*dsp & ~SPECULATIVE) | DEP_ANTI;
3212 /* Note a clobber of REGNO. */
3213 static void
3214 has_dependence_note_reg_clobber (int regno)
3216 struct deps_reg *reg_last = &has_dependence_data.dc->reg_last[regno];
3218 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3219 VINSN_INSN_RTX
3220 (has_dependence_data.con)))
3222 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3224 if (reg_last->sets)
3225 *dsp = (*dsp & ~SPECULATIVE) | DEP_OUTPUT;
3227 if (reg_last->uses || reg_last->implicit_sets)
3228 *dsp = (*dsp & ~SPECULATIVE) | DEP_ANTI;
3232 /* Note a use of REGNO. */
3233 static void
3234 has_dependence_note_reg_use (int regno)
3236 struct deps_reg *reg_last = &has_dependence_data.dc->reg_last[regno];
3238 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3239 VINSN_INSN_RTX
3240 (has_dependence_data.con)))
3242 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3244 if (reg_last->sets)
3245 *dsp = (*dsp & ~SPECULATIVE) | DEP_TRUE;
3247 if (reg_last->clobbers || reg_last->implicit_sets)
3248 *dsp = (*dsp & ~SPECULATIVE) | DEP_ANTI;
3250 /* Merge BE_IN_SPEC bits into *DSP when the dependency producer
3251 is actually a check insn. We need to do this for any register
3252 read-read dependency with the check unless we track properly
3253 all registers written by BE_IN_SPEC-speculated insns, as
3254 we don't have explicit dependence lists. See PR 53975. */
3255 if (reg_last->uses)
3257 ds_t pro_spec_checked_ds;
3259 pro_spec_checked_ds = INSN_SPEC_CHECKED_DS (has_dependence_data.pro);
3260 pro_spec_checked_ds = ds_get_max_dep_weak (pro_spec_checked_ds);
3262 if (pro_spec_checked_ds != 0)
3263 *dsp = ds_full_merge (*dsp, pro_spec_checked_ds,
3264 NULL_RTX, NULL_RTX);
3269 /* Note a memory dependence. */
3270 static void
3271 has_dependence_note_mem_dep (rtx mem ATTRIBUTE_UNUSED,
3272 rtx pending_mem ATTRIBUTE_UNUSED,
3273 insn_t pending_insn ATTRIBUTE_UNUSED,
3274 ds_t ds ATTRIBUTE_UNUSED)
3276 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3277 VINSN_INSN_RTX (has_dependence_data.con)))
3279 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3281 *dsp = ds_full_merge (ds, *dsp, pending_mem, mem);
3285 /* Note a dependence. */
3286 static void
3287 has_dependence_note_dep (insn_t pro ATTRIBUTE_UNUSED,
3288 ds_t ds ATTRIBUTE_UNUSED)
3290 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3291 VINSN_INSN_RTX (has_dependence_data.con)))
3293 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3295 *dsp = ds_full_merge (ds, *dsp, NULL_RTX, NULL_RTX);
3299 /* Mark the insn as having a hard dependence that prevents speculation. */
3300 void
3301 sel_mark_hard_insn (rtx insn)
3303 int i;
3305 /* Only work when we're in has_dependence_p mode.
3306 ??? This is a hack, this should actually be a hook. */
3307 if (!has_dependence_data.dc || !has_dependence_data.pro)
3308 return;
3310 gcc_assert (insn == VINSN_INSN_RTX (has_dependence_data.con));
3311 gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
3313 for (i = 0; i < DEPS_IN_NOWHERE; i++)
3314 has_dependence_data.has_dep_p[i] &= ~SPECULATIVE;
3317 /* This structure holds the hooks for the dependency analysis used when
3318 actually processing dependencies in the scheduler. */
3319 static struct sched_deps_info_def has_dependence_sched_deps_info;
3321 /* This initializes most of the fields of the above structure. */
3322 static const struct sched_deps_info_def const_has_dependence_sched_deps_info =
3324 NULL,
3326 has_dependence_start_insn,
3327 has_dependence_finish_insn,
3328 has_dependence_start_lhs,
3329 has_dependence_finish_lhs,
3330 has_dependence_start_rhs,
3331 has_dependence_finish_rhs,
3332 has_dependence_note_reg_set,
3333 has_dependence_note_reg_clobber,
3334 has_dependence_note_reg_use,
3335 has_dependence_note_mem_dep,
3336 has_dependence_note_dep,
3338 0, /* use_cselib */
3339 0, /* use_deps_list */
3340 0 /* generate_spec_deps */
3343 /* Initialize has_dependence_sched_deps_info with extra spec field. */
3344 static void
3345 setup_has_dependence_sched_deps_info (void)
3347 memcpy (&has_dependence_sched_deps_info,
3348 &const_has_dependence_sched_deps_info,
3349 sizeof (has_dependence_sched_deps_info));
3351 if (spec_info != NULL)
3352 has_dependence_sched_deps_info.generate_spec_deps = 1;
3354 sched_deps_info = &has_dependence_sched_deps_info;
3357 /* Remove all dependences found and recorded in has_dependence_data array. */
3358 void
3359 sel_clear_has_dependence (void)
3361 int i;
3363 for (i = 0; i < DEPS_IN_NOWHERE; i++)
3364 has_dependence_data.has_dep_p[i] = 0;
3367 /* Return nonzero if EXPR has is dependent upon PRED. Return the pointer
3368 to the dependence information array in HAS_DEP_PP. */
3369 ds_t
3370 has_dependence_p (expr_t expr, insn_t pred, ds_t **has_dep_pp)
3372 int i;
3373 ds_t ds;
3374 struct deps_desc *dc;
3376 if (INSN_SIMPLEJUMP_P (pred))
3377 /* Unconditional jump is just a transfer of control flow.
3378 Ignore it. */
3379 return false;
3381 dc = &INSN_DEPS_CONTEXT (pred);
3383 /* We init this field lazily. */
3384 if (dc->reg_last == NULL)
3385 init_deps_reg_last (dc);
3387 if (!dc->readonly)
3389 has_dependence_data.pro = NULL;
3390 /* Initialize empty dep context with information about PRED. */
3391 advance_deps_context (dc, pred);
3392 dc->readonly = 1;
3395 has_dependence_data.where = DEPS_IN_NOWHERE;
3396 has_dependence_data.pro = pred;
3397 has_dependence_data.con = EXPR_VINSN (expr);
3398 has_dependence_data.dc = dc;
3400 sel_clear_has_dependence ();
3402 /* Now catch all dependencies that would be generated between PRED and
3403 INSN. */
3404 setup_has_dependence_sched_deps_info ();
3405 deps_analyze_insn (dc, EXPR_INSN_RTX (expr));
3406 has_dependence_data.dc = NULL;
3408 /* When a barrier was found, set DEPS_IN_INSN bits. */
3409 if (dc->last_reg_pending_barrier == TRUE_BARRIER)
3410 has_dependence_data.has_dep_p[DEPS_IN_INSN] = DEP_TRUE;
3411 else if (dc->last_reg_pending_barrier == MOVE_BARRIER)
3412 has_dependence_data.has_dep_p[DEPS_IN_INSN] = DEP_ANTI;
3414 /* Do not allow stores to memory to move through checks. Currently
3415 we don't move this to sched-deps.c as the check doesn't have
3416 obvious places to which this dependence can be attached.
3417 FIMXE: this should go to a hook. */
3418 if (EXPR_LHS (expr)
3419 && MEM_P (EXPR_LHS (expr))
3420 && sel_insn_is_speculation_check (pred))
3421 has_dependence_data.has_dep_p[DEPS_IN_INSN] = DEP_ANTI;
3423 *has_dep_pp = has_dependence_data.has_dep_p;
3424 ds = 0;
3425 for (i = 0; i < DEPS_IN_NOWHERE; i++)
3426 ds = ds_full_merge (ds, has_dependence_data.has_dep_p[i],
3427 NULL_RTX, NULL_RTX);
3429 return ds;
3433 /* Dependence hooks implementation that checks dependence latency constraints
3434 on the insns being scheduled. The entry point for these routines is
3435 tick_check_p predicate. */
3437 static struct
3439 /* An expr we are currently checking. */
3440 expr_t expr;
3442 /* A minimal cycle for its scheduling. */
3443 int cycle;
3445 /* Whether we have seen a true dependence while checking. */
3446 bool seen_true_dep_p;
3447 } tick_check_data;
3449 /* Update minimal scheduling cycle for tick_check_insn given that it depends
3450 on PRO with status DS and weight DW. */
3451 static void
3452 tick_check_dep_with_dw (insn_t pro_insn, ds_t ds, dw_t dw)
3454 expr_t con_expr = tick_check_data.expr;
3455 insn_t con_insn = EXPR_INSN_RTX (con_expr);
3457 if (con_insn != pro_insn)
3459 enum reg_note dt;
3460 int tick;
3462 if (/* PROducer was removed from above due to pipelining. */
3463 !INSN_IN_STREAM_P (pro_insn)
3464 /* Or PROducer was originally on the next iteration regarding the
3465 CONsumer. */
3466 || (INSN_SCHED_TIMES (pro_insn)
3467 - EXPR_SCHED_TIMES (con_expr)) > 1)
3468 /* Don't count this dependence. */
3469 return;
3471 dt = ds_to_dt (ds);
3472 if (dt == REG_DEP_TRUE)
3473 tick_check_data.seen_true_dep_p = true;
3475 gcc_assert (INSN_SCHED_CYCLE (pro_insn) > 0);
3478 dep_def _dep, *dep = &_dep;
3480 init_dep (dep, pro_insn, con_insn, dt);
3482 tick = INSN_SCHED_CYCLE (pro_insn) + dep_cost_1 (dep, dw);
3485 /* When there are several kinds of dependencies between pro and con,
3486 only REG_DEP_TRUE should be taken into account. */
3487 if (tick > tick_check_data.cycle
3488 && (dt == REG_DEP_TRUE || !tick_check_data.seen_true_dep_p))
3489 tick_check_data.cycle = tick;
3493 /* An implementation of note_dep hook. */
3494 static void
3495 tick_check_note_dep (insn_t pro, ds_t ds)
3497 tick_check_dep_with_dw (pro, ds, 0);
3500 /* An implementation of note_mem_dep hook. */
3501 static void
3502 tick_check_note_mem_dep (rtx mem1, rtx mem2, insn_t pro, ds_t ds)
3504 dw_t dw;
3506 dw = (ds_to_dt (ds) == REG_DEP_TRUE
3507 ? estimate_dep_weak (mem1, mem2)
3508 : 0);
3510 tick_check_dep_with_dw (pro, ds, dw);
3513 /* This structure contains hooks for dependence analysis used when determining
3514 whether an insn is ready for scheduling. */
3515 static struct sched_deps_info_def tick_check_sched_deps_info =
3517 NULL,
3519 NULL,
3520 NULL,
3521 NULL,
3522 NULL,
3523 NULL,
3524 NULL,
3525 haifa_note_reg_set,
3526 haifa_note_reg_clobber,
3527 haifa_note_reg_use,
3528 tick_check_note_mem_dep,
3529 tick_check_note_dep,
3531 0, 0, 0
3534 /* Estimate number of cycles from the current cycle of FENCE until EXPR can be
3535 scheduled. Return 0 if all data from producers in DC is ready. */
3537 tick_check_p (expr_t expr, deps_t dc, fence_t fence)
3539 int cycles_left;
3540 /* Initialize variables. */
3541 tick_check_data.expr = expr;
3542 tick_check_data.cycle = 0;
3543 tick_check_data.seen_true_dep_p = false;
3544 sched_deps_info = &tick_check_sched_deps_info;
3546 gcc_assert (!dc->readonly);
3547 dc->readonly = 1;
3548 deps_analyze_insn (dc, EXPR_INSN_RTX (expr));
3549 dc->readonly = 0;
3551 cycles_left = tick_check_data.cycle - FENCE_CYCLE (fence);
3553 return cycles_left >= 0 ? cycles_left : 0;
3557 /* Functions to work with insns. */
3559 /* Returns true if LHS of INSN is the same as DEST of an insn
3560 being moved. */
3561 bool
3562 lhs_of_insn_equals_to_dest_p (insn_t insn, rtx dest)
3564 rtx lhs = INSN_LHS (insn);
3566 if (lhs == NULL || dest == NULL)
3567 return false;
3569 return rtx_equal_p (lhs, dest);
3572 /* Return s_i_d entry of INSN. Callable from debugger. */
3573 sel_insn_data_def
3574 insn_sid (insn_t insn)
3576 return *SID (insn);
3579 /* True when INSN is a speculative check. We can tell this by looking
3580 at the data structures of the selective scheduler, not by examining
3581 the pattern. */
3582 bool
3583 sel_insn_is_speculation_check (rtx insn)
3585 return s_i_d.exists () && !! INSN_SPEC_CHECKED_DS (insn);
3588 /* Extracts machine mode MODE and destination location DST_LOC
3589 for given INSN. */
3590 void
3591 get_dest_and_mode (rtx insn, rtx *dst_loc, machine_mode *mode)
3593 rtx pat = PATTERN (insn);
3595 gcc_assert (dst_loc);
3596 gcc_assert (GET_CODE (pat) == SET);
3598 *dst_loc = SET_DEST (pat);
3600 gcc_assert (*dst_loc);
3601 gcc_assert (MEM_P (*dst_loc) || REG_P (*dst_loc));
3603 if (mode)
3604 *mode = GET_MODE (*dst_loc);
3607 /* Returns true when moving through JUMP will result in bookkeeping
3608 creation. */
3609 bool
3610 bookkeeping_can_be_created_if_moved_through_p (insn_t jump)
3612 insn_t succ;
3613 succ_iterator si;
3615 FOR_EACH_SUCC (succ, si, jump)
3616 if (sel_num_cfg_preds_gt_1 (succ))
3617 return true;
3619 return false;
3622 /* Return 'true' if INSN is the only one in its basic block. */
3623 static bool
3624 insn_is_the_only_one_in_bb_p (insn_t insn)
3626 return sel_bb_head_p (insn) && sel_bb_end_p (insn);
3629 #ifdef ENABLE_CHECKING
3630 /* Check that the region we're scheduling still has at most one
3631 backedge. */
3632 static void
3633 verify_backedges (void)
3635 if (pipelining_p)
3637 int i, n = 0;
3638 edge e;
3639 edge_iterator ei;
3641 for (i = 0; i < current_nr_blocks; i++)
3642 FOR_EACH_EDGE (e, ei, BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (i))->succs)
3643 if (in_current_region_p (e->dest)
3644 && BLOCK_TO_BB (e->dest->index) < i)
3645 n++;
3647 gcc_assert (n <= 1);
3650 #endif
3653 /* Functions to work with control flow. */
3655 /* Recompute BLOCK_TO_BB and BB_FOR_BLOCK for current region so that blocks
3656 are sorted in topological order (it might have been invalidated by
3657 redirecting an edge). */
3658 static void
3659 sel_recompute_toporder (void)
3661 int i, n, rgn;
3662 int *postorder, n_blocks;
3664 postorder = XALLOCAVEC (int, n_basic_blocks_for_fn (cfun));
3665 n_blocks = post_order_compute (postorder, false, false);
3667 rgn = CONTAINING_RGN (BB_TO_BLOCK (0));
3668 for (n = 0, i = n_blocks - 1; i >= 0; i--)
3669 if (CONTAINING_RGN (postorder[i]) == rgn)
3671 BLOCK_TO_BB (postorder[i]) = n;
3672 BB_TO_BLOCK (n) = postorder[i];
3673 n++;
3676 /* Assert that we updated info for all blocks. We may miss some blocks if
3677 this function is called when redirecting an edge made a block
3678 unreachable, but that block is not deleted yet. */
3679 gcc_assert (n == RGN_NR_BLOCKS (rgn));
3682 /* Tidy the possibly empty block BB. */
3683 static bool
3684 maybe_tidy_empty_bb (basic_block bb)
3686 basic_block succ_bb, pred_bb, note_bb;
3687 vec<basic_block> dom_bbs;
3688 edge e;
3689 edge_iterator ei;
3690 bool rescan_p;
3692 /* Keep empty bb only if this block immediately precedes EXIT and
3693 has incoming non-fallthrough edge, or it has no predecessors or
3694 successors. Otherwise remove it. */
3695 if (!sel_bb_empty_p (bb)
3696 || (single_succ_p (bb)
3697 && single_succ (bb) == EXIT_BLOCK_PTR_FOR_FN (cfun)
3698 && (!single_pred_p (bb)
3699 || !(single_pred_edge (bb)->flags & EDGE_FALLTHRU)))
3700 || EDGE_COUNT (bb->preds) == 0
3701 || EDGE_COUNT (bb->succs) == 0)
3702 return false;
3704 /* Do not attempt to redirect complex edges. */
3705 FOR_EACH_EDGE (e, ei, bb->preds)
3706 if (e->flags & EDGE_COMPLEX)
3707 return false;
3708 else if (e->flags & EDGE_FALLTHRU)
3710 rtx note;
3711 /* If prev bb ends with asm goto, see if any of the
3712 ASM_OPERANDS_LABELs don't point to the fallthru
3713 label. Do not attempt to redirect it in that case. */
3714 if (JUMP_P (BB_END (e->src))
3715 && (note = extract_asm_operands (PATTERN (BB_END (e->src)))))
3717 int i, n = ASM_OPERANDS_LABEL_LENGTH (note);
3719 for (i = 0; i < n; ++i)
3720 if (XEXP (ASM_OPERANDS_LABEL (note, i), 0) == BB_HEAD (bb))
3721 return false;
3725 free_data_sets (bb);
3727 /* Do not delete BB if it has more than one successor.
3728 That can occur when we moving a jump. */
3729 if (!single_succ_p (bb))
3731 gcc_assert (can_merge_blocks_p (bb->prev_bb, bb));
3732 sel_merge_blocks (bb->prev_bb, bb);
3733 return true;
3736 succ_bb = single_succ (bb);
3737 rescan_p = true;
3738 pred_bb = NULL;
3739 dom_bbs.create (0);
3741 /* Save a pred/succ from the current region to attach the notes to. */
3742 note_bb = NULL;
3743 FOR_EACH_EDGE (e, ei, bb->preds)
3744 if (in_current_region_p (e->src))
3746 note_bb = e->src;
3747 break;
3749 if (note_bb == NULL)
3750 note_bb = succ_bb;
3752 /* Redirect all non-fallthru edges to the next bb. */
3753 while (rescan_p)
3755 rescan_p = false;
3757 FOR_EACH_EDGE (e, ei, bb->preds)
3759 pred_bb = e->src;
3761 if (!(e->flags & EDGE_FALLTHRU))
3763 /* We can not invalidate computed topological order by moving
3764 the edge destination block (E->SUCC) along a fallthru edge.
3766 We will update dominators here only when we'll get
3767 an unreachable block when redirecting, otherwise
3768 sel_redirect_edge_and_branch will take care of it. */
3769 if (e->dest != bb
3770 && single_pred_p (e->dest))
3771 dom_bbs.safe_push (e->dest);
3772 sel_redirect_edge_and_branch (e, succ_bb);
3773 rescan_p = true;
3774 break;
3776 /* If the edge is fallthru, but PRED_BB ends in a conditional jump
3777 to BB (so there is no non-fallthru edge from PRED_BB to BB), we
3778 still have to adjust it. */
3779 else if (single_succ_p (pred_bb) && any_condjump_p (BB_END (pred_bb)))
3781 /* If possible, try to remove the unneeded conditional jump. */
3782 if (INSN_SCHED_TIMES (BB_END (pred_bb)) == 0
3783 && !IN_CURRENT_FENCE_P (BB_END (pred_bb)))
3785 if (!sel_remove_insn (BB_END (pred_bb), false, false))
3786 tidy_fallthru_edge (e);
3788 else
3789 sel_redirect_edge_and_branch (e, succ_bb);
3790 rescan_p = true;
3791 break;
3796 if (can_merge_blocks_p (bb->prev_bb, bb))
3797 sel_merge_blocks (bb->prev_bb, bb);
3798 else
3800 /* This is a block without fallthru predecessor. Just delete it. */
3801 gcc_assert (note_bb);
3802 move_bb_info (note_bb, bb);
3803 remove_empty_bb (bb, true);
3806 if (!dom_bbs.is_empty ())
3808 dom_bbs.safe_push (succ_bb);
3809 iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, false);
3810 dom_bbs.release ();
3813 return true;
3816 /* Tidy the control flow after we have removed original insn from
3817 XBB. Return true if we have removed some blocks. When FULL_TIDYING
3818 is true, also try to optimize control flow on non-empty blocks. */
3819 bool
3820 tidy_control_flow (basic_block xbb, bool full_tidying)
3822 bool changed = true;
3823 insn_t first, last;
3825 /* First check whether XBB is empty. */
3826 changed = maybe_tidy_empty_bb (xbb);
3827 if (changed || !full_tidying)
3828 return changed;
3830 /* Check if there is a unnecessary jump after insn left. */
3831 if (bb_has_removable_jump_to_p (xbb, xbb->next_bb)
3832 && INSN_SCHED_TIMES (BB_END (xbb)) == 0
3833 && !IN_CURRENT_FENCE_P (BB_END (xbb)))
3835 if (sel_remove_insn (BB_END (xbb), false, false))
3836 return true;
3837 tidy_fallthru_edge (EDGE_SUCC (xbb, 0));
3840 first = sel_bb_head (xbb);
3841 last = sel_bb_end (xbb);
3842 if (MAY_HAVE_DEBUG_INSNS)
3844 if (first != last && DEBUG_INSN_P (first))
3846 first = NEXT_INSN (first);
3847 while (first != last && (DEBUG_INSN_P (first) || NOTE_P (first)));
3849 if (first != last && DEBUG_INSN_P (last))
3851 last = PREV_INSN (last);
3852 while (first != last && (DEBUG_INSN_P (last) || NOTE_P (last)));
3854 /* Check if there is an unnecessary jump in previous basic block leading
3855 to next basic block left after removing INSN from stream.
3856 If it is so, remove that jump and redirect edge to current
3857 basic block (where there was INSN before deletion). This way
3858 when NOP will be deleted several instructions later with its
3859 basic block we will not get a jump to next instruction, which
3860 can be harmful. */
3861 if (first == last
3862 && !sel_bb_empty_p (xbb)
3863 && INSN_NOP_P (last)
3864 /* Flow goes fallthru from current block to the next. */
3865 && EDGE_COUNT (xbb->succs) == 1
3866 && (EDGE_SUCC (xbb, 0)->flags & EDGE_FALLTHRU)
3867 /* When successor is an EXIT block, it may not be the next block. */
3868 && single_succ (xbb) != EXIT_BLOCK_PTR_FOR_FN (cfun)
3869 /* And unconditional jump in previous basic block leads to
3870 next basic block of XBB and this jump can be safely removed. */
3871 && in_current_region_p (xbb->prev_bb)
3872 && bb_has_removable_jump_to_p (xbb->prev_bb, xbb->next_bb)
3873 && INSN_SCHED_TIMES (BB_END (xbb->prev_bb)) == 0
3874 /* Also this jump is not at the scheduling boundary. */
3875 && !IN_CURRENT_FENCE_P (BB_END (xbb->prev_bb)))
3877 bool recompute_toporder_p;
3878 /* Clear data structures of jump - jump itself will be removed
3879 by sel_redirect_edge_and_branch. */
3880 clear_expr (INSN_EXPR (BB_END (xbb->prev_bb)));
3881 recompute_toporder_p
3882 = sel_redirect_edge_and_branch (EDGE_SUCC (xbb->prev_bb, 0), xbb);
3884 gcc_assert (EDGE_SUCC (xbb->prev_bb, 0)->flags & EDGE_FALLTHRU);
3886 /* It can turn out that after removing unused jump, basic block
3887 that contained that jump, becomes empty too. In such case
3888 remove it too. */
3889 if (sel_bb_empty_p (xbb->prev_bb))
3890 changed = maybe_tidy_empty_bb (xbb->prev_bb);
3891 if (recompute_toporder_p)
3892 sel_recompute_toporder ();
3895 #ifdef ENABLE_CHECKING
3896 verify_backedges ();
3897 verify_dominators (CDI_DOMINATORS);
3898 #endif
3900 return changed;
3903 /* Purge meaningless empty blocks in the middle of a region. */
3904 void
3905 purge_empty_blocks (void)
3907 int i;
3909 /* Do not attempt to delete the first basic block in the region. */
3910 for (i = 1; i < current_nr_blocks; )
3912 basic_block b = BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (i));
3914 if (maybe_tidy_empty_bb (b))
3915 continue;
3917 i++;
3921 /* Rip-off INSN from the insn stream. When ONLY_DISCONNECT is true,
3922 do not delete insn's data, because it will be later re-emitted.
3923 Return true if we have removed some blocks afterwards. */
3924 bool
3925 sel_remove_insn (insn_t insn, bool only_disconnect, bool full_tidying)
3927 basic_block bb = BLOCK_FOR_INSN (insn);
3929 gcc_assert (INSN_IN_STREAM_P (insn));
3931 if (DEBUG_INSN_P (insn) && BB_AV_SET_VALID_P (bb))
3933 expr_t expr;
3934 av_set_iterator i;
3936 /* When we remove a debug insn that is head of a BB, it remains
3937 in the AV_SET of the block, but it shouldn't. */
3938 FOR_EACH_EXPR_1 (expr, i, &BB_AV_SET (bb))
3939 if (EXPR_INSN_RTX (expr) == insn)
3941 av_set_iter_remove (&i);
3942 break;
3946 if (only_disconnect)
3947 remove_insn (insn);
3948 else
3950 delete_insn (insn);
3951 clear_expr (INSN_EXPR (insn));
3954 /* It is necessary to NULL these fields in case we are going to re-insert
3955 INSN into the insns stream, as will usually happen in the ONLY_DISCONNECT
3956 case, but also for NOPs that we will return to the nop pool. */
3957 SET_PREV_INSN (insn) = NULL_RTX;
3958 SET_NEXT_INSN (insn) = NULL_RTX;
3959 set_block_for_insn (insn, NULL);
3961 return tidy_control_flow (bb, full_tidying);
3964 /* Estimate number of the insns in BB. */
3965 static int
3966 sel_estimate_number_of_insns (basic_block bb)
3968 int res = 0;
3969 insn_t insn = NEXT_INSN (BB_HEAD (bb)), next_tail = NEXT_INSN (BB_END (bb));
3971 for (; insn != next_tail; insn = NEXT_INSN (insn))
3972 if (NONDEBUG_INSN_P (insn))
3973 res++;
3975 return res;
3978 /* We don't need separate luids for notes or labels. */
3979 static int
3980 sel_luid_for_non_insn (rtx x)
3982 gcc_assert (NOTE_P (x) || LABEL_P (x));
3984 return -1;
3987 /* Find the proper seqno for inserting at INSN by successors.
3988 Return -1 if no successors with positive seqno exist. */
3989 static int
3990 get_seqno_by_succs (rtx_insn *insn)
3992 basic_block bb = BLOCK_FOR_INSN (insn);
3993 rtx_insn *tmp = insn, *end = BB_END (bb);
3994 int seqno;
3995 insn_t succ = NULL;
3996 succ_iterator si;
3998 while (tmp != end)
4000 tmp = NEXT_INSN (tmp);
4001 if (INSN_P (tmp))
4002 return INSN_SEQNO (tmp);
4005 seqno = INT_MAX;
4007 FOR_EACH_SUCC_1 (succ, si, end, SUCCS_NORMAL)
4008 if (INSN_SEQNO (succ) > 0)
4009 seqno = MIN (seqno, INSN_SEQNO (succ));
4011 if (seqno == INT_MAX)
4012 return -1;
4014 return seqno;
4017 /* Compute seqno for INSN by its preds or succs. Use OLD_SEQNO to compute
4018 seqno in corner cases. */
4019 static int
4020 get_seqno_for_a_jump (insn_t insn, int old_seqno)
4022 int seqno;
4024 gcc_assert (INSN_SIMPLEJUMP_P (insn));
4026 if (!sel_bb_head_p (insn))
4027 seqno = INSN_SEQNO (PREV_INSN (insn));
4028 else
4030 basic_block bb = BLOCK_FOR_INSN (insn);
4032 if (single_pred_p (bb)
4033 && !in_current_region_p (single_pred (bb)))
4035 /* We can have preds outside a region when splitting edges
4036 for pipelining of an outer loop. Use succ instead.
4037 There should be only one of them. */
4038 insn_t succ = NULL;
4039 succ_iterator si;
4040 bool first = true;
4042 gcc_assert (flag_sel_sched_pipelining_outer_loops
4043 && current_loop_nest);
4044 FOR_EACH_SUCC_1 (succ, si, insn,
4045 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
4047 gcc_assert (first);
4048 first = false;
4051 gcc_assert (succ != NULL);
4052 seqno = INSN_SEQNO (succ);
4054 else
4056 insn_t *preds;
4057 int n;
4059 cfg_preds (BLOCK_FOR_INSN (insn), &preds, &n);
4061 gcc_assert (n > 0);
4062 /* For one predecessor, use simple method. */
4063 if (n == 1)
4064 seqno = INSN_SEQNO (preds[0]);
4065 else
4066 seqno = get_seqno_by_preds (insn);
4068 free (preds);
4072 /* We were unable to find a good seqno among preds. */
4073 if (seqno < 0)
4074 seqno = get_seqno_by_succs (insn);
4076 if (seqno < 0)
4078 /* The only case where this could be here legally is that the only
4079 unscheduled insn was a conditional jump that got removed and turned
4080 into this unconditional one. Initialize from the old seqno
4081 of that jump passed down to here. */
4082 seqno = old_seqno;
4085 gcc_assert (seqno >= 0);
4086 return seqno;
4089 /* Find the proper seqno for inserting at INSN. Returns -1 if no predecessors
4090 with positive seqno exist. */
4092 get_seqno_by_preds (rtx_insn *insn)
4094 basic_block bb = BLOCK_FOR_INSN (insn);
4095 rtx_insn *tmp = insn, *head = BB_HEAD (bb);
4096 insn_t *preds;
4097 int n, i, seqno;
4099 while (tmp != head)
4101 tmp = PREV_INSN (tmp);
4102 if (INSN_P (tmp))
4103 return INSN_SEQNO (tmp);
4106 cfg_preds (bb, &preds, &n);
4107 for (i = 0, seqno = -1; i < n; i++)
4108 seqno = MAX (seqno, INSN_SEQNO (preds[i]));
4110 return seqno;
4115 /* Extend pass-scope data structures for basic blocks. */
4116 void
4117 sel_extend_global_bb_info (void)
4119 sel_global_bb_info.safe_grow_cleared (last_basic_block_for_fn (cfun));
4122 /* Extend region-scope data structures for basic blocks. */
4123 static void
4124 extend_region_bb_info (void)
4126 sel_region_bb_info.safe_grow_cleared (last_basic_block_for_fn (cfun));
4129 /* Extend all data structures to fit for all basic blocks. */
4130 static void
4131 extend_bb_info (void)
4133 sel_extend_global_bb_info ();
4134 extend_region_bb_info ();
4137 /* Finalize pass-scope data structures for basic blocks. */
4138 void
4139 sel_finish_global_bb_info (void)
4141 sel_global_bb_info.release ();
4144 /* Finalize region-scope data structures for basic blocks. */
4145 static void
4146 finish_region_bb_info (void)
4148 sel_region_bb_info.release ();
4152 /* Data for each insn in current region. */
4153 vec<sel_insn_data_def> s_i_d = vNULL;
4155 /* Extend data structures for insns from current region. */
4156 static void
4157 extend_insn_data (void)
4159 int reserve;
4161 sched_extend_target ();
4162 sched_deps_init (false);
4164 /* Extend data structures for insns from current region. */
4165 reserve = (sched_max_luid + 1 - s_i_d.length ());
4166 if (reserve > 0 && ! s_i_d.space (reserve))
4168 int size;
4170 if (sched_max_luid / 2 > 1024)
4171 size = sched_max_luid + 1024;
4172 else
4173 size = 3 * sched_max_luid / 2;
4176 s_i_d.safe_grow_cleared (size);
4180 /* Finalize data structures for insns from current region. */
4181 static void
4182 finish_insns (void)
4184 unsigned i;
4186 /* Clear here all dependence contexts that may have left from insns that were
4187 removed during the scheduling. */
4188 for (i = 0; i < s_i_d.length (); i++)
4190 sel_insn_data_def *sid_entry = &s_i_d[i];
4192 if (sid_entry->live)
4193 return_regset_to_pool (sid_entry->live);
4194 if (sid_entry->analyzed_deps)
4196 BITMAP_FREE (sid_entry->analyzed_deps);
4197 BITMAP_FREE (sid_entry->found_deps);
4198 htab_delete (sid_entry->transformed_insns);
4199 free_deps (&sid_entry->deps_context);
4201 if (EXPR_VINSN (&sid_entry->expr))
4203 clear_expr (&sid_entry->expr);
4205 /* Also, clear CANT_MOVE bit here, because we really don't want it
4206 to be passed to the next region. */
4207 CANT_MOVE_BY_LUID (i) = 0;
4211 s_i_d.release ();
4214 /* A proxy to pass initialization data to init_insn (). */
4215 static sel_insn_data_def _insn_init_ssid;
4216 static sel_insn_data_t insn_init_ssid = &_insn_init_ssid;
4218 /* If true create a new vinsn. Otherwise use the one from EXPR. */
4219 static bool insn_init_create_new_vinsn_p;
4221 /* Set all necessary data for initialization of the new insn[s]. */
4222 static expr_t
4223 set_insn_init (expr_t expr, vinsn_t vi, int seqno)
4225 expr_t x = &insn_init_ssid->expr;
4227 copy_expr_onside (x, expr);
4228 if (vi != NULL)
4230 insn_init_create_new_vinsn_p = false;
4231 change_vinsn_in_expr (x, vi);
4233 else
4234 insn_init_create_new_vinsn_p = true;
4236 insn_init_ssid->seqno = seqno;
4237 return x;
4240 /* Init data for INSN. */
4241 static void
4242 init_insn_data (insn_t insn)
4244 expr_t expr;
4245 sel_insn_data_t ssid = insn_init_ssid;
4247 /* The fields mentioned below are special and hence are not being
4248 propagated to the new insns. */
4249 gcc_assert (!ssid->asm_p && ssid->sched_next == NULL
4250 && !ssid->after_stall_p && ssid->sched_cycle == 0);
4251 gcc_assert (INSN_P (insn) && INSN_LUID (insn) > 0);
4253 expr = INSN_EXPR (insn);
4254 copy_expr (expr, &ssid->expr);
4255 prepare_insn_expr (insn, ssid->seqno);
4257 if (insn_init_create_new_vinsn_p)
4258 change_vinsn_in_expr (expr, vinsn_create (insn, init_insn_force_unique_p));
4260 if (first_time_insn_init (insn))
4261 init_first_time_insn_data (insn);
4264 /* This is used to initialize spurious jumps generated by
4265 sel_redirect_edge (). OLD_SEQNO is used for initializing seqnos
4266 in corner cases within get_seqno_for_a_jump. */
4267 static void
4268 init_simplejump_data (insn_t insn, int old_seqno)
4270 init_expr (INSN_EXPR (insn), vinsn_create (insn, false), 0,
4271 REG_BR_PROB_BASE, 0, 0, 0, 0, 0, 0,
4272 vNULL, true, false, false,
4273 false, true);
4274 INSN_SEQNO (insn) = get_seqno_for_a_jump (insn, old_seqno);
4275 init_first_time_insn_data (insn);
4278 /* Perform deferred initialization of insns. This is used to process
4279 a new jump that may be created by redirect_edge. OLD_SEQNO is used
4280 for initializing simplejumps in init_simplejump_data. */
4281 static void
4282 sel_init_new_insn (insn_t insn, int flags, int old_seqno)
4284 /* We create data structures for bb when the first insn is emitted in it. */
4285 if (INSN_P (insn)
4286 && INSN_IN_STREAM_P (insn)
4287 && insn_is_the_only_one_in_bb_p (insn))
4289 extend_bb_info ();
4290 create_initial_data_sets (BLOCK_FOR_INSN (insn));
4293 if (flags & INSN_INIT_TODO_LUID)
4295 sched_extend_luids ();
4296 sched_init_insn_luid (insn);
4299 if (flags & INSN_INIT_TODO_SSID)
4301 extend_insn_data ();
4302 init_insn_data (insn);
4303 clear_expr (&insn_init_ssid->expr);
4306 if (flags & INSN_INIT_TODO_SIMPLEJUMP)
4308 extend_insn_data ();
4309 init_simplejump_data (insn, old_seqno);
4312 gcc_assert (CONTAINING_RGN (BLOCK_NUM (insn))
4313 == CONTAINING_RGN (BB_TO_BLOCK (0)));
4317 /* Functions to init/finish work with lv sets. */
4319 /* Init BB_LV_SET of BB from DF_LR_IN set of BB. */
4320 static void
4321 init_lv_set (basic_block bb)
4323 gcc_assert (!BB_LV_SET_VALID_P (bb));
4325 BB_LV_SET (bb) = get_regset_from_pool ();
4326 COPY_REG_SET (BB_LV_SET (bb), DF_LR_IN (bb));
4327 BB_LV_SET_VALID_P (bb) = true;
4330 /* Copy liveness information to BB from FROM_BB. */
4331 static void
4332 copy_lv_set_from (basic_block bb, basic_block from_bb)
4334 gcc_assert (!BB_LV_SET_VALID_P (bb));
4336 COPY_REG_SET (BB_LV_SET (bb), BB_LV_SET (from_bb));
4337 BB_LV_SET_VALID_P (bb) = true;
4340 /* Initialize lv set of all bb headers. */
4341 void
4342 init_lv_sets (void)
4344 basic_block bb;
4346 /* Initialize of LV sets. */
4347 FOR_EACH_BB_FN (bb, cfun)
4348 init_lv_set (bb);
4350 /* Don't forget EXIT_BLOCK. */
4351 init_lv_set (EXIT_BLOCK_PTR_FOR_FN (cfun));
4354 /* Release lv set of HEAD. */
4355 static void
4356 free_lv_set (basic_block bb)
4358 gcc_assert (BB_LV_SET (bb) != NULL);
4360 return_regset_to_pool (BB_LV_SET (bb));
4361 BB_LV_SET (bb) = NULL;
4362 BB_LV_SET_VALID_P (bb) = false;
4365 /* Finalize lv sets of all bb headers. */
4366 void
4367 free_lv_sets (void)
4369 basic_block bb;
4371 /* Don't forget EXIT_BLOCK. */
4372 free_lv_set (EXIT_BLOCK_PTR_FOR_FN (cfun));
4374 /* Free LV sets. */
4375 FOR_EACH_BB_FN (bb, cfun)
4376 if (BB_LV_SET (bb))
4377 free_lv_set (bb);
4380 /* Mark AV_SET for BB as invalid, so this set will be updated the next time
4381 compute_av() processes BB. This function is called when creating new basic
4382 blocks, as well as for blocks (either new or existing) where new jumps are
4383 created when the control flow is being updated. */
4384 static void
4385 invalidate_av_set (basic_block bb)
4387 BB_AV_LEVEL (bb) = -1;
4390 /* Create initial data sets for BB (they will be invalid). */
4391 static void
4392 create_initial_data_sets (basic_block bb)
4394 if (BB_LV_SET (bb))
4395 BB_LV_SET_VALID_P (bb) = false;
4396 else
4397 BB_LV_SET (bb) = get_regset_from_pool ();
4398 invalidate_av_set (bb);
4401 /* Free av set of BB. */
4402 static void
4403 free_av_set (basic_block bb)
4405 av_set_clear (&BB_AV_SET (bb));
4406 BB_AV_LEVEL (bb) = 0;
4409 /* Free data sets of BB. */
4410 void
4411 free_data_sets (basic_block bb)
4413 free_lv_set (bb);
4414 free_av_set (bb);
4417 /* Exchange data sets of TO and FROM. */
4418 void
4419 exchange_data_sets (basic_block to, basic_block from)
4421 /* Exchange lv sets of TO and FROM. */
4422 std::swap (BB_LV_SET (from), BB_LV_SET (to));
4423 std::swap (BB_LV_SET_VALID_P (from), BB_LV_SET_VALID_P (to));
4425 /* Exchange av sets of TO and FROM. */
4426 std::swap (BB_AV_SET (from), BB_AV_SET (to));
4427 std::swap (BB_AV_LEVEL (from), BB_AV_LEVEL (to));
4430 /* Copy data sets of FROM to TO. */
4431 void
4432 copy_data_sets (basic_block to, basic_block from)
4434 gcc_assert (!BB_LV_SET_VALID_P (to) && !BB_AV_SET_VALID_P (to));
4435 gcc_assert (BB_AV_SET (to) == NULL);
4437 BB_AV_LEVEL (to) = BB_AV_LEVEL (from);
4438 BB_LV_SET_VALID_P (to) = BB_LV_SET_VALID_P (from);
4440 if (BB_AV_SET_VALID_P (from))
4442 BB_AV_SET (to) = av_set_copy (BB_AV_SET (from));
4444 if (BB_LV_SET_VALID_P (from))
4446 gcc_assert (BB_LV_SET (to) != NULL);
4447 COPY_REG_SET (BB_LV_SET (to), BB_LV_SET (from));
4451 /* Return an av set for INSN, if any. */
4452 av_set_t
4453 get_av_set (insn_t insn)
4455 av_set_t av_set;
4457 gcc_assert (AV_SET_VALID_P (insn));
4459 if (sel_bb_head_p (insn))
4460 av_set = BB_AV_SET (BLOCK_FOR_INSN (insn));
4461 else
4462 av_set = NULL;
4464 return av_set;
4467 /* Implementation of AV_LEVEL () macro. Return AV_LEVEL () of INSN. */
4469 get_av_level (insn_t insn)
4471 int av_level;
4473 gcc_assert (INSN_P (insn));
4475 if (sel_bb_head_p (insn))
4476 av_level = BB_AV_LEVEL (BLOCK_FOR_INSN (insn));
4477 else
4478 av_level = INSN_WS_LEVEL (insn);
4480 return av_level;
4485 /* Variables to work with control-flow graph. */
4487 /* The basic block that already has been processed by the sched_data_update (),
4488 but hasn't been in sel_add_bb () yet. */
4489 static vec<basic_block>
4490 last_added_blocks = vNULL;
4492 /* A pool for allocating successor infos. */
4493 static struct
4495 /* A stack for saving succs_info structures. */
4496 struct succs_info *stack;
4498 /* Its size. */
4499 int size;
4501 /* Top of the stack. */
4502 int top;
4504 /* Maximal value of the top. */
4505 int max_top;
4506 } succs_info_pool;
4508 /* Functions to work with control-flow graph. */
4510 /* Return basic block note of BB. */
4511 rtx_insn *
4512 sel_bb_head (basic_block bb)
4514 rtx_insn *head;
4516 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
4518 gcc_assert (exit_insn != NULL_RTX);
4519 head = exit_insn;
4521 else
4523 rtx_note *note = bb_note (bb);
4524 head = next_nonnote_insn (note);
4526 if (head && (BARRIER_P (head) || BLOCK_FOR_INSN (head) != bb))
4527 head = NULL;
4530 return head;
4533 /* Return true if INSN is a basic block header. */
4534 bool
4535 sel_bb_head_p (insn_t insn)
4537 return sel_bb_head (BLOCK_FOR_INSN (insn)) == insn;
4540 /* Return last insn of BB. */
4541 rtx_insn *
4542 sel_bb_end (basic_block bb)
4544 if (sel_bb_empty_p (bb))
4545 return NULL;
4547 gcc_assert (bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
4549 return BB_END (bb);
4552 /* Return true if INSN is the last insn in its basic block. */
4553 bool
4554 sel_bb_end_p (insn_t insn)
4556 return insn == sel_bb_end (BLOCK_FOR_INSN (insn));
4559 /* Return true if BB consist of single NOTE_INSN_BASIC_BLOCK. */
4560 bool
4561 sel_bb_empty_p (basic_block bb)
4563 return sel_bb_head (bb) == NULL;
4566 /* True when BB belongs to the current scheduling region. */
4567 bool
4568 in_current_region_p (basic_block bb)
4570 if (bb->index < NUM_FIXED_BLOCKS)
4571 return false;
4573 return CONTAINING_RGN (bb->index) == CONTAINING_RGN (BB_TO_BLOCK (0));
4576 /* Return the block which is a fallthru bb of a conditional jump JUMP. */
4577 basic_block
4578 fallthru_bb_of_jump (const rtx_insn *jump)
4580 if (!JUMP_P (jump))
4581 return NULL;
4583 if (!any_condjump_p (jump))
4584 return NULL;
4586 /* A basic block that ends with a conditional jump may still have one successor
4587 (and be followed by a barrier), we are not interested. */
4588 if (single_succ_p (BLOCK_FOR_INSN (jump)))
4589 return NULL;
4591 return FALLTHRU_EDGE (BLOCK_FOR_INSN (jump))->dest;
4594 /* Remove all notes from BB. */
4595 static void
4596 init_bb (basic_block bb)
4598 remove_notes (bb_note (bb), BB_END (bb));
4599 BB_NOTE_LIST (bb) = note_list;
4602 void
4603 sel_init_bbs (bb_vec_t bbs)
4605 const struct sched_scan_info_def ssi =
4607 extend_bb_info, /* extend_bb */
4608 init_bb, /* init_bb */
4609 NULL, /* extend_insn */
4610 NULL /* init_insn */
4613 sched_scan (&ssi, bbs);
4616 /* Restore notes for the whole region. */
4617 static void
4618 sel_restore_notes (void)
4620 int bb;
4621 insn_t insn;
4623 for (bb = 0; bb < current_nr_blocks; bb++)
4625 basic_block first, last;
4627 first = EBB_FIRST_BB (bb);
4628 last = EBB_LAST_BB (bb)->next_bb;
4632 note_list = BB_NOTE_LIST (first);
4633 restore_other_notes (NULL, first);
4634 BB_NOTE_LIST (first) = NULL;
4636 FOR_BB_INSNS (first, insn)
4637 if (NONDEBUG_INSN_P (insn))
4638 reemit_notes (insn);
4640 first = first->next_bb;
4642 while (first != last);
4646 /* Free per-bb data structures. */
4647 void
4648 sel_finish_bbs (void)
4650 sel_restore_notes ();
4652 /* Remove current loop preheader from this loop. */
4653 if (current_loop_nest)
4654 sel_remove_loop_preheader ();
4656 finish_region_bb_info ();
4659 /* Return true if INSN has a single successor of type FLAGS. */
4660 bool
4661 sel_insn_has_single_succ_p (insn_t insn, int flags)
4663 insn_t succ;
4664 succ_iterator si;
4665 bool first_p = true;
4667 FOR_EACH_SUCC_1 (succ, si, insn, flags)
4669 if (first_p)
4670 first_p = false;
4671 else
4672 return false;
4675 return true;
4678 /* Allocate successor's info. */
4679 static struct succs_info *
4680 alloc_succs_info (void)
4682 if (succs_info_pool.top == succs_info_pool.max_top)
4684 int i;
4686 if (++succs_info_pool.max_top >= succs_info_pool.size)
4687 gcc_unreachable ();
4689 i = ++succs_info_pool.top;
4690 succs_info_pool.stack[i].succs_ok.create (10);
4691 succs_info_pool.stack[i].succs_other.create (10);
4692 succs_info_pool.stack[i].probs_ok.create (10);
4694 else
4695 succs_info_pool.top++;
4697 return &succs_info_pool.stack[succs_info_pool.top];
4700 /* Free successor's info. */
4701 void
4702 free_succs_info (struct succs_info * sinfo)
4704 gcc_assert (succs_info_pool.top >= 0
4705 && &succs_info_pool.stack[succs_info_pool.top] == sinfo);
4706 succs_info_pool.top--;
4708 /* Clear stale info. */
4709 sinfo->succs_ok.block_remove (0, sinfo->succs_ok.length ());
4710 sinfo->succs_other.block_remove (0, sinfo->succs_other.length ());
4711 sinfo->probs_ok.block_remove (0, sinfo->probs_ok.length ());
4712 sinfo->all_prob = 0;
4713 sinfo->succs_ok_n = 0;
4714 sinfo->all_succs_n = 0;
4717 /* Compute successor info for INSN. FLAGS are the flags passed
4718 to the FOR_EACH_SUCC_1 iterator. */
4719 struct succs_info *
4720 compute_succs_info (insn_t insn, short flags)
4722 succ_iterator si;
4723 insn_t succ;
4724 struct succs_info *sinfo = alloc_succs_info ();
4726 /* Traverse *all* successors and decide what to do with each. */
4727 FOR_EACH_SUCC_1 (succ, si, insn, SUCCS_ALL)
4729 /* FIXME: this doesn't work for skipping to loop exits, as we don't
4730 perform code motion through inner loops. */
4731 short current_flags = si.current_flags & ~SUCCS_SKIP_TO_LOOP_EXITS;
4733 if (current_flags & flags)
4735 sinfo->succs_ok.safe_push (succ);
4736 sinfo->probs_ok.safe_push (
4737 /* FIXME: Improve calculation when skipping
4738 inner loop to exits. */
4739 si.bb_end ? si.e1->probability : REG_BR_PROB_BASE);
4740 sinfo->succs_ok_n++;
4742 else
4743 sinfo->succs_other.safe_push (succ);
4745 /* Compute all_prob. */
4746 if (!si.bb_end)
4747 sinfo->all_prob = REG_BR_PROB_BASE;
4748 else
4749 sinfo->all_prob += si.e1->probability;
4751 sinfo->all_succs_n++;
4754 return sinfo;
4757 /* Return the predecessors of BB in PREDS and their number in N.
4758 Empty blocks are skipped. SIZE is used to allocate PREDS. */
4759 static void
4760 cfg_preds_1 (basic_block bb, insn_t **preds, int *n, int *size)
4762 edge e;
4763 edge_iterator ei;
4765 gcc_assert (BLOCK_TO_BB (bb->index) != 0);
4767 FOR_EACH_EDGE (e, ei, bb->preds)
4769 basic_block pred_bb = e->src;
4770 insn_t bb_end = BB_END (pred_bb);
4772 if (!in_current_region_p (pred_bb))
4774 gcc_assert (flag_sel_sched_pipelining_outer_loops
4775 && current_loop_nest);
4776 continue;
4779 if (sel_bb_empty_p (pred_bb))
4780 cfg_preds_1 (pred_bb, preds, n, size);
4781 else
4783 if (*n == *size)
4784 *preds = XRESIZEVEC (insn_t, *preds,
4785 (*size = 2 * *size + 1));
4786 (*preds)[(*n)++] = bb_end;
4790 gcc_assert (*n != 0
4791 || (flag_sel_sched_pipelining_outer_loops
4792 && current_loop_nest));
4795 /* Find all predecessors of BB and record them in PREDS and their number
4796 in N. Empty blocks are skipped, and only normal (forward in-region)
4797 edges are processed. */
4798 static void
4799 cfg_preds (basic_block bb, insn_t **preds, int *n)
4801 int size = 0;
4803 *preds = NULL;
4804 *n = 0;
4805 cfg_preds_1 (bb, preds, n, &size);
4808 /* Returns true if we are moving INSN through join point. */
4809 bool
4810 sel_num_cfg_preds_gt_1 (insn_t insn)
4812 basic_block bb;
4814 if (!sel_bb_head_p (insn) || INSN_BB (insn) == 0)
4815 return false;
4817 bb = BLOCK_FOR_INSN (insn);
4819 while (1)
4821 if (EDGE_COUNT (bb->preds) > 1)
4822 return true;
4824 gcc_assert (EDGE_PRED (bb, 0)->dest == bb);
4825 bb = EDGE_PRED (bb, 0)->src;
4827 if (!sel_bb_empty_p (bb))
4828 break;
4831 return false;
4834 /* Returns true when BB should be the end of an ebb. Adapted from the
4835 code in sched-ebb.c. */
4836 bool
4837 bb_ends_ebb_p (basic_block bb)
4839 basic_block next_bb = bb_next_bb (bb);
4840 edge e;
4842 if (next_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
4843 || bitmap_bit_p (forced_ebb_heads, next_bb->index)
4844 || (LABEL_P (BB_HEAD (next_bb))
4845 /* NB: LABEL_NUSES () is not maintained outside of jump.c.
4846 Work around that. */
4847 && !single_pred_p (next_bb)))
4848 return true;
4850 if (!in_current_region_p (next_bb))
4851 return true;
4853 e = find_fallthru_edge (bb->succs);
4854 if (e)
4856 gcc_assert (e->dest == next_bb);
4858 return false;
4861 return true;
4864 /* Returns true when INSN and SUCC are in the same EBB, given that SUCC is a
4865 successor of INSN. */
4866 bool
4867 in_same_ebb_p (insn_t insn, insn_t succ)
4869 basic_block ptr = BLOCK_FOR_INSN (insn);
4871 for (;;)
4873 if (ptr == BLOCK_FOR_INSN (succ))
4874 return true;
4876 if (bb_ends_ebb_p (ptr))
4877 return false;
4879 ptr = bb_next_bb (ptr);
4882 gcc_unreachable ();
4883 return false;
4886 /* Recomputes the reverse topological order for the function and
4887 saves it in REV_TOP_ORDER_INDEX. REV_TOP_ORDER_INDEX_LEN is also
4888 modified appropriately. */
4889 static void
4890 recompute_rev_top_order (void)
4892 int *postorder;
4893 int n_blocks, i;
4895 if (!rev_top_order_index
4896 || rev_top_order_index_len < last_basic_block_for_fn (cfun))
4898 rev_top_order_index_len = last_basic_block_for_fn (cfun);
4899 rev_top_order_index = XRESIZEVEC (int, rev_top_order_index,
4900 rev_top_order_index_len);
4903 postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
4905 n_blocks = post_order_compute (postorder, true, false);
4906 gcc_assert (n_basic_blocks_for_fn (cfun) == n_blocks);
4908 /* Build reverse function: for each basic block with BB->INDEX == K
4909 rev_top_order_index[K] is it's reverse topological sort number. */
4910 for (i = 0; i < n_blocks; i++)
4912 gcc_assert (postorder[i] < rev_top_order_index_len);
4913 rev_top_order_index[postorder[i]] = i;
4916 free (postorder);
4919 /* Clear all flags from insns in BB that could spoil its rescheduling. */
4920 void
4921 clear_outdated_rtx_info (basic_block bb)
4923 rtx_insn *insn;
4925 FOR_BB_INSNS (bb, insn)
4926 if (INSN_P (insn))
4928 SCHED_GROUP_P (insn) = 0;
4929 INSN_AFTER_STALL_P (insn) = 0;
4930 INSN_SCHED_TIMES (insn) = 0;
4931 EXPR_PRIORITY_ADJ (INSN_EXPR (insn)) = 0;
4933 /* We cannot use the changed caches, as previously we could ignore
4934 the LHS dependence due to enabled renaming and transform
4935 the expression, and currently we'll be unable to do this. */
4936 htab_empty (INSN_TRANSFORMED_INSNS (insn));
4940 /* Add BB_NOTE to the pool of available basic block notes. */
4941 static void
4942 return_bb_to_pool (basic_block bb)
4944 rtx_note *note = bb_note (bb);
4946 gcc_assert (NOTE_BASIC_BLOCK (note) == bb
4947 && bb->aux == NULL);
4949 /* It turns out that current cfg infrastructure does not support
4950 reuse of basic blocks. Don't bother for now. */
4951 /*bb_note_pool.safe_push (note);*/
4954 /* Get a bb_note from pool or return NULL_RTX if pool is empty. */
4955 static rtx_note *
4956 get_bb_note_from_pool (void)
4958 if (bb_note_pool.is_empty ())
4959 return NULL;
4960 else
4962 rtx_note *note = bb_note_pool.pop ();
4964 SET_PREV_INSN (note) = NULL_RTX;
4965 SET_NEXT_INSN (note) = NULL_RTX;
4967 return note;
4971 /* Free bb_note_pool. */
4972 void
4973 free_bb_note_pool (void)
4975 bb_note_pool.release ();
4978 /* Setup scheduler pool and successor structure. */
4979 void
4980 alloc_sched_pools (void)
4982 int succs_size;
4984 succs_size = MAX_WS + 1;
4985 succs_info_pool.stack = XCNEWVEC (struct succs_info, succs_size);
4986 succs_info_pool.size = succs_size;
4987 succs_info_pool.top = -1;
4988 succs_info_pool.max_top = -1;
4991 /* Free the pools. */
4992 void
4993 free_sched_pools (void)
4995 int i;
4997 sched_lists_pool.release ();
4998 gcc_assert (succs_info_pool.top == -1);
4999 for (i = 0; i <= succs_info_pool.max_top; i++)
5001 succs_info_pool.stack[i].succs_ok.release ();
5002 succs_info_pool.stack[i].succs_other.release ();
5003 succs_info_pool.stack[i].probs_ok.release ();
5005 free (succs_info_pool.stack);
5009 /* Returns a position in RGN where BB can be inserted retaining
5010 topological order. */
5011 static int
5012 find_place_to_insert_bb (basic_block bb, int rgn)
5014 bool has_preds_outside_rgn = false;
5015 edge e;
5016 edge_iterator ei;
5018 /* Find whether we have preds outside the region. */
5019 FOR_EACH_EDGE (e, ei, bb->preds)
5020 if (!in_current_region_p (e->src))
5022 has_preds_outside_rgn = true;
5023 break;
5026 /* Recompute the top order -- needed when we have > 1 pred
5027 and in case we don't have preds outside. */
5028 if (flag_sel_sched_pipelining_outer_loops
5029 && (has_preds_outside_rgn || EDGE_COUNT (bb->preds) > 1))
5031 int i, bbi = bb->index, cur_bbi;
5033 recompute_rev_top_order ();
5034 for (i = RGN_NR_BLOCKS (rgn) - 1; i >= 0; i--)
5036 cur_bbi = BB_TO_BLOCK (i);
5037 if (rev_top_order_index[bbi]
5038 < rev_top_order_index[cur_bbi])
5039 break;
5042 /* We skipped the right block, so we increase i. We accommodate
5043 it for increasing by step later, so we decrease i. */
5044 return (i + 1) - 1;
5046 else if (has_preds_outside_rgn)
5048 /* This is the case when we generate an extra empty block
5049 to serve as region head during pipelining. */
5050 e = EDGE_SUCC (bb, 0);
5051 gcc_assert (EDGE_COUNT (bb->succs) == 1
5052 && in_current_region_p (EDGE_SUCC (bb, 0)->dest)
5053 && (BLOCK_TO_BB (e->dest->index) == 0));
5054 return -1;
5057 /* We don't have preds outside the region. We should have
5058 the only pred, because the multiple preds case comes from
5059 the pipelining of outer loops, and that is handled above.
5060 Just take the bbi of this single pred. */
5061 if (EDGE_COUNT (bb->succs) > 0)
5063 int pred_bbi;
5065 gcc_assert (EDGE_COUNT (bb->preds) == 1);
5067 pred_bbi = EDGE_PRED (bb, 0)->src->index;
5068 return BLOCK_TO_BB (pred_bbi);
5070 else
5071 /* BB has no successors. It is safe to put it in the end. */
5072 return current_nr_blocks - 1;
5075 /* Deletes an empty basic block freeing its data. */
5076 static void
5077 delete_and_free_basic_block (basic_block bb)
5079 gcc_assert (sel_bb_empty_p (bb));
5081 if (BB_LV_SET (bb))
5082 free_lv_set (bb);
5084 bitmap_clear_bit (blocks_to_reschedule, bb->index);
5086 /* Can't assert av_set properties because we use sel_aremove_bb
5087 when removing loop preheader from the region. At the point of
5088 removing the preheader we already have deallocated sel_region_bb_info. */
5089 gcc_assert (BB_LV_SET (bb) == NULL
5090 && !BB_LV_SET_VALID_P (bb)
5091 && BB_AV_LEVEL (bb) == 0
5092 && BB_AV_SET (bb) == NULL);
5094 delete_basic_block (bb);
5097 /* Add BB to the current region and update the region data. */
5098 static void
5099 add_block_to_current_region (basic_block bb)
5101 int i, pos, bbi = -2, rgn;
5103 rgn = CONTAINING_RGN (BB_TO_BLOCK (0));
5104 bbi = find_place_to_insert_bb (bb, rgn);
5105 bbi += 1;
5106 pos = RGN_BLOCKS (rgn) + bbi;
5108 gcc_assert (RGN_HAS_REAL_EBB (rgn) == 0
5109 && ebb_head[bbi] == pos);
5111 /* Make a place for the new block. */
5112 extend_regions ();
5114 for (i = RGN_BLOCKS (rgn + 1) - 1; i >= pos; i--)
5115 BLOCK_TO_BB (rgn_bb_table[i])++;
5117 memmove (rgn_bb_table + pos + 1,
5118 rgn_bb_table + pos,
5119 (RGN_BLOCKS (nr_regions) - pos) * sizeof (*rgn_bb_table));
5121 /* Initialize data for BB. */
5122 rgn_bb_table[pos] = bb->index;
5123 BLOCK_TO_BB (bb->index) = bbi;
5124 CONTAINING_RGN (bb->index) = rgn;
5126 RGN_NR_BLOCKS (rgn)++;
5128 for (i = rgn + 1; i <= nr_regions; i++)
5129 RGN_BLOCKS (i)++;
5132 /* Remove BB from the current region and update the region data. */
5133 static void
5134 remove_bb_from_region (basic_block bb)
5136 int i, pos, bbi = -2, rgn;
5138 rgn = CONTAINING_RGN (BB_TO_BLOCK (0));
5139 bbi = BLOCK_TO_BB (bb->index);
5140 pos = RGN_BLOCKS (rgn) + bbi;
5142 gcc_assert (RGN_HAS_REAL_EBB (rgn) == 0
5143 && ebb_head[bbi] == pos);
5145 for (i = RGN_BLOCKS (rgn + 1) - 1; i >= pos; i--)
5146 BLOCK_TO_BB (rgn_bb_table[i])--;
5148 memmove (rgn_bb_table + pos,
5149 rgn_bb_table + pos + 1,
5150 (RGN_BLOCKS (nr_regions) - pos) * sizeof (*rgn_bb_table));
5152 RGN_NR_BLOCKS (rgn)--;
5153 for (i = rgn + 1; i <= nr_regions; i++)
5154 RGN_BLOCKS (i)--;
5157 /* Add BB to the current region and update all data. If BB is NULL, add all
5158 blocks from last_added_blocks vector. */
5159 static void
5160 sel_add_bb (basic_block bb)
5162 /* Extend luids so that new notes will receive zero luids. */
5163 sched_extend_luids ();
5164 sched_init_bbs ();
5165 sel_init_bbs (last_added_blocks);
5167 /* When bb is passed explicitly, the vector should contain
5168 the only element that equals to bb; otherwise, the vector
5169 should not be NULL. */
5170 gcc_assert (last_added_blocks.exists ());
5172 if (bb != NULL)
5174 gcc_assert (last_added_blocks.length () == 1
5175 && last_added_blocks[0] == bb);
5176 add_block_to_current_region (bb);
5178 /* We associate creating/deleting data sets with the first insn
5179 appearing / disappearing in the bb. */
5180 if (!sel_bb_empty_p (bb) && BB_LV_SET (bb) == NULL)
5181 create_initial_data_sets (bb);
5183 last_added_blocks.release ();
5185 else
5186 /* BB is NULL - process LAST_ADDED_BLOCKS instead. */
5188 int i;
5189 basic_block temp_bb = NULL;
5191 for (i = 0;
5192 last_added_blocks.iterate (i, &bb); i++)
5194 add_block_to_current_region (bb);
5195 temp_bb = bb;
5198 /* We need to fetch at least one bb so we know the region
5199 to update. */
5200 gcc_assert (temp_bb != NULL);
5201 bb = temp_bb;
5203 last_added_blocks.release ();
5206 rgn_setup_region (CONTAINING_RGN (bb->index));
5209 /* Remove BB from the current region and update all data.
5210 If REMOVE_FROM_CFG_PBB is true, also remove the block cfom cfg. */
5211 static void
5212 sel_remove_bb (basic_block bb, bool remove_from_cfg_p)
5214 unsigned idx = bb->index;
5216 gcc_assert (bb != NULL && BB_NOTE_LIST (bb) == NULL_RTX);
5218 remove_bb_from_region (bb);
5219 return_bb_to_pool (bb);
5220 bitmap_clear_bit (blocks_to_reschedule, idx);
5222 if (remove_from_cfg_p)
5224 basic_block succ = single_succ (bb);
5225 delete_and_free_basic_block (bb);
5226 set_immediate_dominator (CDI_DOMINATORS, succ,
5227 recompute_dominator (CDI_DOMINATORS, succ));
5230 rgn_setup_region (CONTAINING_RGN (idx));
5233 /* Concatenate info of EMPTY_BB to info of MERGE_BB. */
5234 static void
5235 move_bb_info (basic_block merge_bb, basic_block empty_bb)
5237 if (in_current_region_p (merge_bb))
5238 concat_note_lists (BB_NOTE_LIST (empty_bb),
5239 &BB_NOTE_LIST (merge_bb));
5240 BB_NOTE_LIST (empty_bb) = NULL;
5244 /* Remove EMPTY_BB. If REMOVE_FROM_CFG_P is false, remove EMPTY_BB from
5245 region, but keep it in CFG. */
5246 static void
5247 remove_empty_bb (basic_block empty_bb, bool remove_from_cfg_p)
5249 /* The block should contain just a note or a label.
5250 We try to check whether it is unused below. */
5251 gcc_assert (BB_HEAD (empty_bb) == BB_END (empty_bb)
5252 || LABEL_P (BB_HEAD (empty_bb)));
5254 /* If basic block has predecessors or successors, redirect them. */
5255 if (remove_from_cfg_p
5256 && (EDGE_COUNT (empty_bb->preds) > 0
5257 || EDGE_COUNT (empty_bb->succs) > 0))
5259 basic_block pred;
5260 basic_block succ;
5262 /* We need to init PRED and SUCC before redirecting edges. */
5263 if (EDGE_COUNT (empty_bb->preds) > 0)
5265 edge e;
5267 gcc_assert (EDGE_COUNT (empty_bb->preds) == 1);
5269 e = EDGE_PRED (empty_bb, 0);
5270 gcc_assert (e->src == empty_bb->prev_bb
5271 && (e->flags & EDGE_FALLTHRU));
5273 pred = empty_bb->prev_bb;
5275 else
5276 pred = NULL;
5278 if (EDGE_COUNT (empty_bb->succs) > 0)
5280 /* We do not check fallthruness here as above, because
5281 after removing a jump the edge may actually be not fallthru. */
5282 gcc_assert (EDGE_COUNT (empty_bb->succs) == 1);
5283 succ = EDGE_SUCC (empty_bb, 0)->dest;
5285 else
5286 succ = NULL;
5288 if (EDGE_COUNT (empty_bb->preds) > 0 && succ != NULL)
5290 edge e = EDGE_PRED (empty_bb, 0);
5292 if (e->flags & EDGE_FALLTHRU)
5293 redirect_edge_succ_nodup (e, succ);
5294 else
5295 sel_redirect_edge_and_branch (EDGE_PRED (empty_bb, 0), succ);
5298 if (EDGE_COUNT (empty_bb->succs) > 0 && pred != NULL)
5300 edge e = EDGE_SUCC (empty_bb, 0);
5302 if (find_edge (pred, e->dest) == NULL)
5303 redirect_edge_pred (e, pred);
5307 /* Finish removing. */
5308 sel_remove_bb (empty_bb, remove_from_cfg_p);
5311 /* An implementation of create_basic_block hook, which additionally updates
5312 per-bb data structures. */
5313 static basic_block
5314 sel_create_basic_block (void *headp, void *endp, basic_block after)
5316 basic_block new_bb;
5317 rtx_note *new_bb_note;
5319 gcc_assert (flag_sel_sched_pipelining_outer_loops
5320 || !last_added_blocks.exists ());
5322 new_bb_note = get_bb_note_from_pool ();
5324 if (new_bb_note == NULL_RTX)
5325 new_bb = orig_cfg_hooks.create_basic_block (headp, endp, after);
5326 else
5328 new_bb = create_basic_block_structure ((rtx_insn *) headp,
5329 (rtx_insn *) endp,
5330 new_bb_note, after);
5331 new_bb->aux = NULL;
5334 last_added_blocks.safe_push (new_bb);
5336 return new_bb;
5339 /* Implement sched_init_only_bb (). */
5340 static void
5341 sel_init_only_bb (basic_block bb, basic_block after)
5343 gcc_assert (after == NULL);
5345 extend_regions ();
5346 rgn_make_new_region_out_of_new_block (bb);
5349 /* Update the latch when we've splitted or merged it from FROM block to TO.
5350 This should be checked for all outer loops, too. */
5351 static void
5352 change_loops_latches (basic_block from, basic_block to)
5354 gcc_assert (from != to);
5356 if (current_loop_nest)
5358 struct loop *loop;
5360 for (loop = current_loop_nest; loop; loop = loop_outer (loop))
5361 if (considered_for_pipelining_p (loop) && loop->latch == from)
5363 gcc_assert (loop == current_loop_nest);
5364 loop->latch = to;
5365 gcc_assert (loop_latch_edge (loop));
5370 /* Splits BB on two basic blocks, adding it to the region and extending
5371 per-bb data structures. Returns the newly created bb. */
5372 static basic_block
5373 sel_split_block (basic_block bb, rtx after)
5375 basic_block new_bb;
5376 insn_t insn;
5378 new_bb = sched_split_block_1 (bb, after);
5379 sel_add_bb (new_bb);
5381 /* This should be called after sel_add_bb, because this uses
5382 CONTAINING_RGN for the new block, which is not yet initialized.
5383 FIXME: this function may be a no-op now. */
5384 change_loops_latches (bb, new_bb);
5386 /* Update ORIG_BB_INDEX for insns moved into the new block. */
5387 FOR_BB_INSNS (new_bb, insn)
5388 if (INSN_P (insn))
5389 EXPR_ORIG_BB_INDEX (INSN_EXPR (insn)) = new_bb->index;
5391 if (sel_bb_empty_p (bb))
5393 gcc_assert (!sel_bb_empty_p (new_bb));
5395 /* NEW_BB has data sets that need to be updated and BB holds
5396 data sets that should be removed. Exchange these data sets
5397 so that we won't lose BB's valid data sets. */
5398 exchange_data_sets (new_bb, bb);
5399 free_data_sets (bb);
5402 if (!sel_bb_empty_p (new_bb)
5403 && bitmap_bit_p (blocks_to_reschedule, bb->index))
5404 bitmap_set_bit (blocks_to_reschedule, new_bb->index);
5406 return new_bb;
5409 /* If BB ends with a jump insn whose ID is bigger then PREV_MAX_UID, return it.
5410 Otherwise returns NULL. */
5411 static rtx_insn *
5412 check_for_new_jump (basic_block bb, int prev_max_uid)
5414 rtx_insn *end;
5416 end = sel_bb_end (bb);
5417 if (end && INSN_UID (end) >= prev_max_uid)
5418 return end;
5419 return NULL;
5422 /* Look for a new jump either in FROM_BB block or in newly created JUMP_BB block.
5423 New means having UID at least equal to PREV_MAX_UID. */
5424 static rtx_insn *
5425 find_new_jump (basic_block from, basic_block jump_bb, int prev_max_uid)
5427 rtx_insn *jump;
5429 /* Return immediately if no new insns were emitted. */
5430 if (get_max_uid () == prev_max_uid)
5431 return NULL;
5433 /* Now check both blocks for new jumps. It will ever be only one. */
5434 if ((jump = check_for_new_jump (from, prev_max_uid)))
5435 return jump;
5437 if (jump_bb != NULL
5438 && (jump = check_for_new_jump (jump_bb, prev_max_uid)))
5439 return jump;
5440 return NULL;
5443 /* Splits E and adds the newly created basic block to the current region.
5444 Returns this basic block. */
5445 basic_block
5446 sel_split_edge (edge e)
5448 basic_block new_bb, src, other_bb = NULL;
5449 int prev_max_uid;
5450 rtx_insn *jump;
5452 src = e->src;
5453 prev_max_uid = get_max_uid ();
5454 new_bb = split_edge (e);
5456 if (flag_sel_sched_pipelining_outer_loops
5457 && current_loop_nest)
5459 int i;
5460 basic_block bb;
5462 /* Some of the basic blocks might not have been added to the loop.
5463 Add them here, until this is fixed in force_fallthru. */
5464 for (i = 0;
5465 last_added_blocks.iterate (i, &bb); i++)
5466 if (!bb->loop_father)
5468 add_bb_to_loop (bb, e->dest->loop_father);
5470 gcc_assert (!other_bb && (new_bb->index != bb->index));
5471 other_bb = bb;
5475 /* Add all last_added_blocks to the region. */
5476 sel_add_bb (NULL);
5478 jump = find_new_jump (src, new_bb, prev_max_uid);
5479 if (jump)
5480 sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP);
5482 /* Put the correct lv set on this block. */
5483 if (other_bb && !sel_bb_empty_p (other_bb))
5484 compute_live (sel_bb_head (other_bb));
5486 return new_bb;
5489 /* Implement sched_create_empty_bb (). */
5490 static basic_block
5491 sel_create_empty_bb (basic_block after)
5493 basic_block new_bb;
5495 new_bb = sched_create_empty_bb_1 (after);
5497 /* We'll explicitly initialize NEW_BB via sel_init_only_bb () a bit
5498 later. */
5499 gcc_assert (last_added_blocks.length () == 1
5500 && last_added_blocks[0] == new_bb);
5502 last_added_blocks.release ();
5503 return new_bb;
5506 /* Implement sched_create_recovery_block. ORIG_INSN is where block
5507 will be splitted to insert a check. */
5508 basic_block
5509 sel_create_recovery_block (insn_t orig_insn)
5511 basic_block first_bb, second_bb, recovery_block;
5512 basic_block before_recovery = NULL;
5513 rtx_insn *jump;
5515 first_bb = BLOCK_FOR_INSN (orig_insn);
5516 if (sel_bb_end_p (orig_insn))
5518 /* Avoid introducing an empty block while splitting. */
5519 gcc_assert (single_succ_p (first_bb));
5520 second_bb = single_succ (first_bb);
5522 else
5523 second_bb = sched_split_block (first_bb, orig_insn);
5525 recovery_block = sched_create_recovery_block (&before_recovery);
5526 if (before_recovery)
5527 copy_lv_set_from (before_recovery, EXIT_BLOCK_PTR_FOR_FN (cfun));
5529 gcc_assert (sel_bb_empty_p (recovery_block));
5530 sched_create_recovery_edges (first_bb, recovery_block, second_bb);
5531 if (current_loops != NULL)
5532 add_bb_to_loop (recovery_block, first_bb->loop_father);
5534 sel_add_bb (recovery_block);
5536 jump = BB_END (recovery_block);
5537 gcc_assert (sel_bb_head (recovery_block) == jump);
5538 sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP);
5540 return recovery_block;
5543 /* Merge basic block B into basic block A. */
5544 static void
5545 sel_merge_blocks (basic_block a, basic_block b)
5547 gcc_assert (sel_bb_empty_p (b)
5548 && EDGE_COUNT (b->preds) == 1
5549 && EDGE_PRED (b, 0)->src == b->prev_bb);
5551 move_bb_info (b->prev_bb, b);
5552 remove_empty_bb (b, false);
5553 merge_blocks (a, b);
5554 change_loops_latches (b, a);
5557 /* A wrapper for redirect_edge_and_branch_force, which also initializes
5558 data structures for possibly created bb and insns. */
5559 void
5560 sel_redirect_edge_and_branch_force (edge e, basic_block to)
5562 basic_block jump_bb, src, orig_dest = e->dest;
5563 int prev_max_uid;
5564 rtx_insn *jump;
5565 int old_seqno = -1;
5567 /* This function is now used only for bookkeeping code creation, where
5568 we'll never get the single pred of orig_dest block and thus will not
5569 hit unreachable blocks when updating dominator info. */
5570 gcc_assert (!sel_bb_empty_p (e->src)
5571 && !single_pred_p (orig_dest));
5572 src = e->src;
5573 prev_max_uid = get_max_uid ();
5574 /* Compute and pass old_seqno down to sel_init_new_insn only for the case
5575 when the conditional jump being redirected may become unconditional. */
5576 if (any_condjump_p (BB_END (src))
5577 && INSN_SEQNO (BB_END (src)) >= 0)
5578 old_seqno = INSN_SEQNO (BB_END (src));
5580 jump_bb = redirect_edge_and_branch_force (e, to);
5581 if (jump_bb != NULL)
5582 sel_add_bb (jump_bb);
5584 /* This function could not be used to spoil the loop structure by now,
5585 thus we don't care to update anything. But check it to be sure. */
5586 if (current_loop_nest
5587 && pipelining_p)
5588 gcc_assert (loop_latch_edge (current_loop_nest));
5590 jump = find_new_jump (src, jump_bb, prev_max_uid);
5591 if (jump)
5592 sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP,
5593 old_seqno);
5594 set_immediate_dominator (CDI_DOMINATORS, to,
5595 recompute_dominator (CDI_DOMINATORS, to));
5596 set_immediate_dominator (CDI_DOMINATORS, orig_dest,
5597 recompute_dominator (CDI_DOMINATORS, orig_dest));
5600 /* A wrapper for redirect_edge_and_branch. Return TRUE if blocks connected by
5601 redirected edge are in reverse topological order. */
5602 bool
5603 sel_redirect_edge_and_branch (edge e, basic_block to)
5605 bool latch_edge_p;
5606 basic_block src, orig_dest = e->dest;
5607 int prev_max_uid;
5608 rtx_insn *jump;
5609 edge redirected;
5610 bool recompute_toporder_p = false;
5611 bool maybe_unreachable = single_pred_p (orig_dest);
5612 int old_seqno = -1;
5614 latch_edge_p = (pipelining_p
5615 && current_loop_nest
5616 && e == loop_latch_edge (current_loop_nest));
5618 src = e->src;
5619 prev_max_uid = get_max_uid ();
5621 /* Compute and pass old_seqno down to sel_init_new_insn only for the case
5622 when the conditional jump being redirected may become unconditional. */
5623 if (any_condjump_p (BB_END (src))
5624 && INSN_SEQNO (BB_END (src)) >= 0)
5625 old_seqno = INSN_SEQNO (BB_END (src));
5627 redirected = redirect_edge_and_branch (e, to);
5629 gcc_assert (redirected && !last_added_blocks.exists ());
5631 /* When we've redirected a latch edge, update the header. */
5632 if (latch_edge_p)
5634 current_loop_nest->header = to;
5635 gcc_assert (loop_latch_edge (current_loop_nest));
5638 /* In rare situations, the topological relation between the blocks connected
5639 by the redirected edge can change (see PR42245 for an example). Update
5640 block_to_bb/bb_to_block. */
5641 if (CONTAINING_RGN (e->src->index) == CONTAINING_RGN (to->index)
5642 && BLOCK_TO_BB (e->src->index) > BLOCK_TO_BB (to->index))
5643 recompute_toporder_p = true;
5645 jump = find_new_jump (src, NULL, prev_max_uid);
5646 if (jump)
5647 sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP, old_seqno);
5649 /* Only update dominator info when we don't have unreachable blocks.
5650 Otherwise we'll update in maybe_tidy_empty_bb. */
5651 if (!maybe_unreachable)
5653 set_immediate_dominator (CDI_DOMINATORS, to,
5654 recompute_dominator (CDI_DOMINATORS, to));
5655 set_immediate_dominator (CDI_DOMINATORS, orig_dest,
5656 recompute_dominator (CDI_DOMINATORS, orig_dest));
5658 return recompute_toporder_p;
5661 /* This variable holds the cfg hooks used by the selective scheduler. */
5662 static struct cfg_hooks sel_cfg_hooks;
5664 /* Register sel-sched cfg hooks. */
5665 void
5666 sel_register_cfg_hooks (void)
5668 sched_split_block = sel_split_block;
5670 orig_cfg_hooks = get_cfg_hooks ();
5671 sel_cfg_hooks = orig_cfg_hooks;
5673 sel_cfg_hooks.create_basic_block = sel_create_basic_block;
5675 set_cfg_hooks (sel_cfg_hooks);
5677 sched_init_only_bb = sel_init_only_bb;
5678 sched_split_block = sel_split_block;
5679 sched_create_empty_bb = sel_create_empty_bb;
5682 /* Unregister sel-sched cfg hooks. */
5683 void
5684 sel_unregister_cfg_hooks (void)
5686 sched_create_empty_bb = NULL;
5687 sched_split_block = NULL;
5688 sched_init_only_bb = NULL;
5690 set_cfg_hooks (orig_cfg_hooks);
5694 /* Emit an insn rtx based on PATTERN. If a jump insn is wanted,
5695 LABEL is where this jump should be directed. */
5696 rtx_insn *
5697 create_insn_rtx_from_pattern (rtx pattern, rtx label)
5699 rtx_insn *insn_rtx;
5701 gcc_assert (!INSN_P (pattern));
5703 start_sequence ();
5705 if (label == NULL_RTX)
5706 insn_rtx = emit_insn (pattern);
5707 else if (DEBUG_INSN_P (label))
5708 insn_rtx = emit_debug_insn (pattern);
5709 else
5711 insn_rtx = emit_jump_insn (pattern);
5712 JUMP_LABEL (insn_rtx) = label;
5713 ++LABEL_NUSES (label);
5716 end_sequence ();
5718 sched_extend_luids ();
5719 sched_extend_target ();
5720 sched_deps_init (false);
5722 /* Initialize INSN_CODE now. */
5723 recog_memoized (insn_rtx);
5724 return insn_rtx;
5727 /* Create a new vinsn for INSN_RTX. FORCE_UNIQUE_P is true when the vinsn
5728 must not be clonable. */
5729 vinsn_t
5730 create_vinsn_from_insn_rtx (rtx_insn *insn_rtx, bool force_unique_p)
5732 gcc_assert (INSN_P (insn_rtx) && !INSN_IN_STREAM_P (insn_rtx));
5734 /* If VINSN_TYPE is not USE, retain its uniqueness. */
5735 return vinsn_create (insn_rtx, force_unique_p);
5738 /* Create a copy of INSN_RTX. */
5739 rtx_insn *
5740 create_copy_of_insn_rtx (rtx insn_rtx)
5742 rtx_insn *res;
5743 rtx link;
5745 if (DEBUG_INSN_P (insn_rtx))
5746 return create_insn_rtx_from_pattern (copy_rtx (PATTERN (insn_rtx)),
5747 insn_rtx);
5749 gcc_assert (NONJUMP_INSN_P (insn_rtx));
5751 res = create_insn_rtx_from_pattern (copy_rtx (PATTERN (insn_rtx)),
5752 NULL_RTX);
5754 /* Copy all REG_NOTES except REG_EQUAL/REG_EQUIV and REG_LABEL_OPERAND
5755 since mark_jump_label will make them. REG_LABEL_TARGETs are created
5756 there too, but are supposed to be sticky, so we copy them. */
5757 for (link = REG_NOTES (insn_rtx); link; link = XEXP (link, 1))
5758 if (REG_NOTE_KIND (link) != REG_LABEL_OPERAND
5759 && REG_NOTE_KIND (link) != REG_EQUAL
5760 && REG_NOTE_KIND (link) != REG_EQUIV)
5762 if (GET_CODE (link) == EXPR_LIST)
5763 add_reg_note (res, REG_NOTE_KIND (link),
5764 copy_insn_1 (XEXP (link, 0)));
5765 else
5766 add_reg_note (res, REG_NOTE_KIND (link), XEXP (link, 0));
5769 return res;
5772 /* Change vinsn field of EXPR to hold NEW_VINSN. */
5773 void
5774 change_vinsn_in_expr (expr_t expr, vinsn_t new_vinsn)
5776 vinsn_detach (EXPR_VINSN (expr));
5778 EXPR_VINSN (expr) = new_vinsn;
5779 vinsn_attach (new_vinsn);
5782 /* Helpers for global init. */
5783 /* This structure is used to be able to call existing bundling mechanism
5784 and calculate insn priorities. */
5785 static struct haifa_sched_info sched_sel_haifa_sched_info =
5787 NULL, /* init_ready_list */
5788 NULL, /* can_schedule_ready_p */
5789 NULL, /* schedule_more_p */
5790 NULL, /* new_ready */
5791 NULL, /* rgn_rank */
5792 sel_print_insn, /* rgn_print_insn */
5793 contributes_to_priority,
5794 NULL, /* insn_finishes_block_p */
5796 NULL, NULL,
5797 NULL, NULL,
5798 0, 0,
5800 NULL, /* add_remove_insn */
5801 NULL, /* begin_schedule_ready */
5802 NULL, /* begin_move_insn */
5803 NULL, /* advance_target_bb */
5805 NULL,
5806 NULL,
5808 SEL_SCHED | NEW_BBS
5811 /* Setup special insns used in the scheduler. */
5812 void
5813 setup_nop_and_exit_insns (void)
5815 gcc_assert (nop_pattern == NULL_RTX
5816 && exit_insn == NULL_RTX);
5818 nop_pattern = constm1_rtx;
5820 start_sequence ();
5821 emit_insn (nop_pattern);
5822 exit_insn = get_insns ();
5823 end_sequence ();
5824 set_block_for_insn (exit_insn, EXIT_BLOCK_PTR_FOR_FN (cfun));
5827 /* Free special insns used in the scheduler. */
5828 void
5829 free_nop_and_exit_insns (void)
5831 exit_insn = NULL;
5832 nop_pattern = NULL_RTX;
5835 /* Setup a special vinsn used in new insns initialization. */
5836 void
5837 setup_nop_vinsn (void)
5839 nop_vinsn = vinsn_create (exit_insn, false);
5840 vinsn_attach (nop_vinsn);
5843 /* Free a special vinsn used in new insns initialization. */
5844 void
5845 free_nop_vinsn (void)
5847 gcc_assert (VINSN_COUNT (nop_vinsn) == 1);
5848 vinsn_detach (nop_vinsn);
5849 nop_vinsn = NULL;
5852 /* Call a set_sched_flags hook. */
5853 void
5854 sel_set_sched_flags (void)
5856 /* ??? This means that set_sched_flags were called, and we decided to
5857 support speculation. However, set_sched_flags also modifies flags
5858 on current_sched_info, doing this only at global init. And we
5859 sometimes change c_s_i later. So put the correct flags again. */
5860 if (spec_info && targetm.sched.set_sched_flags)
5861 targetm.sched.set_sched_flags (spec_info);
5864 /* Setup pointers to global sched info structures. */
5865 void
5866 sel_setup_sched_infos (void)
5868 rgn_setup_common_sched_info ();
5870 memcpy (&sel_common_sched_info, common_sched_info,
5871 sizeof (sel_common_sched_info));
5873 sel_common_sched_info.fix_recovery_cfg = NULL;
5874 sel_common_sched_info.add_block = NULL;
5875 sel_common_sched_info.estimate_number_of_insns
5876 = sel_estimate_number_of_insns;
5877 sel_common_sched_info.luid_for_non_insn = sel_luid_for_non_insn;
5878 sel_common_sched_info.sched_pass_id = SCHED_SEL_PASS;
5880 common_sched_info = &sel_common_sched_info;
5882 current_sched_info = &sched_sel_haifa_sched_info;
5883 current_sched_info->sched_max_insns_priority =
5884 get_rgn_sched_max_insns_priority ();
5886 sel_set_sched_flags ();
5890 /* Adds basic block BB to region RGN at the position *BB_ORD_INDEX,
5891 *BB_ORD_INDEX after that is increased. */
5892 static void
5893 sel_add_block_to_region (basic_block bb, int *bb_ord_index, int rgn)
5895 RGN_NR_BLOCKS (rgn) += 1;
5896 RGN_DONT_CALC_DEPS (rgn) = 0;
5897 RGN_HAS_REAL_EBB (rgn) = 0;
5898 CONTAINING_RGN (bb->index) = rgn;
5899 BLOCK_TO_BB (bb->index) = *bb_ord_index;
5900 rgn_bb_table[RGN_BLOCKS (rgn) + *bb_ord_index] = bb->index;
5901 (*bb_ord_index)++;
5903 /* FIXME: it is true only when not scheduling ebbs. */
5904 RGN_BLOCKS (rgn + 1) = RGN_BLOCKS (rgn) + RGN_NR_BLOCKS (rgn);
5907 /* Functions to support pipelining of outer loops. */
5909 /* Creates a new empty region and returns it's number. */
5910 static int
5911 sel_create_new_region (void)
5913 int new_rgn_number = nr_regions;
5915 RGN_NR_BLOCKS (new_rgn_number) = 0;
5917 /* FIXME: This will work only when EBBs are not created. */
5918 if (new_rgn_number != 0)
5919 RGN_BLOCKS (new_rgn_number) = RGN_BLOCKS (new_rgn_number - 1) +
5920 RGN_NR_BLOCKS (new_rgn_number - 1);
5921 else
5922 RGN_BLOCKS (new_rgn_number) = 0;
5924 /* Set the blocks of the next region so the other functions may
5925 calculate the number of blocks in the region. */
5926 RGN_BLOCKS (new_rgn_number + 1) = RGN_BLOCKS (new_rgn_number) +
5927 RGN_NR_BLOCKS (new_rgn_number);
5929 nr_regions++;
5931 return new_rgn_number;
5934 /* If X has a smaller topological sort number than Y, returns -1;
5935 if greater, returns 1. */
5936 static int
5937 bb_top_order_comparator (const void *x, const void *y)
5939 basic_block bb1 = *(const basic_block *) x;
5940 basic_block bb2 = *(const basic_block *) y;
5942 gcc_assert (bb1 == bb2
5943 || rev_top_order_index[bb1->index]
5944 != rev_top_order_index[bb2->index]);
5946 /* It's a reverse topological order in REV_TOP_ORDER_INDEX, so
5947 bbs with greater number should go earlier. */
5948 if (rev_top_order_index[bb1->index] > rev_top_order_index[bb2->index])
5949 return -1;
5950 else
5951 return 1;
5954 /* Create a region for LOOP and return its number. If we don't want
5955 to pipeline LOOP, return -1. */
5956 static int
5957 make_region_from_loop (struct loop *loop)
5959 unsigned int i;
5960 int new_rgn_number = -1;
5961 struct loop *inner;
5963 /* Basic block index, to be assigned to BLOCK_TO_BB. */
5964 int bb_ord_index = 0;
5965 basic_block *loop_blocks;
5966 basic_block preheader_block;
5968 if (loop->num_nodes
5969 > (unsigned) PARAM_VALUE (PARAM_MAX_PIPELINE_REGION_BLOCKS))
5970 return -1;
5972 /* Don't pipeline loops whose latch belongs to some of its inner loops. */
5973 for (inner = loop->inner; inner; inner = inner->inner)
5974 if (flow_bb_inside_loop_p (inner, loop->latch))
5975 return -1;
5977 loop->ninsns = num_loop_insns (loop);
5978 if ((int) loop->ninsns > PARAM_VALUE (PARAM_MAX_PIPELINE_REGION_INSNS))
5979 return -1;
5981 loop_blocks = get_loop_body_in_custom_order (loop, bb_top_order_comparator);
5983 for (i = 0; i < loop->num_nodes; i++)
5984 if (loop_blocks[i]->flags & BB_IRREDUCIBLE_LOOP)
5986 free (loop_blocks);
5987 return -1;
5990 preheader_block = loop_preheader_edge (loop)->src;
5991 gcc_assert (preheader_block);
5992 gcc_assert (loop_blocks[0] == loop->header);
5994 new_rgn_number = sel_create_new_region ();
5996 sel_add_block_to_region (preheader_block, &bb_ord_index, new_rgn_number);
5997 bitmap_set_bit (bbs_in_loop_rgns, preheader_block->index);
5999 for (i = 0; i < loop->num_nodes; i++)
6001 /* Add only those blocks that haven't been scheduled in the inner loop.
6002 The exception is the basic blocks with bookkeeping code - they should
6003 be added to the region (and they actually don't belong to the loop
6004 body, but to the region containing that loop body). */
6006 gcc_assert (new_rgn_number >= 0);
6008 if (! bitmap_bit_p (bbs_in_loop_rgns, loop_blocks[i]->index))
6010 sel_add_block_to_region (loop_blocks[i], &bb_ord_index,
6011 new_rgn_number);
6012 bitmap_set_bit (bbs_in_loop_rgns, loop_blocks[i]->index);
6016 free (loop_blocks);
6017 MARK_LOOP_FOR_PIPELINING (loop);
6019 return new_rgn_number;
6022 /* Create a new region from preheader blocks LOOP_BLOCKS. */
6023 void
6024 make_region_from_loop_preheader (vec<basic_block> *&loop_blocks)
6026 unsigned int i;
6027 int new_rgn_number = -1;
6028 basic_block bb;
6030 /* Basic block index, to be assigned to BLOCK_TO_BB. */
6031 int bb_ord_index = 0;
6033 new_rgn_number = sel_create_new_region ();
6035 FOR_EACH_VEC_ELT (*loop_blocks, i, bb)
6037 gcc_assert (new_rgn_number >= 0);
6039 sel_add_block_to_region (bb, &bb_ord_index, new_rgn_number);
6042 vec_free (loop_blocks);
6046 /* Create region(s) from loop nest LOOP, such that inner loops will be
6047 pipelined before outer loops. Returns true when a region for LOOP
6048 is created. */
6049 static bool
6050 make_regions_from_loop_nest (struct loop *loop)
6052 struct loop *cur_loop;
6053 int rgn_number;
6055 /* Traverse all inner nodes of the loop. */
6056 for (cur_loop = loop->inner; cur_loop; cur_loop = cur_loop->next)
6057 if (! bitmap_bit_p (bbs_in_loop_rgns, cur_loop->header->index))
6058 return false;
6060 /* At this moment all regular inner loops should have been pipelined.
6061 Try to create a region from this loop. */
6062 rgn_number = make_region_from_loop (loop);
6064 if (rgn_number < 0)
6065 return false;
6067 loop_nests.safe_push (loop);
6068 return true;
6071 /* Initalize data structures needed. */
6072 void
6073 sel_init_pipelining (void)
6075 /* Collect loop information to be used in outer loops pipelining. */
6076 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
6077 | LOOPS_HAVE_FALLTHRU_PREHEADERS
6078 | LOOPS_HAVE_RECORDED_EXITS
6079 | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS);
6080 current_loop_nest = NULL;
6082 bbs_in_loop_rgns = sbitmap_alloc (last_basic_block_for_fn (cfun));
6083 bitmap_clear (bbs_in_loop_rgns);
6085 recompute_rev_top_order ();
6088 /* Returns a struct loop for region RGN. */
6089 loop_p
6090 get_loop_nest_for_rgn (unsigned int rgn)
6092 /* Regions created with extend_rgns don't have corresponding loop nests,
6093 because they don't represent loops. */
6094 if (rgn < loop_nests.length ())
6095 return loop_nests[rgn];
6096 else
6097 return NULL;
6100 /* True when LOOP was included into pipelining regions. */
6101 bool
6102 considered_for_pipelining_p (struct loop *loop)
6104 if (loop_depth (loop) == 0)
6105 return false;
6107 /* Now, the loop could be too large or irreducible. Check whether its
6108 region is in LOOP_NESTS.
6109 We determine the region number of LOOP as the region number of its
6110 latch. We can't use header here, because this header could be
6111 just removed preheader and it will give us the wrong region number.
6112 Latch can't be used because it could be in the inner loop too. */
6113 if (LOOP_MARKED_FOR_PIPELINING_P (loop))
6115 int rgn = CONTAINING_RGN (loop->latch->index);
6117 gcc_assert ((unsigned) rgn < loop_nests.length ());
6118 return true;
6121 return false;
6124 /* Makes regions from the rest of the blocks, after loops are chosen
6125 for pipelining. */
6126 static void
6127 make_regions_from_the_rest (void)
6129 int cur_rgn_blocks;
6130 int *loop_hdr;
6131 int i;
6133 basic_block bb;
6134 edge e;
6135 edge_iterator ei;
6136 int *degree;
6138 /* Index in rgn_bb_table where to start allocating new regions. */
6139 cur_rgn_blocks = nr_regions ? RGN_BLOCKS (nr_regions) : 0;
6141 /* Make regions from all the rest basic blocks - those that don't belong to
6142 any loop or belong to irreducible loops. Prepare the data structures
6143 for extend_rgns. */
6145 /* LOOP_HDR[I] == -1 if I-th bb doesn't belong to any loop,
6146 LOOP_HDR[I] == LOOP_HDR[J] iff basic blocks I and J reside within the same
6147 loop. */
6148 loop_hdr = XNEWVEC (int, last_basic_block_for_fn (cfun));
6149 degree = XCNEWVEC (int, last_basic_block_for_fn (cfun));
6152 /* For each basic block that belongs to some loop assign the number
6153 of innermost loop it belongs to. */
6154 for (i = 0; i < last_basic_block_for_fn (cfun); i++)
6155 loop_hdr[i] = -1;
6157 FOR_EACH_BB_FN (bb, cfun)
6159 if (bb->loop_father && bb->loop_father->num != 0
6160 && !(bb->flags & BB_IRREDUCIBLE_LOOP))
6161 loop_hdr[bb->index] = bb->loop_father->num;
6164 /* For each basic block degree is calculated as the number of incoming
6165 edges, that are going out of bbs that are not yet scheduled.
6166 The basic blocks that are scheduled have degree value of zero. */
6167 FOR_EACH_BB_FN (bb, cfun)
6169 degree[bb->index] = 0;
6171 if (!bitmap_bit_p (bbs_in_loop_rgns, bb->index))
6173 FOR_EACH_EDGE (e, ei, bb->preds)
6174 if (!bitmap_bit_p (bbs_in_loop_rgns, e->src->index))
6175 degree[bb->index]++;
6177 else
6178 degree[bb->index] = -1;
6181 extend_rgns (degree, &cur_rgn_blocks, bbs_in_loop_rgns, loop_hdr);
6183 /* Any block that did not end up in a region is placed into a region
6184 by itself. */
6185 FOR_EACH_BB_FN (bb, cfun)
6186 if (degree[bb->index] >= 0)
6188 rgn_bb_table[cur_rgn_blocks] = bb->index;
6189 RGN_NR_BLOCKS (nr_regions) = 1;
6190 RGN_BLOCKS (nr_regions) = cur_rgn_blocks++;
6191 RGN_DONT_CALC_DEPS (nr_regions) = 0;
6192 RGN_HAS_REAL_EBB (nr_regions) = 0;
6193 CONTAINING_RGN (bb->index) = nr_regions++;
6194 BLOCK_TO_BB (bb->index) = 0;
6197 free (degree);
6198 free (loop_hdr);
6201 /* Free data structures used in pipelining of loops. */
6202 void sel_finish_pipelining (void)
6204 struct loop *loop;
6206 /* Release aux fields so we don't free them later by mistake. */
6207 FOR_EACH_LOOP (loop, 0)
6208 loop->aux = NULL;
6210 loop_optimizer_finalize ();
6212 loop_nests.release ();
6214 free (rev_top_order_index);
6215 rev_top_order_index = NULL;
6218 /* This function replaces the find_rgns when
6219 FLAG_SEL_SCHED_PIPELINING_OUTER_LOOPS is set. */
6220 void
6221 sel_find_rgns (void)
6223 sel_init_pipelining ();
6224 extend_regions ();
6226 if (current_loops)
6228 loop_p loop;
6230 FOR_EACH_LOOP (loop, (flag_sel_sched_pipelining_outer_loops
6231 ? LI_FROM_INNERMOST
6232 : LI_ONLY_INNERMOST))
6233 make_regions_from_loop_nest (loop);
6236 /* Make regions from all the rest basic blocks and schedule them.
6237 These blocks include blocks that don't belong to any loop or belong
6238 to irreducible loops. */
6239 make_regions_from_the_rest ();
6241 /* We don't need bbs_in_loop_rgns anymore. */
6242 sbitmap_free (bbs_in_loop_rgns);
6243 bbs_in_loop_rgns = NULL;
6246 /* Add the preheader blocks from previous loop to current region taking
6247 it from LOOP_PREHEADER_BLOCKS (current_loop_nest) and record them in *BBS.
6248 This function is only used with -fsel-sched-pipelining-outer-loops. */
6249 void
6250 sel_add_loop_preheaders (bb_vec_t *bbs)
6252 int i;
6253 basic_block bb;
6254 vec<basic_block> *preheader_blocks
6255 = LOOP_PREHEADER_BLOCKS (current_loop_nest);
6257 if (!preheader_blocks)
6258 return;
6260 for (i = 0; preheader_blocks->iterate (i, &bb); i++)
6262 bbs->safe_push (bb);
6263 last_added_blocks.safe_push (bb);
6264 sel_add_bb (bb);
6267 vec_free (preheader_blocks);
6270 /* While pipelining outer loops, returns TRUE if BB is a loop preheader.
6271 Please note that the function should also work when pipelining_p is
6272 false, because it is used when deciding whether we should or should
6273 not reschedule pipelined code. */
6274 bool
6275 sel_is_loop_preheader_p (basic_block bb)
6277 if (current_loop_nest)
6279 struct loop *outer;
6281 if (preheader_removed)
6282 return false;
6284 /* Preheader is the first block in the region. */
6285 if (BLOCK_TO_BB (bb->index) == 0)
6286 return true;
6288 /* We used to find a preheader with the topological information.
6289 Check that the above code is equivalent to what we did before. */
6291 if (in_current_region_p (current_loop_nest->header))
6292 gcc_assert (!(BLOCK_TO_BB (bb->index)
6293 < BLOCK_TO_BB (current_loop_nest->header->index)));
6295 /* Support the situation when the latch block of outer loop
6296 could be from here. */
6297 for (outer = loop_outer (current_loop_nest);
6298 outer;
6299 outer = loop_outer (outer))
6300 if (considered_for_pipelining_p (outer) && outer->latch == bb)
6301 gcc_unreachable ();
6304 return false;
6307 /* Check whether JUMP_BB ends with a jump insn that leads only to DEST_BB and
6308 can be removed, making the corresponding edge fallthrough (assuming that
6309 all basic blocks between JUMP_BB and DEST_BB are empty). */
6310 static bool
6311 bb_has_removable_jump_to_p (basic_block jump_bb, basic_block dest_bb)
6313 if (!onlyjump_p (BB_END (jump_bb))
6314 || tablejump_p (BB_END (jump_bb), NULL, NULL))
6315 return false;
6317 /* Several outgoing edges, abnormal edge or destination of jump is
6318 not DEST_BB. */
6319 if (EDGE_COUNT (jump_bb->succs) != 1
6320 || EDGE_SUCC (jump_bb, 0)->flags & (EDGE_ABNORMAL | EDGE_CROSSING)
6321 || EDGE_SUCC (jump_bb, 0)->dest != dest_bb)
6322 return false;
6324 /* If not anything of the upper. */
6325 return true;
6328 /* Removes the loop preheader from the current region and saves it in
6329 PREHEADER_BLOCKS of the father loop, so they will be added later to
6330 region that represents an outer loop. */
6331 static void
6332 sel_remove_loop_preheader (void)
6334 int i, old_len;
6335 int cur_rgn = CONTAINING_RGN (BB_TO_BLOCK (0));
6336 basic_block bb;
6337 bool all_empty_p = true;
6338 vec<basic_block> *preheader_blocks
6339 = LOOP_PREHEADER_BLOCKS (loop_outer (current_loop_nest));
6341 vec_check_alloc (preheader_blocks, 0);
6343 gcc_assert (current_loop_nest);
6344 old_len = preheader_blocks->length ();
6346 /* Add blocks that aren't within the current loop to PREHEADER_BLOCKS. */
6347 for (i = 0; i < RGN_NR_BLOCKS (cur_rgn); i++)
6349 bb = BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (i));
6351 /* If the basic block belongs to region, but doesn't belong to
6352 corresponding loop, then it should be a preheader. */
6353 if (sel_is_loop_preheader_p (bb))
6355 preheader_blocks->safe_push (bb);
6356 if (BB_END (bb) != bb_note (bb))
6357 all_empty_p = false;
6361 /* Remove these blocks only after iterating over the whole region. */
6362 for (i = preheader_blocks->length () - 1; i >= old_len; i--)
6364 bb = (*preheader_blocks)[i];
6365 sel_remove_bb (bb, false);
6368 if (!considered_for_pipelining_p (loop_outer (current_loop_nest)))
6370 if (!all_empty_p)
6371 /* Immediately create new region from preheader. */
6372 make_region_from_loop_preheader (preheader_blocks);
6373 else
6375 /* If all preheader blocks are empty - dont create new empty region.
6376 Instead, remove them completely. */
6377 FOR_EACH_VEC_ELT (*preheader_blocks, i, bb)
6379 edge e;
6380 edge_iterator ei;
6381 basic_block prev_bb = bb->prev_bb, next_bb = bb->next_bb;
6383 /* Redirect all incoming edges to next basic block. */
6384 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
6386 if (! (e->flags & EDGE_FALLTHRU))
6387 redirect_edge_and_branch (e, bb->next_bb);
6388 else
6389 redirect_edge_succ (e, bb->next_bb);
6391 gcc_assert (BB_NOTE_LIST (bb) == NULL);
6392 delete_and_free_basic_block (bb);
6394 /* Check if after deleting preheader there is a nonconditional
6395 jump in PREV_BB that leads to the next basic block NEXT_BB.
6396 If it is so - delete this jump and clear data sets of its
6397 basic block if it becomes empty. */
6398 if (next_bb->prev_bb == prev_bb
6399 && prev_bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
6400 && bb_has_removable_jump_to_p (prev_bb, next_bb))
6402 redirect_edge_and_branch (EDGE_SUCC (prev_bb, 0), next_bb);
6403 if (BB_END (prev_bb) == bb_note (prev_bb))
6404 free_data_sets (prev_bb);
6407 set_immediate_dominator (CDI_DOMINATORS, next_bb,
6408 recompute_dominator (CDI_DOMINATORS,
6409 next_bb));
6412 vec_free (preheader_blocks);
6414 else
6415 /* Store preheader within the father's loop structure. */
6416 SET_LOOP_PREHEADER_BLOCKS (loop_outer (current_loop_nest),
6417 preheader_blocks);
6420 #endif