Enable dumping of alias graphs.
[official-gcc/Ramakrishna.git] / gcc / sel-sched-ir.c
blob9a61ed84dca6e8f642573793f7a08669c43f10a0
1 /* Instruction scheduling pass. Selective scheduler and pipeliner.
2 Copyright (C) 2006, 2007, 2008, 2009 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 "toplev.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 "flags.h"
31 #include "insn-config.h"
32 #include "insn-attr.h"
33 #include "except.h"
34 #include "toplev.h"
35 #include "recog.h"
36 #include "params.h"
37 #include "target.h"
38 #include "timevar.h"
39 #include "tree-pass.h"
40 #include "sched-int.h"
41 #include "ggc.h"
42 #include "tree.h"
43 #include "vec.h"
44 #include "langhooks.h"
45 #include "rtlhooks-def.h"
47 #ifdef INSN_SCHEDULING
48 #include "sel-sched-ir.h"
49 /* We don't have to use it except for sel_print_insn. */
50 #include "sel-sched-dump.h"
52 /* A vector holding bb info for whole scheduling pass. */
53 VEC(sel_global_bb_info_def, heap) *sel_global_bb_info = NULL;
55 /* A vector holding bb info. */
56 VEC(sel_region_bb_info_def, heap) *sel_region_bb_info = NULL;
58 /* A pool for allocating all lists. */
59 alloc_pool sched_lists_pool;
61 /* This contains information about successors for compute_av_set. */
62 struct succs_info current_succs;
64 /* Data structure to describe interaction with the generic scheduler utils. */
65 static struct common_sched_info_def sel_common_sched_info;
67 /* The loop nest being pipelined. */
68 struct loop *current_loop_nest;
70 /* LOOP_NESTS is a vector containing the corresponding loop nest for
71 each region. */
72 static VEC(loop_p, heap) *loop_nests = NULL;
74 /* Saves blocks already in loop regions, indexed by bb->index. */
75 static sbitmap bbs_in_loop_rgns = NULL;
77 /* CFG hooks that are saved before changing create_basic_block hook. */
78 static struct cfg_hooks orig_cfg_hooks;
81 /* Array containing reverse topological index of function basic blocks,
82 indexed by BB->INDEX. */
83 static int *rev_top_order_index = NULL;
85 /* Length of the above array. */
86 static int rev_top_order_index_len = -1;
88 /* A regset pool structure. */
89 static struct
91 /* The stack to which regsets are returned. */
92 regset *v;
94 /* Its pointer. */
95 int n;
97 /* Its size. */
98 int s;
100 /* In VV we save all generated regsets so that, when destructing the
101 pool, we can compare it with V and check that every regset was returned
102 back to pool. */
103 regset *vv;
105 /* The pointer of VV stack. */
106 int nn;
108 /* Its size. */
109 int ss;
111 /* The difference between allocated and returned regsets. */
112 int diff;
113 } regset_pool = { NULL, 0, 0, NULL, 0, 0, 0 };
115 /* This represents the nop pool. */
116 static struct
118 /* The vector which holds previously emitted nops. */
119 insn_t *v;
121 /* Its pointer. */
122 int n;
124 /* Its size. */
125 int s;
126 } nop_pool = { NULL, 0, 0 };
128 /* The pool for basic block notes. */
129 static rtx_vec_t bb_note_pool;
131 /* A NOP pattern used to emit placeholder insns. */
132 rtx nop_pattern = NULL_RTX;
133 /* A special instruction that resides in EXIT_BLOCK.
134 EXIT_INSN is successor of the insns that lead to EXIT_BLOCK. */
135 rtx exit_insn = NULL_RTX;
137 /* TRUE if while scheduling current region, which is loop, its preheader
138 was removed. */
139 bool preheader_removed = false;
142 /* Forward static declarations. */
143 static void fence_clear (fence_t);
145 static void deps_init_id (idata_t, insn_t, bool);
146 static void init_id_from_df (idata_t, insn_t, bool);
147 static expr_t set_insn_init (expr_t, vinsn_t, int);
149 static void cfg_preds (basic_block, insn_t **, int *);
150 static void prepare_insn_expr (insn_t, int);
151 static void free_history_vect (VEC (expr_history_def, heap) **);
153 static void move_bb_info (basic_block, basic_block);
154 static void remove_empty_bb (basic_block, bool);
155 static void sel_remove_loop_preheader (void);
157 static bool insn_is_the_only_one_in_bb_p (insn_t);
158 static void create_initial_data_sets (basic_block);
160 static void free_av_set (basic_block);
161 static void invalidate_av_set (basic_block);
162 static void extend_insn_data (void);
163 static void sel_init_new_insn (insn_t, int);
164 static void finish_insns (void);
166 /* Various list functions. */
168 /* Copy an instruction list L. */
169 ilist_t
170 ilist_copy (ilist_t l)
172 ilist_t head = NULL, *tailp = &head;
174 while (l)
176 ilist_add (tailp, ILIST_INSN (l));
177 tailp = &ILIST_NEXT (*tailp);
178 l = ILIST_NEXT (l);
181 return head;
184 /* Invert an instruction list L. */
185 ilist_t
186 ilist_invert (ilist_t l)
188 ilist_t res = NULL;
190 while (l)
192 ilist_add (&res, ILIST_INSN (l));
193 l = ILIST_NEXT (l);
196 return res;
199 /* Add a new boundary to the LP list with parameters TO, PTR, and DC. */
200 void
201 blist_add (blist_t *lp, insn_t to, ilist_t ptr, deps_t dc)
203 bnd_t bnd;
205 _list_add (lp);
206 bnd = BLIST_BND (*lp);
208 BND_TO (bnd) = to;
209 BND_PTR (bnd) = ptr;
210 BND_AV (bnd) = NULL;
211 BND_AV1 (bnd) = NULL;
212 BND_DC (bnd) = dc;
215 /* Remove the list note pointed to by LP. */
216 void
217 blist_remove (blist_t *lp)
219 bnd_t b = BLIST_BND (*lp);
221 av_set_clear (&BND_AV (b));
222 av_set_clear (&BND_AV1 (b));
223 ilist_clear (&BND_PTR (b));
225 _list_remove (lp);
228 /* Init a fence tail L. */
229 void
230 flist_tail_init (flist_tail_t l)
232 FLIST_TAIL_HEAD (l) = NULL;
233 FLIST_TAIL_TAILP (l) = &FLIST_TAIL_HEAD (l);
236 /* Try to find fence corresponding to INSN in L. */
237 fence_t
238 flist_lookup (flist_t l, insn_t insn)
240 while (l)
242 if (FENCE_INSN (FLIST_FENCE (l)) == insn)
243 return FLIST_FENCE (l);
245 l = FLIST_NEXT (l);
248 return NULL;
251 /* Init the fields of F before running fill_insns. */
252 static void
253 init_fence_for_scheduling (fence_t f)
255 FENCE_BNDS (f) = NULL;
256 FENCE_PROCESSED_P (f) = false;
257 FENCE_SCHEDULED_P (f) = false;
260 /* Add new fence consisting of INSN and STATE to the list pointed to by LP. */
261 static void
262 flist_add (flist_t *lp, insn_t insn, state_t state, deps_t dc, void *tc,
263 insn_t last_scheduled_insn, VEC(rtx,gc) *executing_insns,
264 int *ready_ticks, int ready_ticks_size, insn_t sched_next,
265 int cycle, int cycle_issued_insns,
266 bool starts_cycle_p, bool after_stall_p)
268 fence_t f;
270 _list_add (lp);
271 f = FLIST_FENCE (*lp);
273 FENCE_INSN (f) = insn;
275 gcc_assert (state != NULL);
276 FENCE_STATE (f) = state;
278 FENCE_CYCLE (f) = cycle;
279 FENCE_ISSUED_INSNS (f) = cycle_issued_insns;
280 FENCE_STARTS_CYCLE_P (f) = starts_cycle_p;
281 FENCE_AFTER_STALL_P (f) = after_stall_p;
283 gcc_assert (dc != NULL);
284 FENCE_DC (f) = dc;
286 gcc_assert (tc != NULL || targetm.sched.alloc_sched_context == NULL);
287 FENCE_TC (f) = tc;
289 FENCE_LAST_SCHEDULED_INSN (f) = last_scheduled_insn;
290 FENCE_EXECUTING_INSNS (f) = executing_insns;
291 FENCE_READY_TICKS (f) = ready_ticks;
292 FENCE_READY_TICKS_SIZE (f) = ready_ticks_size;
293 FENCE_SCHED_NEXT (f) = sched_next;
295 init_fence_for_scheduling (f);
298 /* Remove the head node of the list pointed to by LP. */
299 static void
300 flist_remove (flist_t *lp)
302 if (FENCE_INSN (FLIST_FENCE (*lp)))
303 fence_clear (FLIST_FENCE (*lp));
304 _list_remove (lp);
307 /* Clear the fence list pointed to by LP. */
308 void
309 flist_clear (flist_t *lp)
311 while (*lp)
312 flist_remove (lp);
315 /* Add ORIGINAL_INSN the def list DL honoring CROSSES_CALL. */
316 void
317 def_list_add (def_list_t *dl, insn_t original_insn, bool crosses_call)
319 def_t d;
321 _list_add (dl);
322 d = DEF_LIST_DEF (*dl);
324 d->orig_insn = original_insn;
325 d->crosses_call = crosses_call;
329 /* Functions to work with target contexts. */
331 /* Bulk target context. It is convenient for debugging purposes to ensure
332 that there are no uninitialized (null) target contexts. */
333 static tc_t bulk_tc = (tc_t) 1;
335 /* Target hooks wrappers. In the future we can provide some default
336 implementations for them. */
338 /* Allocate a store for the target context. */
339 static tc_t
340 alloc_target_context (void)
342 return (targetm.sched.alloc_sched_context
343 ? targetm.sched.alloc_sched_context () : bulk_tc);
346 /* Init target context TC.
347 If CLEAN_P is true, then make TC as it is beginning of the scheduler.
348 Overwise, copy current backend context to TC. */
349 static void
350 init_target_context (tc_t tc, bool clean_p)
352 if (targetm.sched.init_sched_context)
353 targetm.sched.init_sched_context (tc, clean_p);
356 /* Allocate and initialize a target context. Meaning of CLEAN_P is the same as
357 int init_target_context (). */
358 tc_t
359 create_target_context (bool clean_p)
361 tc_t tc = alloc_target_context ();
363 init_target_context (tc, clean_p);
364 return tc;
367 /* Copy TC to the current backend context. */
368 void
369 set_target_context (tc_t tc)
371 if (targetm.sched.set_sched_context)
372 targetm.sched.set_sched_context (tc);
375 /* TC is about to be destroyed. Free any internal data. */
376 static void
377 clear_target_context (tc_t tc)
379 if (targetm.sched.clear_sched_context)
380 targetm.sched.clear_sched_context (tc);
383 /* Clear and free it. */
384 static void
385 delete_target_context (tc_t tc)
387 clear_target_context (tc);
389 if (targetm.sched.free_sched_context)
390 targetm.sched.free_sched_context (tc);
393 /* Make a copy of FROM in TO.
394 NB: May be this should be a hook. */
395 static void
396 copy_target_context (tc_t to, tc_t from)
398 tc_t tmp = create_target_context (false);
400 set_target_context (from);
401 init_target_context (to, false);
403 set_target_context (tmp);
404 delete_target_context (tmp);
407 /* Create a copy of TC. */
408 static tc_t
409 create_copy_of_target_context (tc_t tc)
411 tc_t copy = alloc_target_context ();
413 copy_target_context (copy, tc);
415 return copy;
418 /* Clear TC and initialize it according to CLEAN_P. The meaning of CLEAN_P
419 is the same as in init_target_context (). */
420 void
421 reset_target_context (tc_t tc, bool clean_p)
423 clear_target_context (tc);
424 init_target_context (tc, clean_p);
427 /* Functions to work with dependence contexts.
428 Dc (aka deps context, aka deps_t, aka struct deps *) is short for dependence
429 context. It accumulates information about processed insns to decide if
430 current insn is dependent on the processed ones. */
432 /* Make a copy of FROM in TO. */
433 static void
434 copy_deps_context (deps_t to, deps_t from)
436 init_deps (to);
437 deps_join (to, from);
440 /* Allocate store for dep context. */
441 static deps_t
442 alloc_deps_context (void)
444 return XNEW (struct deps);
447 /* Allocate and initialize dep context. */
448 static deps_t
449 create_deps_context (void)
451 deps_t dc = alloc_deps_context ();
453 init_deps (dc);
454 return dc;
457 /* Create a copy of FROM. */
458 static deps_t
459 create_copy_of_deps_context (deps_t from)
461 deps_t to = alloc_deps_context ();
463 copy_deps_context (to, from);
464 return to;
467 /* Clean up internal data of DC. */
468 static void
469 clear_deps_context (deps_t dc)
471 free_deps (dc);
474 /* Clear and free DC. */
475 static void
476 delete_deps_context (deps_t dc)
478 clear_deps_context (dc);
479 free (dc);
482 /* Clear and init DC. */
483 static void
484 reset_deps_context (deps_t dc)
486 clear_deps_context (dc);
487 init_deps (dc);
490 /* This structure describes the dependence analysis hooks for advancing
491 dependence context. */
492 static struct sched_deps_info_def advance_deps_context_sched_deps_info =
494 NULL,
496 NULL, /* start_insn */
497 NULL, /* finish_insn */
498 NULL, /* start_lhs */
499 NULL, /* finish_lhs */
500 NULL, /* start_rhs */
501 NULL, /* finish_rhs */
502 haifa_note_reg_set,
503 haifa_note_reg_clobber,
504 haifa_note_reg_use,
505 NULL, /* note_mem_dep */
506 NULL, /* note_dep */
508 0, 0, 0
511 /* Process INSN and add its impact on DC. */
512 void
513 advance_deps_context (deps_t dc, insn_t insn)
515 sched_deps_info = &advance_deps_context_sched_deps_info;
516 deps_analyze_insn (dc, insn);
520 /* Functions to work with DFA states. */
522 /* Allocate store for a DFA state. */
523 static state_t
524 state_alloc (void)
526 return xmalloc (dfa_state_size);
529 /* Allocate and initialize DFA state. */
530 static state_t
531 state_create (void)
533 state_t state = state_alloc ();
535 state_reset (state);
536 advance_state (state);
537 return state;
540 /* Free DFA state. */
541 static void
542 state_free (state_t state)
544 free (state);
547 /* Make a copy of FROM in TO. */
548 static void
549 state_copy (state_t to, state_t from)
551 memcpy (to, from, dfa_state_size);
554 /* Create a copy of FROM. */
555 static state_t
556 state_create_copy (state_t from)
558 state_t to = state_alloc ();
560 state_copy (to, from);
561 return to;
565 /* Functions to work with fences. */
567 /* Clear the fence. */
568 static void
569 fence_clear (fence_t f)
571 state_t s = FENCE_STATE (f);
572 deps_t dc = FENCE_DC (f);
573 void *tc = FENCE_TC (f);
575 ilist_clear (&FENCE_BNDS (f));
577 gcc_assert ((s != NULL && dc != NULL && tc != NULL)
578 || (s == NULL && dc == NULL && tc == NULL));
580 if (s != NULL)
581 free (s);
583 if (dc != NULL)
584 delete_deps_context (dc);
586 if (tc != NULL)
587 delete_target_context (tc);
588 VEC_free (rtx, gc, FENCE_EXECUTING_INSNS (f));
589 free (FENCE_READY_TICKS (f));
590 FENCE_READY_TICKS (f) = NULL;
593 /* Init a list of fences with successors of OLD_FENCE. */
594 void
595 init_fences (insn_t old_fence)
597 insn_t succ;
598 succ_iterator si;
599 bool first = true;
600 int ready_ticks_size = get_max_uid () + 1;
602 FOR_EACH_SUCC_1 (succ, si, old_fence,
603 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
606 if (first)
607 first = false;
608 else
609 gcc_assert (flag_sel_sched_pipelining_outer_loops);
611 flist_add (&fences, succ,
612 state_create (),
613 create_deps_context () /* dc */,
614 create_target_context (true) /* tc */,
615 NULL_RTX /* last_scheduled_insn */,
616 NULL, /* executing_insns */
617 XCNEWVEC (int, ready_ticks_size), /* ready_ticks */
618 ready_ticks_size,
619 NULL_RTX /* sched_next */,
620 1 /* cycle */, 0 /* cycle_issued_insns */,
621 1 /* starts_cycle_p */, 0 /* after_stall_p */);
625 /* Merges two fences (filling fields of fence F with resulting values) by
626 following rules: 1) state, target context and last scheduled insn are
627 propagated from fallthrough edge if it is available;
628 2) deps context and cycle is propagated from more probable edge;
629 3) all other fields are set to corresponding constant values.
631 INSN, STATE, DC, TC, LAST_SCHEDULED_INSN, EXECUTING_INSNS,
632 READY_TICKS, READY_TICKS_SIZE, SCHED_NEXT, CYCLE and AFTER_STALL_P
633 are the corresponding fields of the second fence. */
634 static void
635 merge_fences (fence_t f, insn_t insn,
636 state_t state, deps_t dc, void *tc,
637 rtx last_scheduled_insn, VEC(rtx, gc) *executing_insns,
638 int *ready_ticks, int ready_ticks_size,
639 rtx sched_next, int cycle, bool after_stall_p)
641 insn_t last_scheduled_insn_old = FENCE_LAST_SCHEDULED_INSN (f);
643 gcc_assert (sel_bb_head_p (FENCE_INSN (f))
644 && !sched_next && !FENCE_SCHED_NEXT (f));
646 /* Check if we can decide which path fences came.
647 If we can't (or don't want to) - reset all. */
648 if (last_scheduled_insn == NULL
649 || last_scheduled_insn_old == NULL
650 /* This is a case when INSN is reachable on several paths from
651 one insn (this can happen when pipelining of outer loops is on and
652 there are two edges: one going around of inner loop and the other -
653 right through it; in such case just reset everything). */
654 || last_scheduled_insn == last_scheduled_insn_old)
656 state_reset (FENCE_STATE (f));
657 state_free (state);
659 reset_deps_context (FENCE_DC (f));
660 delete_deps_context (dc);
662 reset_target_context (FENCE_TC (f), true);
663 delete_target_context (tc);
665 if (cycle > FENCE_CYCLE (f))
666 FENCE_CYCLE (f) = cycle;
668 FENCE_LAST_SCHEDULED_INSN (f) = NULL;
669 VEC_free (rtx, gc, executing_insns);
670 free (ready_ticks);
671 if (FENCE_EXECUTING_INSNS (f))
672 VEC_block_remove (rtx, FENCE_EXECUTING_INSNS (f), 0,
673 VEC_length (rtx, FENCE_EXECUTING_INSNS (f)));
674 if (FENCE_READY_TICKS (f))
675 memset (FENCE_READY_TICKS (f), 0, FENCE_READY_TICKS_SIZE (f));
677 else
679 edge edge_old = NULL, edge_new = NULL;
680 edge candidate;
681 succ_iterator si;
682 insn_t succ;
684 /* Find fallthrough edge. */
685 gcc_assert (BLOCK_FOR_INSN (insn)->prev_bb);
686 candidate = find_fallthru_edge (BLOCK_FOR_INSN (insn)->prev_bb);
688 if (!candidate
689 || (candidate->src != BLOCK_FOR_INSN (last_scheduled_insn)
690 && candidate->src != BLOCK_FOR_INSN (last_scheduled_insn_old)))
692 /* No fallthrough edge leading to basic block of INSN. */
693 state_reset (FENCE_STATE (f));
694 state_free (state);
696 reset_target_context (FENCE_TC (f), true);
697 delete_target_context (tc);
699 FENCE_LAST_SCHEDULED_INSN (f) = NULL;
701 else
702 if (candidate->src == BLOCK_FOR_INSN (last_scheduled_insn))
704 /* Would be weird if same insn is successor of several fallthrough
705 edges. */
706 gcc_assert (BLOCK_FOR_INSN (insn)->prev_bb
707 != BLOCK_FOR_INSN (last_scheduled_insn_old));
709 state_free (FENCE_STATE (f));
710 FENCE_STATE (f) = state;
712 delete_target_context (FENCE_TC (f));
713 FENCE_TC (f) = tc;
715 FENCE_LAST_SCHEDULED_INSN (f) = last_scheduled_insn;
717 else
719 /* Leave STATE, TC and LAST_SCHEDULED_INSN fields untouched. */
720 state_free (state);
721 delete_target_context (tc);
723 gcc_assert (BLOCK_FOR_INSN (insn)->prev_bb
724 != BLOCK_FOR_INSN (last_scheduled_insn));
727 /* Find edge of first predecessor (last_scheduled_insn_old->insn). */
728 FOR_EACH_SUCC_1 (succ, si, last_scheduled_insn_old,
729 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
731 if (succ == insn)
733 /* No same successor allowed from several edges. */
734 gcc_assert (!edge_old);
735 edge_old = si.e1;
738 /* Find edge of second predecessor (last_scheduled_insn->insn). */
739 FOR_EACH_SUCC_1 (succ, si, last_scheduled_insn,
740 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
742 if (succ == insn)
744 /* No same successor allowed from several edges. */
745 gcc_assert (!edge_new);
746 edge_new = si.e1;
750 /* Check if we can choose most probable predecessor. */
751 if (edge_old == NULL || edge_new == NULL)
753 reset_deps_context (FENCE_DC (f));
754 delete_deps_context (dc);
755 VEC_free (rtx, gc, executing_insns);
756 free (ready_ticks);
758 FENCE_CYCLE (f) = MAX (FENCE_CYCLE (f), cycle);
759 if (FENCE_EXECUTING_INSNS (f))
760 VEC_block_remove (rtx, FENCE_EXECUTING_INSNS (f), 0,
761 VEC_length (rtx, FENCE_EXECUTING_INSNS (f)));
762 if (FENCE_READY_TICKS (f))
763 memset (FENCE_READY_TICKS (f), 0, FENCE_READY_TICKS_SIZE (f));
765 else
766 if (edge_new->probability > edge_old->probability)
768 delete_deps_context (FENCE_DC (f));
769 FENCE_DC (f) = dc;
770 VEC_free (rtx, gc, FENCE_EXECUTING_INSNS (f));
771 FENCE_EXECUTING_INSNS (f) = executing_insns;
772 free (FENCE_READY_TICKS (f));
773 FENCE_READY_TICKS (f) = ready_ticks;
774 FENCE_READY_TICKS_SIZE (f) = ready_ticks_size;
775 FENCE_CYCLE (f) = cycle;
777 else
779 /* Leave DC and CYCLE untouched. */
780 delete_deps_context (dc);
781 VEC_free (rtx, gc, executing_insns);
782 free (ready_ticks);
786 /* Fill remaining invariant fields. */
787 if (after_stall_p)
788 FENCE_AFTER_STALL_P (f) = 1;
790 FENCE_ISSUED_INSNS (f) = 0;
791 FENCE_STARTS_CYCLE_P (f) = 1;
792 FENCE_SCHED_NEXT (f) = NULL;
795 /* Add a new fence to NEW_FENCES list, initializing it from all
796 other parameters. */
797 static void
798 add_to_fences (flist_tail_t new_fences, insn_t insn,
799 state_t state, deps_t dc, void *tc, rtx last_scheduled_insn,
800 VEC(rtx, gc) *executing_insns, int *ready_ticks,
801 int ready_ticks_size, rtx sched_next, int cycle,
802 int cycle_issued_insns, bool starts_cycle_p, bool after_stall_p)
804 fence_t f = flist_lookup (FLIST_TAIL_HEAD (new_fences), insn);
806 if (! f)
808 flist_add (FLIST_TAIL_TAILP (new_fences), insn, state, dc, tc,
809 last_scheduled_insn, executing_insns, ready_ticks,
810 ready_ticks_size, sched_next, cycle, cycle_issued_insns,
811 starts_cycle_p, after_stall_p);
813 FLIST_TAIL_TAILP (new_fences)
814 = &FLIST_NEXT (*FLIST_TAIL_TAILP (new_fences));
816 else
818 merge_fences (f, insn, state, dc, tc, last_scheduled_insn,
819 executing_insns, ready_ticks, ready_ticks_size,
820 sched_next, cycle, after_stall_p);
824 /* Move the first fence in the OLD_FENCES list to NEW_FENCES. */
825 void
826 move_fence_to_fences (flist_t old_fences, flist_tail_t new_fences)
828 fence_t f, old;
829 flist_t *tailp = FLIST_TAIL_TAILP (new_fences);
831 old = FLIST_FENCE (old_fences);
832 f = flist_lookup (FLIST_TAIL_HEAD (new_fences),
833 FENCE_INSN (FLIST_FENCE (old_fences)));
834 if (f)
836 merge_fences (f, old->insn, old->state, old->dc, old->tc,
837 old->last_scheduled_insn, old->executing_insns,
838 old->ready_ticks, old->ready_ticks_size,
839 old->sched_next, old->cycle,
840 old->after_stall_p);
842 else
844 _list_add (tailp);
845 FLIST_TAIL_TAILP (new_fences) = &FLIST_NEXT (*tailp);
846 *FLIST_FENCE (*tailp) = *old;
847 init_fence_for_scheduling (FLIST_FENCE (*tailp));
849 FENCE_INSN (old) = NULL;
852 /* Add a new fence to NEW_FENCES list and initialize most of its data
853 as a clean one. */
854 void
855 add_clean_fence_to_fences (flist_tail_t new_fences, insn_t succ, fence_t fence)
857 int ready_ticks_size = get_max_uid () + 1;
859 add_to_fences (new_fences,
860 succ, state_create (), create_deps_context (),
861 create_target_context (true),
862 NULL_RTX, NULL,
863 XCNEWVEC (int, ready_ticks_size), ready_ticks_size,
864 NULL_RTX, FENCE_CYCLE (fence) + 1,
865 0, 1, FENCE_AFTER_STALL_P (fence));
868 /* Add a new fence to NEW_FENCES list and initialize all of its data
869 from FENCE and SUCC. */
870 void
871 add_dirty_fence_to_fences (flist_tail_t new_fences, insn_t succ, fence_t fence)
873 int * new_ready_ticks
874 = XNEWVEC (int, FENCE_READY_TICKS_SIZE (fence));
876 memcpy (new_ready_ticks, FENCE_READY_TICKS (fence),
877 FENCE_READY_TICKS_SIZE (fence) * sizeof (int));
878 add_to_fences (new_fences,
879 succ, state_create_copy (FENCE_STATE (fence)),
880 create_copy_of_deps_context (FENCE_DC (fence)),
881 create_copy_of_target_context (FENCE_TC (fence)),
882 FENCE_LAST_SCHEDULED_INSN (fence),
883 VEC_copy (rtx, gc, FENCE_EXECUTING_INSNS (fence)),
884 new_ready_ticks,
885 FENCE_READY_TICKS_SIZE (fence),
886 FENCE_SCHED_NEXT (fence),
887 FENCE_CYCLE (fence),
888 FENCE_ISSUED_INSNS (fence),
889 FENCE_STARTS_CYCLE_P (fence),
890 FENCE_AFTER_STALL_P (fence));
894 /* Functions to work with regset and nop pools. */
896 /* Returns the new regset from pool. It might have some of the bits set
897 from the previous usage. */
898 regset
899 get_regset_from_pool (void)
901 regset rs;
903 if (regset_pool.n != 0)
904 rs = regset_pool.v[--regset_pool.n];
905 else
906 /* We need to create the regset. */
908 rs = ALLOC_REG_SET (&reg_obstack);
910 if (regset_pool.nn == regset_pool.ss)
911 regset_pool.vv = XRESIZEVEC (regset, regset_pool.vv,
912 (regset_pool.ss = 2 * regset_pool.ss + 1));
913 regset_pool.vv[regset_pool.nn++] = rs;
916 regset_pool.diff++;
918 return rs;
921 /* Same as above, but returns the empty regset. */
922 regset
923 get_clear_regset_from_pool (void)
925 regset rs = get_regset_from_pool ();
927 CLEAR_REG_SET (rs);
928 return rs;
931 /* Return regset RS to the pool for future use. */
932 void
933 return_regset_to_pool (regset rs)
935 regset_pool.diff--;
937 if (regset_pool.n == regset_pool.s)
938 regset_pool.v = XRESIZEVEC (regset, regset_pool.v,
939 (regset_pool.s = 2 * regset_pool.s + 1));
940 regset_pool.v[regset_pool.n++] = rs;
943 #ifdef ENABLE_CHECKING
944 /* This is used as a qsort callback for sorting regset pool stacks.
945 X and XX are addresses of two regsets. They are never equal. */
946 static int
947 cmp_v_in_regset_pool (const void *x, const void *xx)
949 return *((const regset *) x) - *((const regset *) xx);
951 #endif
953 /* Free the regset pool possibly checking for memory leaks. */
954 void
955 free_regset_pool (void)
957 #ifdef ENABLE_CHECKING
959 regset *v = regset_pool.v;
960 int i = 0;
961 int n = regset_pool.n;
963 regset *vv = regset_pool.vv;
964 int ii = 0;
965 int nn = regset_pool.nn;
967 int diff = 0;
969 gcc_assert (n <= nn);
971 /* Sort both vectors so it will be possible to compare them. */
972 qsort (v, n, sizeof (*v), cmp_v_in_regset_pool);
973 qsort (vv, nn, sizeof (*vv), cmp_v_in_regset_pool);
975 while (ii < nn)
977 if (v[i] == vv[ii])
978 i++;
979 else
980 /* VV[II] was lost. */
981 diff++;
983 ii++;
986 gcc_assert (diff == regset_pool.diff);
988 #endif
990 /* If not true - we have a memory leak. */
991 gcc_assert (regset_pool.diff == 0);
993 while (regset_pool.n)
995 --regset_pool.n;
996 FREE_REG_SET (regset_pool.v[regset_pool.n]);
999 free (regset_pool.v);
1000 regset_pool.v = NULL;
1001 regset_pool.s = 0;
1003 free (regset_pool.vv);
1004 regset_pool.vv = NULL;
1005 regset_pool.nn = 0;
1006 regset_pool.ss = 0;
1008 regset_pool.diff = 0;
1012 /* Functions to work with nop pools. NOP insns are used as temporary
1013 placeholders of the insns being scheduled to allow correct update of
1014 the data sets. When update is finished, NOPs are deleted. */
1016 /* A vinsn that is used to represent a nop. This vinsn is shared among all
1017 nops sel-sched generates. */
1018 static vinsn_t nop_vinsn = NULL;
1020 /* Emit a nop before INSN, taking it from pool. */
1021 insn_t
1022 get_nop_from_pool (insn_t insn)
1024 insn_t nop;
1025 bool old_p = nop_pool.n != 0;
1026 int flags;
1028 if (old_p)
1029 nop = nop_pool.v[--nop_pool.n];
1030 else
1031 nop = nop_pattern;
1033 nop = emit_insn_before (nop, insn);
1035 if (old_p)
1036 flags = INSN_INIT_TODO_SSID;
1037 else
1038 flags = INSN_INIT_TODO_LUID | INSN_INIT_TODO_SSID;
1040 set_insn_init (INSN_EXPR (insn), nop_vinsn, INSN_SEQNO (insn));
1041 sel_init_new_insn (nop, flags);
1043 return nop;
1046 /* Remove NOP from the instruction stream and return it to the pool. */
1047 void
1048 return_nop_to_pool (insn_t nop, bool full_tidying)
1050 gcc_assert (INSN_IN_STREAM_P (nop));
1051 sel_remove_insn (nop, false, full_tidying);
1053 if (nop_pool.n == nop_pool.s)
1054 nop_pool.v = XRESIZEVEC (rtx, nop_pool.v,
1055 (nop_pool.s = 2 * nop_pool.s + 1));
1056 nop_pool.v[nop_pool.n++] = nop;
1059 /* Free the nop pool. */
1060 void
1061 free_nop_pool (void)
1063 nop_pool.n = 0;
1064 nop_pool.s = 0;
1065 free (nop_pool.v);
1066 nop_pool.v = NULL;
1070 /* Skip unspec to support ia64 speculation. Called from rtx_equal_p_cb.
1071 The callback is given two rtxes XX and YY and writes the new rtxes
1072 to NX and NY in case some needs to be skipped. */
1073 static int
1074 skip_unspecs_callback (const_rtx *xx, const_rtx *yy, rtx *nx, rtx* ny)
1076 const_rtx x = *xx;
1077 const_rtx y = *yy;
1079 if (GET_CODE (x) == UNSPEC
1080 && (targetm.sched.skip_rtx_p == NULL
1081 || targetm.sched.skip_rtx_p (x)))
1083 *nx = XVECEXP (x, 0, 0);
1084 *ny = CONST_CAST_RTX (y);
1085 return 1;
1088 if (GET_CODE (y) == UNSPEC
1089 && (targetm.sched.skip_rtx_p == NULL
1090 || targetm.sched.skip_rtx_p (y)))
1092 *nx = CONST_CAST_RTX (x);
1093 *ny = XVECEXP (y, 0, 0);
1094 return 1;
1097 return 0;
1100 /* Callback, called from hash_rtx_cb. Helps to hash UNSPEC rtx X in a correct way
1101 to support ia64 speculation. When changes are needed, new rtx X and new mode
1102 NMODE are written, and the callback returns true. */
1103 static int
1104 hash_with_unspec_callback (const_rtx x, enum machine_mode mode ATTRIBUTE_UNUSED,
1105 rtx *nx, enum machine_mode* nmode)
1107 if (GET_CODE (x) == UNSPEC
1108 && targetm.sched.skip_rtx_p
1109 && targetm.sched.skip_rtx_p (x))
1111 *nx = XVECEXP (x, 0 ,0);
1112 *nmode = VOIDmode;
1113 return 1;
1116 return 0;
1119 /* Returns LHS and RHS are ok to be scheduled separately. */
1120 static bool
1121 lhs_and_rhs_separable_p (rtx lhs, rtx rhs)
1123 if (lhs == NULL || rhs == NULL)
1124 return false;
1126 /* Do not schedule CONST, CONST_INT and CONST_DOUBLE etc as rhs: no point
1127 to use reg, if const can be used. Moreover, scheduling const as rhs may
1128 lead to mode mismatch cause consts don't have modes but they could be
1129 merged from branches where the same const used in different modes. */
1130 if (CONSTANT_P (rhs))
1131 return false;
1133 /* ??? Do not rename predicate registers to avoid ICEs in bundling. */
1134 if (COMPARISON_P (rhs))
1135 return false;
1137 /* Do not allow single REG to be an rhs. */
1138 if (REG_P (rhs))
1139 return false;
1141 /* See comment at find_used_regs_1 (*1) for explanation of this
1142 restriction. */
1143 /* FIXME: remove this later. */
1144 if (MEM_P (lhs))
1145 return false;
1147 /* This will filter all tricky things like ZERO_EXTRACT etc.
1148 For now we don't handle it. */
1149 if (!REG_P (lhs) && !MEM_P (lhs))
1150 return false;
1152 return true;
1155 /* Initialize vinsn VI for INSN. Only for use from vinsn_create (). When
1156 FORCE_UNIQUE_P is true, the resulting vinsn will not be clonable. This is
1157 used e.g. for insns from recovery blocks. */
1158 static void
1159 vinsn_init (vinsn_t vi, insn_t insn, bool force_unique_p)
1161 hash_rtx_callback_function hrcf;
1162 int insn_class;
1164 VINSN_INSN_RTX (vi) = insn;
1165 VINSN_COUNT (vi) = 0;
1166 vi->cost = -1;
1168 if (DF_INSN_UID_SAFE_GET (INSN_UID (insn)) != NULL)
1169 init_id_from_df (VINSN_ID (vi), insn, force_unique_p);
1170 else
1171 deps_init_id (VINSN_ID (vi), insn, force_unique_p);
1173 /* Hash vinsn depending on whether it is separable or not. */
1174 hrcf = targetm.sched.skip_rtx_p ? hash_with_unspec_callback : NULL;
1175 if (VINSN_SEPARABLE_P (vi))
1177 rtx rhs = VINSN_RHS (vi);
1179 VINSN_HASH (vi) = hash_rtx_cb (rhs, GET_MODE (rhs),
1180 NULL, NULL, false, hrcf);
1181 VINSN_HASH_RTX (vi) = hash_rtx_cb (VINSN_PATTERN (vi),
1182 VOIDmode, NULL, NULL,
1183 false, hrcf);
1185 else
1187 VINSN_HASH (vi) = hash_rtx_cb (VINSN_PATTERN (vi), VOIDmode,
1188 NULL, NULL, false, hrcf);
1189 VINSN_HASH_RTX (vi) = VINSN_HASH (vi);
1192 insn_class = haifa_classify_insn (insn);
1193 if (insn_class >= 2
1194 && (!targetm.sched.get_insn_spec_ds
1195 || ((targetm.sched.get_insn_spec_ds (insn) & BEGIN_CONTROL)
1196 == 0)))
1197 VINSN_MAY_TRAP_P (vi) = true;
1198 else
1199 VINSN_MAY_TRAP_P (vi) = false;
1202 /* Indicate that VI has become the part of an rtx object. */
1203 void
1204 vinsn_attach (vinsn_t vi)
1206 /* Assert that VI is not pending for deletion. */
1207 gcc_assert (VINSN_INSN_RTX (vi));
1209 VINSN_COUNT (vi)++;
1212 /* Create and init VI from the INSN. Use UNIQUE_P for determining the correct
1213 VINSN_TYPE (VI). */
1214 static vinsn_t
1215 vinsn_create (insn_t insn, bool force_unique_p)
1217 vinsn_t vi = XCNEW (struct vinsn_def);
1219 vinsn_init (vi, insn, force_unique_p);
1220 return vi;
1223 /* Return a copy of VI. When REATTACH_P is true, detach VI and attach
1224 the copy. */
1225 vinsn_t
1226 vinsn_copy (vinsn_t vi, bool reattach_p)
1228 rtx copy;
1229 bool unique = VINSN_UNIQUE_P (vi);
1230 vinsn_t new_vi;
1232 copy = create_copy_of_insn_rtx (VINSN_INSN_RTX (vi));
1233 new_vi = create_vinsn_from_insn_rtx (copy, unique);
1234 if (reattach_p)
1236 vinsn_detach (vi);
1237 vinsn_attach (new_vi);
1240 return new_vi;
1243 /* Delete the VI vinsn and free its data. */
1244 static void
1245 vinsn_delete (vinsn_t vi)
1247 gcc_assert (VINSN_COUNT (vi) == 0);
1249 return_regset_to_pool (VINSN_REG_SETS (vi));
1250 return_regset_to_pool (VINSN_REG_USES (vi));
1251 return_regset_to_pool (VINSN_REG_CLOBBERS (vi));
1253 free (vi);
1256 /* Indicate that VI is no longer a part of some rtx object.
1257 Remove VI if it is no longer needed. */
1258 void
1259 vinsn_detach (vinsn_t vi)
1261 gcc_assert (VINSN_COUNT (vi) > 0);
1263 if (--VINSN_COUNT (vi) == 0)
1264 vinsn_delete (vi);
1267 /* Returns TRUE if VI is a branch. */
1268 bool
1269 vinsn_cond_branch_p (vinsn_t vi)
1271 insn_t insn;
1273 if (!VINSN_UNIQUE_P (vi))
1274 return false;
1276 insn = VINSN_INSN_RTX (vi);
1277 if (BB_END (BLOCK_FOR_INSN (insn)) != insn)
1278 return false;
1280 return control_flow_insn_p (insn);
1283 /* Return latency of INSN. */
1284 static int
1285 sel_insn_rtx_cost (rtx insn)
1287 int cost;
1289 /* A USE insn, or something else we don't need to
1290 understand. We can't pass these directly to
1291 result_ready_cost or insn_default_latency because it will
1292 trigger a fatal error for unrecognizable insns. */
1293 if (recog_memoized (insn) < 0)
1294 cost = 0;
1295 else
1297 cost = insn_default_latency (insn);
1299 if (cost < 0)
1300 cost = 0;
1303 return cost;
1306 /* Return the cost of the VI.
1307 !!! FIXME: Unify with haifa-sched.c: insn_cost (). */
1309 sel_vinsn_cost (vinsn_t vi)
1311 int cost = vi->cost;
1313 if (cost < 0)
1315 cost = sel_insn_rtx_cost (VINSN_INSN_RTX (vi));
1316 vi->cost = cost;
1319 return cost;
1323 /* Functions for insn emitting. */
1325 /* Emit new insn after AFTER based on PATTERN and initialize its data from
1326 EXPR and SEQNO. */
1327 insn_t
1328 sel_gen_insn_from_rtx_after (rtx pattern, expr_t expr, int seqno, insn_t after)
1330 insn_t new_insn;
1332 gcc_assert (EXPR_TARGET_AVAILABLE (expr) == true);
1334 new_insn = emit_insn_after (pattern, after);
1335 set_insn_init (expr, NULL, seqno);
1336 sel_init_new_insn (new_insn, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SSID);
1338 return new_insn;
1341 /* Force newly generated vinsns to be unique. */
1342 static bool init_insn_force_unique_p = false;
1344 /* Emit new speculation recovery insn after AFTER based on PATTERN and
1345 initialize its data from EXPR and SEQNO. */
1346 insn_t
1347 sel_gen_recovery_insn_from_rtx_after (rtx pattern, expr_t expr, int seqno,
1348 insn_t after)
1350 insn_t insn;
1352 gcc_assert (!init_insn_force_unique_p);
1354 init_insn_force_unique_p = true;
1355 insn = sel_gen_insn_from_rtx_after (pattern, expr, seqno, after);
1356 CANT_MOVE (insn) = 1;
1357 init_insn_force_unique_p = false;
1359 return insn;
1362 /* Emit new insn after AFTER based on EXPR and SEQNO. If VINSN is not NULL,
1363 take it as a new vinsn instead of EXPR's vinsn.
1364 We simplify insns later, after scheduling region in
1365 simplify_changed_insns. */
1366 insn_t
1367 sel_gen_insn_from_expr_after (expr_t expr, vinsn_t vinsn, int seqno,
1368 insn_t after)
1370 expr_t emit_expr;
1371 insn_t insn;
1372 int flags;
1374 emit_expr = set_insn_init (expr, vinsn ? vinsn : EXPR_VINSN (expr),
1375 seqno);
1376 insn = EXPR_INSN_RTX (emit_expr);
1377 add_insn_after (insn, after, BLOCK_FOR_INSN (insn));
1379 flags = INSN_INIT_TODO_SSID;
1380 if (INSN_LUID (insn) == 0)
1381 flags |= INSN_INIT_TODO_LUID;
1382 sel_init_new_insn (insn, flags);
1384 return insn;
1387 /* Move insn from EXPR after AFTER. */
1388 insn_t
1389 sel_move_insn (expr_t expr, int seqno, insn_t after)
1391 insn_t insn = EXPR_INSN_RTX (expr);
1392 basic_block bb = BLOCK_FOR_INSN (after);
1393 insn_t next = NEXT_INSN (after);
1395 /* Assert that in move_op we disconnected this insn properly. */
1396 gcc_assert (EXPR_VINSN (INSN_EXPR (insn)) != NULL);
1397 PREV_INSN (insn) = after;
1398 NEXT_INSN (insn) = next;
1400 NEXT_INSN (after) = insn;
1401 PREV_INSN (next) = insn;
1403 /* Update links from insn to bb and vice versa. */
1404 df_insn_change_bb (insn, bb);
1405 if (BB_END (bb) == after)
1406 BB_END (bb) = insn;
1408 prepare_insn_expr (insn, seqno);
1409 return insn;
1413 /* Functions to work with right-hand sides. */
1415 /* Search for a hash value determined by UID/NEW_VINSN in a sorted vector
1416 VECT and return true when found. Use NEW_VINSN for comparison only when
1417 COMPARE_VINSNS is true. Write to INDP the index on which
1418 the search has stopped, such that inserting the new element at INDP will
1419 retain VECT's sort order. */
1420 static bool
1421 find_in_history_vect_1 (VEC(expr_history_def, heap) *vect,
1422 unsigned uid, vinsn_t new_vinsn,
1423 bool compare_vinsns, int *indp)
1425 expr_history_def *arr;
1426 int i, j, len = VEC_length (expr_history_def, vect);
1428 if (len == 0)
1430 *indp = 0;
1431 return false;
1434 arr = VEC_address (expr_history_def, vect);
1435 i = 0, j = len - 1;
1437 while (i <= j)
1439 unsigned auid = arr[i].uid;
1440 vinsn_t avinsn = arr[i].new_expr_vinsn;
1442 if (auid == uid
1443 /* When undoing transformation on a bookkeeping copy, the new vinsn
1444 may not be exactly equal to the one that is saved in the vector.
1445 This is because the insn whose copy we're checking was possibly
1446 substituted itself. */
1447 && (! compare_vinsns
1448 || vinsn_equal_p (avinsn, new_vinsn)))
1450 *indp = i;
1451 return true;
1453 else if (auid > uid)
1454 break;
1455 i++;
1458 *indp = i;
1459 return false;
1462 /* Search for a uid of INSN and NEW_VINSN in a sorted vector VECT. Return
1463 the position found or -1, if no such value is in vector.
1464 Search also for UIDs of insn's originators, if ORIGINATORS_P is true. */
1466 find_in_history_vect (VEC(expr_history_def, heap) *vect, rtx insn,
1467 vinsn_t new_vinsn, bool originators_p)
1469 int ind;
1471 if (find_in_history_vect_1 (vect, INSN_UID (insn), new_vinsn,
1472 false, &ind))
1473 return ind;
1475 if (INSN_ORIGINATORS (insn) && originators_p)
1477 unsigned uid;
1478 bitmap_iterator bi;
1480 EXECUTE_IF_SET_IN_BITMAP (INSN_ORIGINATORS (insn), 0, uid, bi)
1481 if (find_in_history_vect_1 (vect, uid, new_vinsn, false, &ind))
1482 return ind;
1485 return -1;
1488 /* Insert new element in a sorted history vector pointed to by PVECT,
1489 if it is not there already. The element is searched using
1490 UID/NEW_EXPR_VINSN pair. TYPE, OLD_EXPR_VINSN and SPEC_DS save
1491 the history of a transformation. */
1492 void
1493 insert_in_history_vect (VEC (expr_history_def, heap) **pvect,
1494 unsigned uid, enum local_trans_type type,
1495 vinsn_t old_expr_vinsn, vinsn_t new_expr_vinsn,
1496 ds_t spec_ds)
1498 VEC(expr_history_def, heap) *vect = *pvect;
1499 expr_history_def temp;
1500 bool res;
1501 int ind;
1503 res = find_in_history_vect_1 (vect, uid, new_expr_vinsn, true, &ind);
1505 if (res)
1507 expr_history_def *phist = VEC_index (expr_history_def, vect, ind);
1509 /* It is possible that speculation types of expressions that were
1510 propagated through different paths will be different here. In this
1511 case, merge the status to get the correct check later. */
1512 if (phist->spec_ds != spec_ds)
1513 phist->spec_ds = ds_max_merge (phist->spec_ds, spec_ds);
1514 return;
1517 temp.uid = uid;
1518 temp.old_expr_vinsn = old_expr_vinsn;
1519 temp.new_expr_vinsn = new_expr_vinsn;
1520 temp.spec_ds = spec_ds;
1521 temp.type = type;
1523 vinsn_attach (old_expr_vinsn);
1524 vinsn_attach (new_expr_vinsn);
1525 VEC_safe_insert (expr_history_def, heap, vect, ind, &temp);
1526 *pvect = vect;
1529 /* Free history vector PVECT. */
1530 static void
1531 free_history_vect (VEC (expr_history_def, heap) **pvect)
1533 unsigned i;
1534 expr_history_def *phist;
1536 if (! *pvect)
1537 return;
1539 for (i = 0;
1540 VEC_iterate (expr_history_def, *pvect, i, phist);
1541 i++)
1543 vinsn_detach (phist->old_expr_vinsn);
1544 vinsn_detach (phist->new_expr_vinsn);
1547 VEC_free (expr_history_def, heap, *pvect);
1548 *pvect = NULL;
1552 /* Compare two vinsns as rhses if possible and as vinsns otherwise. */
1553 bool
1554 vinsn_equal_p (vinsn_t x, vinsn_t y)
1556 rtx_equal_p_callback_function repcf;
1558 if (x == y)
1559 return true;
1561 if (VINSN_TYPE (x) != VINSN_TYPE (y))
1562 return false;
1564 if (VINSN_HASH (x) != VINSN_HASH (y))
1565 return false;
1567 repcf = targetm.sched.skip_rtx_p ? skip_unspecs_callback : NULL;
1568 if (VINSN_SEPARABLE_P (x))
1570 /* Compare RHSes of VINSNs. */
1571 gcc_assert (VINSN_RHS (x));
1572 gcc_assert (VINSN_RHS (y));
1574 return rtx_equal_p_cb (VINSN_RHS (x), VINSN_RHS (y), repcf);
1577 return rtx_equal_p_cb (VINSN_PATTERN (x), VINSN_PATTERN (y), repcf);
1581 /* Functions for working with expressions. */
1583 /* Initialize EXPR. */
1584 static void
1585 init_expr (expr_t expr, vinsn_t vi, int spec, int use, int priority,
1586 int sched_times, int orig_bb_index, ds_t spec_done_ds,
1587 ds_t spec_to_check_ds, int orig_sched_cycle,
1588 VEC(expr_history_def, heap) *history, bool target_available,
1589 bool was_substituted, bool was_renamed, bool needs_spec_check_p,
1590 bool cant_move)
1592 vinsn_attach (vi);
1594 EXPR_VINSN (expr) = vi;
1595 EXPR_SPEC (expr) = spec;
1596 EXPR_USEFULNESS (expr) = use;
1597 EXPR_PRIORITY (expr) = priority;
1598 EXPR_PRIORITY_ADJ (expr) = 0;
1599 EXPR_SCHED_TIMES (expr) = sched_times;
1600 EXPR_ORIG_BB_INDEX (expr) = orig_bb_index;
1601 EXPR_ORIG_SCHED_CYCLE (expr) = orig_sched_cycle;
1602 EXPR_SPEC_DONE_DS (expr) = spec_done_ds;
1603 EXPR_SPEC_TO_CHECK_DS (expr) = spec_to_check_ds;
1605 if (history)
1606 EXPR_HISTORY_OF_CHANGES (expr) = history;
1607 else
1608 EXPR_HISTORY_OF_CHANGES (expr) = NULL;
1610 EXPR_TARGET_AVAILABLE (expr) = target_available;
1611 EXPR_WAS_SUBSTITUTED (expr) = was_substituted;
1612 EXPR_WAS_RENAMED (expr) = was_renamed;
1613 EXPR_NEEDS_SPEC_CHECK_P (expr) = needs_spec_check_p;
1614 EXPR_CANT_MOVE (expr) = cant_move;
1617 /* Make a copy of the expr FROM into the expr TO. */
1618 void
1619 copy_expr (expr_t to, expr_t from)
1621 VEC(expr_history_def, heap) *temp = NULL;
1623 if (EXPR_HISTORY_OF_CHANGES (from))
1625 unsigned i;
1626 expr_history_def *phist;
1628 temp = VEC_copy (expr_history_def, heap, EXPR_HISTORY_OF_CHANGES (from));
1629 for (i = 0;
1630 VEC_iterate (expr_history_def, temp, i, phist);
1631 i++)
1633 vinsn_attach (phist->old_expr_vinsn);
1634 vinsn_attach (phist->new_expr_vinsn);
1638 init_expr (to, EXPR_VINSN (from), EXPR_SPEC (from),
1639 EXPR_USEFULNESS (from), EXPR_PRIORITY (from),
1640 EXPR_SCHED_TIMES (from), EXPR_ORIG_BB_INDEX (from),
1641 EXPR_SPEC_DONE_DS (from), EXPR_SPEC_TO_CHECK_DS (from),
1642 EXPR_ORIG_SCHED_CYCLE (from), temp,
1643 EXPR_TARGET_AVAILABLE (from), EXPR_WAS_SUBSTITUTED (from),
1644 EXPR_WAS_RENAMED (from), EXPR_NEEDS_SPEC_CHECK_P (from),
1645 EXPR_CANT_MOVE (from));
1648 /* Same, but the final expr will not ever be in av sets, so don't copy
1649 "uninteresting" data such as bitmap cache. */
1650 void
1651 copy_expr_onside (expr_t to, expr_t from)
1653 init_expr (to, EXPR_VINSN (from), EXPR_SPEC (from), EXPR_USEFULNESS (from),
1654 EXPR_PRIORITY (from), EXPR_SCHED_TIMES (from), 0,
1655 EXPR_SPEC_DONE_DS (from), EXPR_SPEC_TO_CHECK_DS (from), 0, NULL,
1656 EXPR_TARGET_AVAILABLE (from), EXPR_WAS_SUBSTITUTED (from),
1657 EXPR_WAS_RENAMED (from), EXPR_NEEDS_SPEC_CHECK_P (from),
1658 EXPR_CANT_MOVE (from));
1661 /* Prepare the expr of INSN for scheduling. Used when moving insn and when
1662 initializing new insns. */
1663 static void
1664 prepare_insn_expr (insn_t insn, int seqno)
1666 expr_t expr = INSN_EXPR (insn);
1667 ds_t ds;
1669 INSN_SEQNO (insn) = seqno;
1670 EXPR_ORIG_BB_INDEX (expr) = BLOCK_NUM (insn);
1671 EXPR_SPEC (expr) = 0;
1672 EXPR_ORIG_SCHED_CYCLE (expr) = 0;
1673 EXPR_WAS_SUBSTITUTED (expr) = 0;
1674 EXPR_WAS_RENAMED (expr) = 0;
1675 EXPR_TARGET_AVAILABLE (expr) = 1;
1676 INSN_LIVE_VALID_P (insn) = false;
1678 /* ??? If this expression is speculative, make its dependence
1679 as weak as possible. We can filter this expression later
1680 in process_spec_exprs, because we do not distinguish
1681 between the status we got during compute_av_set and the
1682 existing status. To be fixed. */
1683 ds = EXPR_SPEC_DONE_DS (expr);
1684 if (ds)
1685 EXPR_SPEC_DONE_DS (expr) = ds_get_max_dep_weak (ds);
1687 free_history_vect (&EXPR_HISTORY_OF_CHANGES (expr));
1690 /* Update target_available bits when merging exprs TO and FROM. SPLIT_POINT
1691 is non-null when expressions are merged from different successors at
1692 a split point. */
1693 static void
1694 update_target_availability (expr_t to, expr_t from, insn_t split_point)
1696 if (EXPR_TARGET_AVAILABLE (to) < 0
1697 || EXPR_TARGET_AVAILABLE (from) < 0)
1698 EXPR_TARGET_AVAILABLE (to) = -1;
1699 else
1701 /* We try to detect the case when one of the expressions
1702 can only be reached through another one. In this case,
1703 we can do better. */
1704 if (split_point == NULL)
1706 int toind, fromind;
1708 toind = EXPR_ORIG_BB_INDEX (to);
1709 fromind = EXPR_ORIG_BB_INDEX (from);
1711 if (toind && toind == fromind)
1712 /* Do nothing -- everything is done in
1713 merge_with_other_exprs. */
1715 else
1716 EXPR_TARGET_AVAILABLE (to) = -1;
1718 else
1719 EXPR_TARGET_AVAILABLE (to) &= EXPR_TARGET_AVAILABLE (from);
1723 /* Update speculation bits when merging exprs TO and FROM. SPLIT_POINT
1724 is non-null when expressions are merged from different successors at
1725 a split point. */
1726 static void
1727 update_speculative_bits (expr_t to, expr_t from, insn_t split_point)
1729 ds_t old_to_ds, old_from_ds;
1731 old_to_ds = EXPR_SPEC_DONE_DS (to);
1732 old_from_ds = EXPR_SPEC_DONE_DS (from);
1734 EXPR_SPEC_DONE_DS (to) = ds_max_merge (old_to_ds, old_from_ds);
1735 EXPR_SPEC_TO_CHECK_DS (to) |= EXPR_SPEC_TO_CHECK_DS (from);
1736 EXPR_NEEDS_SPEC_CHECK_P (to) |= EXPR_NEEDS_SPEC_CHECK_P (from);
1738 /* When merging e.g. control & data speculative exprs, or a control
1739 speculative with a control&data speculative one, we really have
1740 to change vinsn too. Also, when speculative status is changed,
1741 we also need to record this as a transformation in expr's history. */
1742 if ((old_to_ds & SPECULATIVE) || (old_from_ds & SPECULATIVE))
1744 old_to_ds = ds_get_speculation_types (old_to_ds);
1745 old_from_ds = ds_get_speculation_types (old_from_ds);
1747 if (old_to_ds != old_from_ds)
1749 ds_t record_ds;
1751 /* When both expressions are speculative, we need to change
1752 the vinsn first. */
1753 if ((old_to_ds & SPECULATIVE) && (old_from_ds & SPECULATIVE))
1755 int res;
1757 res = speculate_expr (to, EXPR_SPEC_DONE_DS (to));
1758 gcc_assert (res >= 0);
1761 if (split_point != NULL)
1763 /* Record the change with proper status. */
1764 record_ds = EXPR_SPEC_DONE_DS (to) & SPECULATIVE;
1765 record_ds &= ~(old_to_ds & SPECULATIVE);
1766 record_ds &= ~(old_from_ds & SPECULATIVE);
1768 insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (to),
1769 INSN_UID (split_point), TRANS_SPECULATION,
1770 EXPR_VINSN (from), EXPR_VINSN (to),
1771 record_ds);
1778 /* Merge bits of FROM expr to TO expr. When SPLIT_POINT is not NULL,
1779 this is done along different paths. */
1780 void
1781 merge_expr_data (expr_t to, expr_t from, insn_t split_point)
1783 int i;
1784 expr_history_def *phist;
1786 /* For now, we just set the spec of resulting expr to be minimum of the specs
1787 of merged exprs. */
1788 if (EXPR_SPEC (to) > EXPR_SPEC (from))
1789 EXPR_SPEC (to) = EXPR_SPEC (from);
1791 if (split_point)
1792 EXPR_USEFULNESS (to) += EXPR_USEFULNESS (from);
1793 else
1794 EXPR_USEFULNESS (to) = MAX (EXPR_USEFULNESS (to),
1795 EXPR_USEFULNESS (from));
1797 if (EXPR_PRIORITY (to) < EXPR_PRIORITY (from))
1798 EXPR_PRIORITY (to) = EXPR_PRIORITY (from);
1800 if (EXPR_SCHED_TIMES (to) > EXPR_SCHED_TIMES (from))
1801 EXPR_SCHED_TIMES (to) = EXPR_SCHED_TIMES (from);
1803 if (EXPR_ORIG_BB_INDEX (to) != EXPR_ORIG_BB_INDEX (from))
1804 EXPR_ORIG_BB_INDEX (to) = 0;
1806 EXPR_ORIG_SCHED_CYCLE (to) = MIN (EXPR_ORIG_SCHED_CYCLE (to),
1807 EXPR_ORIG_SCHED_CYCLE (from));
1809 /* We keep this vector sorted. */
1810 for (i = 0;
1811 VEC_iterate (expr_history_def, EXPR_HISTORY_OF_CHANGES (from),
1812 i, phist);
1813 i++)
1814 insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (to),
1815 phist->uid, phist->type,
1816 phist->old_expr_vinsn, phist->new_expr_vinsn,
1817 phist->spec_ds);
1819 EXPR_WAS_SUBSTITUTED (to) |= EXPR_WAS_SUBSTITUTED (from);
1820 EXPR_WAS_RENAMED (to) |= EXPR_WAS_RENAMED (from);
1821 EXPR_CANT_MOVE (to) |= EXPR_CANT_MOVE (from);
1823 update_target_availability (to, from, split_point);
1824 update_speculative_bits (to, from, split_point);
1827 /* Merge bits of FROM expr to TO expr. Vinsns in the exprs should be equal
1828 in terms of vinsn_equal_p. SPLIT_POINT is non-null when expressions
1829 are merged from different successors at a split point. */
1830 void
1831 merge_expr (expr_t to, expr_t from, insn_t split_point)
1833 vinsn_t to_vi = EXPR_VINSN (to);
1834 vinsn_t from_vi = EXPR_VINSN (from);
1836 gcc_assert (vinsn_equal_p (to_vi, from_vi));
1838 /* Make sure that speculative pattern is propagated into exprs that
1839 have non-speculative one. This will provide us with consistent
1840 speculative bits and speculative patterns inside expr. */
1841 if (EXPR_SPEC_DONE_DS (to) == 0
1842 && EXPR_SPEC_DONE_DS (from) != 0)
1843 change_vinsn_in_expr (to, EXPR_VINSN (from));
1845 merge_expr_data (to, from, split_point);
1846 gcc_assert (EXPR_USEFULNESS (to) <= REG_BR_PROB_BASE);
1849 /* Clear the information of this EXPR. */
1850 void
1851 clear_expr (expr_t expr)
1854 vinsn_detach (EXPR_VINSN (expr));
1855 EXPR_VINSN (expr) = NULL;
1857 free_history_vect (&EXPR_HISTORY_OF_CHANGES (expr));
1860 /* For a given LV_SET, mark EXPR having unavailable target register. */
1861 static void
1862 set_unavailable_target_for_expr (expr_t expr, regset lv_set)
1864 if (EXPR_SEPARABLE_P (expr))
1866 if (REG_P (EXPR_LHS (expr))
1867 && bitmap_bit_p (lv_set, REGNO (EXPR_LHS (expr))))
1869 /* If it's an insn like r1 = use (r1, ...), and it exists in
1870 different forms in each of the av_sets being merged, we can't say
1871 whether original destination register is available or not.
1872 However, this still works if destination register is not used
1873 in the original expression: if the branch at which LV_SET we're
1874 looking here is not actually 'other branch' in sense that same
1875 expression is available through it (but it can't be determined
1876 at computation stage because of transformations on one of the
1877 branches), it still won't affect the availability.
1878 Liveness of a register somewhere on a code motion path means
1879 it's either read somewhere on a codemotion path, live on
1880 'other' branch, live at the point immediately following
1881 the original operation, or is read by the original operation.
1882 The latter case is filtered out in the condition below.
1883 It still doesn't cover the case when register is defined and used
1884 somewhere within the code motion path, and in this case we could
1885 miss a unifying code motion along both branches using a renamed
1886 register, but it won't affect a code correctness since upon
1887 an actual code motion a bookkeeping code would be generated. */
1888 if (bitmap_bit_p (VINSN_REG_USES (EXPR_VINSN (expr)),
1889 REGNO (EXPR_LHS (expr))))
1890 EXPR_TARGET_AVAILABLE (expr) = -1;
1891 else
1892 EXPR_TARGET_AVAILABLE (expr) = false;
1895 else
1897 unsigned regno;
1898 reg_set_iterator rsi;
1900 EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_SETS (EXPR_VINSN (expr)),
1901 0, regno, rsi)
1902 if (bitmap_bit_p (lv_set, regno))
1904 EXPR_TARGET_AVAILABLE (expr) = false;
1905 break;
1908 EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_CLOBBERS (EXPR_VINSN (expr)),
1909 0, regno, rsi)
1910 if (bitmap_bit_p (lv_set, regno))
1912 EXPR_TARGET_AVAILABLE (expr) = false;
1913 break;
1918 /* Try to make EXPR speculative. Return 1 when EXPR's pattern
1919 or dependence status have changed, 2 when also the target register
1920 became unavailable, 0 if nothing had to be changed. */
1922 speculate_expr (expr_t expr, ds_t ds)
1924 int res;
1925 rtx orig_insn_rtx;
1926 rtx spec_pat;
1927 ds_t target_ds, current_ds;
1929 /* Obtain the status we need to put on EXPR. */
1930 target_ds = (ds & SPECULATIVE);
1931 current_ds = EXPR_SPEC_DONE_DS (expr);
1932 ds = ds_full_merge (current_ds, target_ds, NULL_RTX, NULL_RTX);
1934 orig_insn_rtx = EXPR_INSN_RTX (expr);
1936 res = sched_speculate_insn (orig_insn_rtx, ds, &spec_pat);
1938 switch (res)
1940 case 0:
1941 EXPR_SPEC_DONE_DS (expr) = ds;
1942 return current_ds != ds ? 1 : 0;
1944 case 1:
1946 rtx spec_insn_rtx = create_insn_rtx_from_pattern (spec_pat, NULL_RTX);
1947 vinsn_t spec_vinsn = create_vinsn_from_insn_rtx (spec_insn_rtx, false);
1949 change_vinsn_in_expr (expr, spec_vinsn);
1950 EXPR_SPEC_DONE_DS (expr) = ds;
1951 EXPR_NEEDS_SPEC_CHECK_P (expr) = true;
1953 /* Do not allow clobbering the address register of speculative
1954 insns. */
1955 if (bitmap_bit_p (VINSN_REG_USES (EXPR_VINSN (expr)),
1956 expr_dest_regno (expr)))
1958 EXPR_TARGET_AVAILABLE (expr) = false;
1959 return 2;
1962 return 1;
1965 case -1:
1966 return -1;
1968 default:
1969 gcc_unreachable ();
1970 return -1;
1974 /* Return a destination register, if any, of EXPR. */
1976 expr_dest_reg (expr_t expr)
1978 rtx dest = VINSN_LHS (EXPR_VINSN (expr));
1980 if (dest != NULL_RTX && REG_P (dest))
1981 return dest;
1983 return NULL_RTX;
1986 /* Returns the REGNO of the R's destination. */
1987 unsigned
1988 expr_dest_regno (expr_t expr)
1990 rtx dest = expr_dest_reg (expr);
1992 gcc_assert (dest != NULL_RTX);
1993 return REGNO (dest);
1996 /* For a given LV_SET, mark all expressions in JOIN_SET, but not present in
1997 AV_SET having unavailable target register. */
1998 void
1999 mark_unavailable_targets (av_set_t join_set, av_set_t av_set, regset lv_set)
2001 expr_t expr;
2002 av_set_iterator avi;
2004 FOR_EACH_EXPR (expr, avi, join_set)
2005 if (av_set_lookup (av_set, EXPR_VINSN (expr)) == NULL)
2006 set_unavailable_target_for_expr (expr, lv_set);
2010 /* Av set functions. */
2012 /* Add a new element to av set SETP.
2013 Return the element added. */
2014 static av_set_t
2015 av_set_add_element (av_set_t *setp)
2017 /* Insert at the beginning of the list. */
2018 _list_add (setp);
2019 return *setp;
2022 /* Add EXPR to SETP. */
2023 void
2024 av_set_add (av_set_t *setp, expr_t expr)
2026 av_set_t elem;
2028 gcc_assert (!INSN_NOP_P (EXPR_INSN_RTX (expr)));
2029 elem = av_set_add_element (setp);
2030 copy_expr (_AV_SET_EXPR (elem), expr);
2033 /* Same, but do not copy EXPR. */
2034 static void
2035 av_set_add_nocopy (av_set_t *setp, expr_t expr)
2037 av_set_t elem;
2039 elem = av_set_add_element (setp);
2040 *_AV_SET_EXPR (elem) = *expr;
2043 /* Remove expr pointed to by IP from the av_set. */
2044 void
2045 av_set_iter_remove (av_set_iterator *ip)
2047 clear_expr (_AV_SET_EXPR (*ip->lp));
2048 _list_iter_remove (ip);
2051 /* Search for an expr in SET, such that it's equivalent to SOUGHT_VINSN in the
2052 sense of vinsn_equal_p function. Return NULL if no such expr is
2053 in SET was found. */
2054 expr_t
2055 av_set_lookup (av_set_t set, vinsn_t sought_vinsn)
2057 expr_t expr;
2058 av_set_iterator i;
2060 FOR_EACH_EXPR (expr, i, set)
2061 if (vinsn_equal_p (EXPR_VINSN (expr), sought_vinsn))
2062 return expr;
2063 return NULL;
2066 /* Same, but also remove the EXPR found. */
2067 static expr_t
2068 av_set_lookup_and_remove (av_set_t *setp, vinsn_t sought_vinsn)
2070 expr_t expr;
2071 av_set_iterator i;
2073 FOR_EACH_EXPR_1 (expr, i, setp)
2074 if (vinsn_equal_p (EXPR_VINSN (expr), sought_vinsn))
2076 _list_iter_remove_nofree (&i);
2077 return expr;
2079 return NULL;
2082 /* Search for an expr in SET, such that it's equivalent to EXPR in the
2083 sense of vinsn_equal_p function of their vinsns, but not EXPR itself.
2084 Returns NULL if no such expr is in SET was found. */
2085 static expr_t
2086 av_set_lookup_other_equiv_expr (av_set_t set, expr_t expr)
2088 expr_t cur_expr;
2089 av_set_iterator i;
2091 FOR_EACH_EXPR (cur_expr, i, set)
2093 if (cur_expr == expr)
2094 continue;
2095 if (vinsn_equal_p (EXPR_VINSN (cur_expr), EXPR_VINSN (expr)))
2096 return cur_expr;
2099 return NULL;
2102 /* If other expression is already in AVP, remove one of them. */
2103 expr_t
2104 merge_with_other_exprs (av_set_t *avp, av_set_iterator *ip, expr_t expr)
2106 expr_t expr2;
2108 expr2 = av_set_lookup_other_equiv_expr (*avp, expr);
2109 if (expr2 != NULL)
2111 /* Reset target availability on merge, since taking it only from one
2112 of the exprs would be controversial for different code. */
2113 EXPR_TARGET_AVAILABLE (expr2) = -1;
2114 EXPR_USEFULNESS (expr2) = 0;
2116 merge_expr (expr2, expr, NULL);
2118 /* Fix usefulness as it should be now REG_BR_PROB_BASE. */
2119 EXPR_USEFULNESS (expr2) = REG_BR_PROB_BASE;
2121 av_set_iter_remove (ip);
2122 return expr2;
2125 return expr;
2128 /* Return true if there is an expr that correlates to VI in SET. */
2129 bool
2130 av_set_is_in_p (av_set_t set, vinsn_t vi)
2132 return av_set_lookup (set, vi) != NULL;
2135 /* Return a copy of SET. */
2136 av_set_t
2137 av_set_copy (av_set_t set)
2139 expr_t expr;
2140 av_set_iterator i;
2141 av_set_t res = NULL;
2143 FOR_EACH_EXPR (expr, i, set)
2144 av_set_add (&res, expr);
2146 return res;
2149 /* Join two av sets that do not have common elements by attaching second set
2150 (pointed to by FROMP) to the end of first set (TO_TAILP must point to
2151 _AV_SET_NEXT of first set's last element). */
2152 static void
2153 join_distinct_sets (av_set_t *to_tailp, av_set_t *fromp)
2155 gcc_assert (*to_tailp == NULL);
2156 *to_tailp = *fromp;
2157 *fromp = NULL;
2160 /* Makes set pointed to by TO to be the union of TO and FROM. Clear av_set
2161 pointed to by FROMP afterwards. */
2162 void
2163 av_set_union_and_clear (av_set_t *top, av_set_t *fromp, insn_t insn)
2165 expr_t expr1;
2166 av_set_iterator i;
2168 /* Delete from TOP all exprs, that present in FROMP. */
2169 FOR_EACH_EXPR_1 (expr1, i, top)
2171 expr_t expr2 = av_set_lookup (*fromp, EXPR_VINSN (expr1));
2173 if (expr2)
2175 merge_expr (expr2, expr1, insn);
2176 av_set_iter_remove (&i);
2180 join_distinct_sets (i.lp, fromp);
2183 /* Same as above, but also update availability of target register in
2184 TOP judging by TO_LV_SET and FROM_LV_SET. */
2185 void
2186 av_set_union_and_live (av_set_t *top, av_set_t *fromp, regset to_lv_set,
2187 regset from_lv_set, insn_t insn)
2189 expr_t expr1;
2190 av_set_iterator i;
2191 av_set_t *to_tailp, in_both_set = NULL;
2193 /* Delete from TOP all expres, that present in FROMP. */
2194 FOR_EACH_EXPR_1 (expr1, i, top)
2196 expr_t expr2 = av_set_lookup_and_remove (fromp, EXPR_VINSN (expr1));
2198 if (expr2)
2200 /* It may be that the expressions have different destination
2201 registers, in which case we need to check liveness here. */
2202 if (EXPR_SEPARABLE_P (expr1))
2204 int regno1 = (REG_P (EXPR_LHS (expr1))
2205 ? (int) expr_dest_regno (expr1) : -1);
2206 int regno2 = (REG_P (EXPR_LHS (expr2))
2207 ? (int) expr_dest_regno (expr2) : -1);
2209 /* ??? We don't have a way to check restrictions for
2210 *other* register on the current path, we did it only
2211 for the current target register. Give up. */
2212 if (regno1 != regno2)
2213 EXPR_TARGET_AVAILABLE (expr2) = -1;
2215 else if (EXPR_INSN_RTX (expr1) != EXPR_INSN_RTX (expr2))
2216 EXPR_TARGET_AVAILABLE (expr2) = -1;
2218 merge_expr (expr2, expr1, insn);
2219 av_set_add_nocopy (&in_both_set, expr2);
2220 av_set_iter_remove (&i);
2222 else
2223 /* EXPR1 is present in TOP, but not in FROMP. Check it on
2224 FROM_LV_SET. */
2225 set_unavailable_target_for_expr (expr1, from_lv_set);
2227 to_tailp = i.lp;
2229 /* These expressions are not present in TOP. Check liveness
2230 restrictions on TO_LV_SET. */
2231 FOR_EACH_EXPR (expr1, i, *fromp)
2232 set_unavailable_target_for_expr (expr1, to_lv_set);
2234 join_distinct_sets (i.lp, &in_both_set);
2235 join_distinct_sets (to_tailp, fromp);
2238 /* Clear av_set pointed to by SETP. */
2239 void
2240 av_set_clear (av_set_t *setp)
2242 expr_t expr;
2243 av_set_iterator i;
2245 FOR_EACH_EXPR_1 (expr, i, setp)
2246 av_set_iter_remove (&i);
2248 gcc_assert (*setp == NULL);
2251 /* Leave only one non-speculative element in the SETP. */
2252 void
2253 av_set_leave_one_nonspec (av_set_t *setp)
2255 expr_t expr;
2256 av_set_iterator i;
2257 bool has_one_nonspec = false;
2259 /* Keep all speculative exprs, and leave one non-speculative
2260 (the first one). */
2261 FOR_EACH_EXPR_1 (expr, i, setp)
2263 if (!EXPR_SPEC_DONE_DS (expr))
2265 if (has_one_nonspec)
2266 av_set_iter_remove (&i);
2267 else
2268 has_one_nonspec = true;
2273 /* Return the N'th element of the SET. */
2274 expr_t
2275 av_set_element (av_set_t set, int n)
2277 expr_t expr;
2278 av_set_iterator i;
2280 FOR_EACH_EXPR (expr, i, set)
2281 if (n-- == 0)
2282 return expr;
2284 gcc_unreachable ();
2285 return NULL;
2288 /* Deletes all expressions from AVP that are conditional branches (IFs). */
2289 void
2290 av_set_substract_cond_branches (av_set_t *avp)
2292 av_set_iterator i;
2293 expr_t expr;
2295 FOR_EACH_EXPR_1 (expr, i, avp)
2296 if (vinsn_cond_branch_p (EXPR_VINSN (expr)))
2297 av_set_iter_remove (&i);
2300 /* Multiplies usefulness attribute of each member of av-set *AVP by
2301 value PROB / ALL_PROB. */
2302 void
2303 av_set_split_usefulness (av_set_t av, int prob, int all_prob)
2305 av_set_iterator i;
2306 expr_t expr;
2308 FOR_EACH_EXPR (expr, i, av)
2309 EXPR_USEFULNESS (expr) = (all_prob
2310 ? (EXPR_USEFULNESS (expr) * prob) / all_prob
2311 : 0);
2314 /* Leave in AVP only those expressions, which are present in AV,
2315 and return it. */
2316 void
2317 av_set_intersect (av_set_t *avp, av_set_t av)
2319 av_set_iterator i;
2320 expr_t expr;
2322 FOR_EACH_EXPR_1 (expr, i, avp)
2323 if (av_set_lookup (av, EXPR_VINSN (expr)) == NULL)
2324 av_set_iter_remove (&i);
2329 /* Dependence hooks to initialize insn data. */
2331 /* This is used in hooks callable from dependence analysis when initializing
2332 instruction's data. */
2333 static struct
2335 /* Where the dependence was found (lhs/rhs). */
2336 deps_where_t where;
2338 /* The actual data object to initialize. */
2339 idata_t id;
2341 /* True when the insn should not be made clonable. */
2342 bool force_unique_p;
2344 /* True when insn should be treated as of type USE, i.e. never renamed. */
2345 bool force_use_p;
2346 } deps_init_id_data;
2349 /* Setup ID for INSN. FORCE_UNIQUE_P is true when INSN should not be
2350 clonable. */
2351 static void
2352 setup_id_for_insn (idata_t id, insn_t insn, bool force_unique_p)
2354 int type;
2356 /* Determine whether INSN could be cloned and return appropriate vinsn type.
2357 That clonable insns which can be separated into lhs and rhs have type SET.
2358 Other clonable insns have type USE. */
2359 type = GET_CODE (insn);
2361 /* Only regular insns could be cloned. */
2362 if (type == INSN && !force_unique_p)
2363 type = SET;
2364 else if (type == JUMP_INSN && simplejump_p (insn))
2365 type = PC;
2366 else if (type == DEBUG_INSN)
2367 type = !force_unique_p ? USE : INSN;
2369 IDATA_TYPE (id) = type;
2370 IDATA_REG_SETS (id) = get_clear_regset_from_pool ();
2371 IDATA_REG_USES (id) = get_clear_regset_from_pool ();
2372 IDATA_REG_CLOBBERS (id) = get_clear_regset_from_pool ();
2375 /* Start initializing insn data. */
2376 static void
2377 deps_init_id_start_insn (insn_t insn)
2379 gcc_assert (deps_init_id_data.where == DEPS_IN_NOWHERE);
2381 setup_id_for_insn (deps_init_id_data.id, insn,
2382 deps_init_id_data.force_unique_p);
2383 deps_init_id_data.where = DEPS_IN_INSN;
2386 /* Start initializing lhs data. */
2387 static void
2388 deps_init_id_start_lhs (rtx lhs)
2390 gcc_assert (deps_init_id_data.where == DEPS_IN_INSN);
2391 gcc_assert (IDATA_LHS (deps_init_id_data.id) == NULL);
2393 if (IDATA_TYPE (deps_init_id_data.id) == SET)
2395 IDATA_LHS (deps_init_id_data.id) = lhs;
2396 deps_init_id_data.where = DEPS_IN_LHS;
2400 /* Finish initializing lhs data. */
2401 static void
2402 deps_init_id_finish_lhs (void)
2404 deps_init_id_data.where = DEPS_IN_INSN;
2407 /* Note a set of REGNO. */
2408 static void
2409 deps_init_id_note_reg_set (int regno)
2411 haifa_note_reg_set (regno);
2413 if (deps_init_id_data.where == DEPS_IN_RHS)
2414 deps_init_id_data.force_use_p = true;
2416 if (IDATA_TYPE (deps_init_id_data.id) != PC)
2417 SET_REGNO_REG_SET (IDATA_REG_SETS (deps_init_id_data.id), regno);
2419 #ifdef STACK_REGS
2420 /* Make instructions that set stack registers to be ineligible for
2421 renaming to avoid issues with find_used_regs. */
2422 if (IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG))
2423 deps_init_id_data.force_use_p = true;
2424 #endif
2427 /* Note a clobber of REGNO. */
2428 static void
2429 deps_init_id_note_reg_clobber (int regno)
2431 haifa_note_reg_clobber (regno);
2433 if (deps_init_id_data.where == DEPS_IN_RHS)
2434 deps_init_id_data.force_use_p = true;
2436 if (IDATA_TYPE (deps_init_id_data.id) != PC)
2437 SET_REGNO_REG_SET (IDATA_REG_CLOBBERS (deps_init_id_data.id), regno);
2440 /* Note a use of REGNO. */
2441 static void
2442 deps_init_id_note_reg_use (int regno)
2444 haifa_note_reg_use (regno);
2446 if (IDATA_TYPE (deps_init_id_data.id) != PC)
2447 SET_REGNO_REG_SET (IDATA_REG_USES (deps_init_id_data.id), regno);
2450 /* Start initializing rhs data. */
2451 static void
2452 deps_init_id_start_rhs (rtx rhs)
2454 gcc_assert (deps_init_id_data.where == DEPS_IN_INSN);
2456 /* And there was no sel_deps_reset_to_insn (). */
2457 if (IDATA_LHS (deps_init_id_data.id) != NULL)
2459 IDATA_RHS (deps_init_id_data.id) = rhs;
2460 deps_init_id_data.where = DEPS_IN_RHS;
2464 /* Finish initializing rhs data. */
2465 static void
2466 deps_init_id_finish_rhs (void)
2468 gcc_assert (deps_init_id_data.where == DEPS_IN_RHS
2469 || deps_init_id_data.where == DEPS_IN_INSN);
2470 deps_init_id_data.where = DEPS_IN_INSN;
2473 /* Finish initializing insn data. */
2474 static void
2475 deps_init_id_finish_insn (void)
2477 gcc_assert (deps_init_id_data.where == DEPS_IN_INSN);
2479 if (IDATA_TYPE (deps_init_id_data.id) == SET)
2481 rtx lhs = IDATA_LHS (deps_init_id_data.id);
2482 rtx rhs = IDATA_RHS (deps_init_id_data.id);
2484 if (lhs == NULL || rhs == NULL || !lhs_and_rhs_separable_p (lhs, rhs)
2485 || deps_init_id_data.force_use_p)
2487 /* This should be a USE, as we don't want to schedule its RHS
2488 separately. However, we still want to have them recorded
2489 for the purposes of substitution. That's why we don't
2490 simply call downgrade_to_use () here. */
2491 gcc_assert (IDATA_TYPE (deps_init_id_data.id) == SET);
2492 gcc_assert (!lhs == !rhs);
2494 IDATA_TYPE (deps_init_id_data.id) = USE;
2498 deps_init_id_data.where = DEPS_IN_NOWHERE;
2501 /* This is dependence info used for initializing insn's data. */
2502 static struct sched_deps_info_def deps_init_id_sched_deps_info;
2504 /* This initializes most of the static part of the above structure. */
2505 static const struct sched_deps_info_def const_deps_init_id_sched_deps_info =
2507 NULL,
2509 deps_init_id_start_insn,
2510 deps_init_id_finish_insn,
2511 deps_init_id_start_lhs,
2512 deps_init_id_finish_lhs,
2513 deps_init_id_start_rhs,
2514 deps_init_id_finish_rhs,
2515 deps_init_id_note_reg_set,
2516 deps_init_id_note_reg_clobber,
2517 deps_init_id_note_reg_use,
2518 NULL, /* note_mem_dep */
2519 NULL, /* note_dep */
2521 0, /* use_cselib */
2522 0, /* use_deps_list */
2523 0 /* generate_spec_deps */
2526 /* Initialize INSN's lhs and rhs in ID. When FORCE_UNIQUE_P is true,
2527 we don't actually need information about lhs and rhs. */
2528 static void
2529 setup_id_lhs_rhs (idata_t id, insn_t insn, bool force_unique_p)
2531 rtx pat = PATTERN (insn);
2533 if (NONJUMP_INSN_P (insn)
2534 && GET_CODE (pat) == SET
2535 && !force_unique_p)
2537 IDATA_RHS (id) = SET_SRC (pat);
2538 IDATA_LHS (id) = SET_DEST (pat);
2540 else
2541 IDATA_LHS (id) = IDATA_RHS (id) = NULL;
2544 /* Possibly downgrade INSN to USE. */
2545 static void
2546 maybe_downgrade_id_to_use (idata_t id, insn_t insn)
2548 bool must_be_use = false;
2549 unsigned uid = INSN_UID (insn);
2550 df_ref *rec;
2551 rtx lhs = IDATA_LHS (id);
2552 rtx rhs = IDATA_RHS (id);
2554 /* We downgrade only SETs. */
2555 if (IDATA_TYPE (id) != SET)
2556 return;
2558 if (!lhs || !lhs_and_rhs_separable_p (lhs, rhs))
2560 IDATA_TYPE (id) = USE;
2561 return;
2564 for (rec = DF_INSN_UID_DEFS (uid); *rec; rec++)
2566 df_ref def = *rec;
2568 if (DF_REF_INSN (def)
2569 && DF_REF_FLAGS_IS_SET (def, DF_REF_PRE_POST_MODIFY)
2570 && loc_mentioned_in_p (DF_REF_LOC (def), IDATA_RHS (id)))
2572 must_be_use = true;
2573 break;
2576 #ifdef STACK_REGS
2577 /* Make instructions that set stack registers to be ineligible for
2578 renaming to avoid issues with find_used_regs. */
2579 if (IN_RANGE (DF_REF_REGNO (def), FIRST_STACK_REG, LAST_STACK_REG))
2581 must_be_use = true;
2582 break;
2584 #endif
2587 if (must_be_use)
2588 IDATA_TYPE (id) = USE;
2591 /* Setup register sets describing INSN in ID. */
2592 static void
2593 setup_id_reg_sets (idata_t id, insn_t insn)
2595 unsigned uid = INSN_UID (insn);
2596 df_ref *rec;
2597 regset tmp = get_clear_regset_from_pool ();
2599 for (rec = DF_INSN_UID_DEFS (uid); *rec; rec++)
2601 df_ref def = *rec;
2602 unsigned int regno = DF_REF_REGNO (def);
2604 /* Post modifies are treated like clobbers by sched-deps.c. */
2605 if (DF_REF_FLAGS_IS_SET (def, (DF_REF_MUST_CLOBBER
2606 | DF_REF_PRE_POST_MODIFY)))
2607 SET_REGNO_REG_SET (IDATA_REG_CLOBBERS (id), regno);
2608 else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
2610 SET_REGNO_REG_SET (IDATA_REG_SETS (id), regno);
2612 #ifdef STACK_REGS
2613 /* For stack registers, treat writes to them as writes
2614 to the first one to be consistent with sched-deps.c. */
2615 if (IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG))
2616 SET_REGNO_REG_SET (IDATA_REG_SETS (id), FIRST_STACK_REG);
2617 #endif
2619 /* Mark special refs that generate read/write def pair. */
2620 if (DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL)
2621 || regno == STACK_POINTER_REGNUM)
2622 bitmap_set_bit (tmp, regno);
2625 for (rec = DF_INSN_UID_USES (uid); *rec; rec++)
2627 df_ref use = *rec;
2628 unsigned int regno = DF_REF_REGNO (use);
2630 /* When these refs are met for the first time, skip them, as
2631 these uses are just counterparts of some defs. */
2632 if (bitmap_bit_p (tmp, regno))
2633 bitmap_clear_bit (tmp, regno);
2634 else if (! DF_REF_FLAGS_IS_SET (use, DF_REF_CALL_STACK_USAGE))
2636 SET_REGNO_REG_SET (IDATA_REG_USES (id), regno);
2638 #ifdef STACK_REGS
2639 /* For stack registers, treat reads from them as reads from
2640 the first one to be consistent with sched-deps.c. */
2641 if (IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG))
2642 SET_REGNO_REG_SET (IDATA_REG_USES (id), FIRST_STACK_REG);
2643 #endif
2647 return_regset_to_pool (tmp);
2650 /* Initialize instruction data for INSN in ID using DF's data. */
2651 static void
2652 init_id_from_df (idata_t id, insn_t insn, bool force_unique_p)
2654 gcc_assert (DF_INSN_UID_SAFE_GET (INSN_UID (insn)) != NULL);
2656 setup_id_for_insn (id, insn, force_unique_p);
2657 setup_id_lhs_rhs (id, insn, force_unique_p);
2659 if (INSN_NOP_P (insn))
2660 return;
2662 maybe_downgrade_id_to_use (id, insn);
2663 setup_id_reg_sets (id, insn);
2666 /* Initialize instruction data for INSN in ID. */
2667 static void
2668 deps_init_id (idata_t id, insn_t insn, bool force_unique_p)
2670 struct deps _dc, *dc = &_dc;
2672 deps_init_id_data.where = DEPS_IN_NOWHERE;
2673 deps_init_id_data.id = id;
2674 deps_init_id_data.force_unique_p = force_unique_p;
2675 deps_init_id_data.force_use_p = false;
2677 init_deps (dc);
2679 memcpy (&deps_init_id_sched_deps_info,
2680 &const_deps_init_id_sched_deps_info,
2681 sizeof (deps_init_id_sched_deps_info));
2683 if (spec_info != NULL)
2684 deps_init_id_sched_deps_info.generate_spec_deps = 1;
2686 sched_deps_info = &deps_init_id_sched_deps_info;
2688 deps_analyze_insn (dc, insn);
2690 free_deps (dc);
2692 deps_init_id_data.id = NULL;
2697 /* Implement hooks for collecting fundamental insn properties like if insn is
2698 an ASM or is within a SCHED_GROUP. */
2700 /* True when a "one-time init" data for INSN was already inited. */
2701 static bool
2702 first_time_insn_init (insn_t insn)
2704 return INSN_LIVE (insn) == NULL;
2707 /* Hash an entry in a transformed_insns hashtable. */
2708 static hashval_t
2709 hash_transformed_insns (const void *p)
2711 return VINSN_HASH_RTX (((const struct transformed_insns *) p)->vinsn_old);
2714 /* Compare the entries in a transformed_insns hashtable. */
2715 static int
2716 eq_transformed_insns (const void *p, const void *q)
2718 rtx i1 = VINSN_INSN_RTX (((const struct transformed_insns *) p)->vinsn_old);
2719 rtx i2 = VINSN_INSN_RTX (((const struct transformed_insns *) q)->vinsn_old);
2721 if (INSN_UID (i1) == INSN_UID (i2))
2722 return 1;
2723 return rtx_equal_p (PATTERN (i1), PATTERN (i2));
2726 /* Free an entry in a transformed_insns hashtable. */
2727 static void
2728 free_transformed_insns (void *p)
2730 struct transformed_insns *pti = (struct transformed_insns *) p;
2732 vinsn_detach (pti->vinsn_old);
2733 vinsn_detach (pti->vinsn_new);
2734 free (pti);
2737 /* Init the s_i_d data for INSN which should be inited just once, when
2738 we first see the insn. */
2739 static void
2740 init_first_time_insn_data (insn_t insn)
2742 /* This should not be set if this is the first time we init data for
2743 insn. */
2744 gcc_assert (first_time_insn_init (insn));
2746 /* These are needed for nops too. */
2747 INSN_LIVE (insn) = get_regset_from_pool ();
2748 INSN_LIVE_VALID_P (insn) = false;
2750 if (!INSN_NOP_P (insn))
2752 INSN_ANALYZED_DEPS (insn) = BITMAP_ALLOC (NULL);
2753 INSN_FOUND_DEPS (insn) = BITMAP_ALLOC (NULL);
2754 INSN_TRANSFORMED_INSNS (insn)
2755 = htab_create (16, hash_transformed_insns,
2756 eq_transformed_insns, free_transformed_insns);
2757 init_deps (&INSN_DEPS_CONTEXT (insn));
2761 /* Free the same data as above for INSN. */
2762 static void
2763 free_first_time_insn_data (insn_t insn)
2765 gcc_assert (! first_time_insn_init (insn));
2767 BITMAP_FREE (INSN_ANALYZED_DEPS (insn));
2768 BITMAP_FREE (INSN_FOUND_DEPS (insn));
2769 htab_delete (INSN_TRANSFORMED_INSNS (insn));
2770 return_regset_to_pool (INSN_LIVE (insn));
2771 INSN_LIVE (insn) = NULL;
2772 INSN_LIVE_VALID_P (insn) = false;
2774 /* This is allocated only for bookkeeping insns. */
2775 if (INSN_ORIGINATORS (insn))
2776 BITMAP_FREE (INSN_ORIGINATORS (insn));
2777 free_deps (&INSN_DEPS_CONTEXT (insn));
2780 /* Initialize region-scope data structures for basic blocks. */
2781 static void
2782 init_global_and_expr_for_bb (basic_block bb)
2784 if (sel_bb_empty_p (bb))
2785 return;
2787 invalidate_av_set (bb);
2790 /* Data for global dependency analysis (to initialize CANT_MOVE and
2791 SCHED_GROUP_P). */
2792 static struct
2794 /* Previous insn. */
2795 insn_t prev_insn;
2796 } init_global_data;
2798 /* Determine if INSN is in the sched_group, is an asm or should not be
2799 cloned. After that initialize its expr. */
2800 static void
2801 init_global_and_expr_for_insn (insn_t insn)
2803 if (LABEL_P (insn))
2804 return;
2806 if (NOTE_INSN_BASIC_BLOCK_P (insn))
2808 init_global_data.prev_insn = NULL_RTX;
2809 return;
2812 gcc_assert (INSN_P (insn));
2814 if (SCHED_GROUP_P (insn))
2815 /* Setup a sched_group. */
2817 insn_t prev_insn = init_global_data.prev_insn;
2819 if (prev_insn)
2820 INSN_SCHED_NEXT (prev_insn) = insn;
2822 init_global_data.prev_insn = insn;
2824 else
2825 init_global_data.prev_insn = NULL_RTX;
2827 if (GET_CODE (PATTERN (insn)) == ASM_INPUT
2828 || asm_noperands (PATTERN (insn)) >= 0)
2829 /* Mark INSN as an asm. */
2830 INSN_ASM_P (insn) = true;
2833 bool force_unique_p;
2834 ds_t spec_done_ds;
2836 /* Certain instructions cannot be cloned. */
2837 if (CANT_MOVE (insn)
2838 || INSN_ASM_P (insn)
2839 || SCHED_GROUP_P (insn)
2840 || prologue_epilogue_contains (insn)
2841 /* Exception handling insns are always unique. */
2842 || (flag_non_call_exceptions && can_throw_internal (insn))
2843 /* TRAP_IF though have an INSN code is control_flow_insn_p (). */
2844 || control_flow_insn_p (insn))
2845 force_unique_p = true;
2846 else
2847 force_unique_p = false;
2849 if (targetm.sched.get_insn_spec_ds)
2851 spec_done_ds = targetm.sched.get_insn_spec_ds (insn);
2852 spec_done_ds = ds_get_max_dep_weak (spec_done_ds);
2854 else
2855 spec_done_ds = 0;
2857 /* Initialize INSN's expr. */
2858 init_expr (INSN_EXPR (insn), vinsn_create (insn, force_unique_p), 0,
2859 REG_BR_PROB_BASE, INSN_PRIORITY (insn), 0, BLOCK_NUM (insn),
2860 spec_done_ds, 0, 0, NULL, true, false, false, false,
2861 CANT_MOVE (insn));
2864 init_first_time_insn_data (insn);
2867 /* Scan the region and initialize instruction data for basic blocks BBS. */
2868 void
2869 sel_init_global_and_expr (bb_vec_t bbs)
2871 /* ??? It would be nice to implement push / pop scheme for sched_infos. */
2872 const struct sched_scan_info_def ssi =
2874 NULL, /* extend_bb */
2875 init_global_and_expr_for_bb, /* init_bb */
2876 extend_insn_data, /* extend_insn */
2877 init_global_and_expr_for_insn /* init_insn */
2880 sched_scan (&ssi, bbs, NULL, NULL, NULL);
2883 /* Finalize region-scope data structures for basic blocks. */
2884 static void
2885 finish_global_and_expr_for_bb (basic_block bb)
2887 av_set_clear (&BB_AV_SET (bb));
2888 BB_AV_LEVEL (bb) = 0;
2891 /* Finalize INSN's data. */
2892 static void
2893 finish_global_and_expr_insn (insn_t insn)
2895 if (LABEL_P (insn) || NOTE_INSN_BASIC_BLOCK_P (insn))
2896 return;
2898 gcc_assert (INSN_P (insn));
2900 if (INSN_LUID (insn) > 0)
2902 free_first_time_insn_data (insn);
2903 INSN_WS_LEVEL (insn) = 0;
2904 CANT_MOVE (insn) = 0;
2906 /* We can no longer assert this, as vinsns of this insn could be
2907 easily live in other insn's caches. This should be changed to
2908 a counter-like approach among all vinsns. */
2909 gcc_assert (true || VINSN_COUNT (INSN_VINSN (insn)) == 1);
2910 clear_expr (INSN_EXPR (insn));
2914 /* Finalize per instruction data for the whole region. */
2915 void
2916 sel_finish_global_and_expr (void)
2919 bb_vec_t bbs;
2920 int i;
2922 bbs = VEC_alloc (basic_block, heap, current_nr_blocks);
2924 for (i = 0; i < current_nr_blocks; i++)
2925 VEC_quick_push (basic_block, bbs, BASIC_BLOCK (BB_TO_BLOCK (i)));
2927 /* Clear AV_SETs and INSN_EXPRs. */
2929 const struct sched_scan_info_def ssi =
2931 NULL, /* extend_bb */
2932 finish_global_and_expr_for_bb, /* init_bb */
2933 NULL, /* extend_insn */
2934 finish_global_and_expr_insn /* init_insn */
2937 sched_scan (&ssi, bbs, NULL, NULL, NULL);
2940 VEC_free (basic_block, heap, bbs);
2943 finish_insns ();
2947 /* In the below hooks, we merely calculate whether or not a dependence
2948 exists, and in what part of insn. However, we will need more data
2949 when we'll start caching dependence requests. */
2951 /* Container to hold information for dependency analysis. */
2952 static struct
2954 deps_t dc;
2956 /* A variable to track which part of rtx we are scanning in
2957 sched-deps.c: sched_analyze_insn (). */
2958 deps_where_t where;
2960 /* Current producer. */
2961 insn_t pro;
2963 /* Current consumer. */
2964 vinsn_t con;
2966 /* Is SEL_DEPS_HAS_DEP_P[DEPS_IN_X] is true, then X has a dependence.
2967 X is from { INSN, LHS, RHS }. */
2968 ds_t has_dep_p[DEPS_IN_NOWHERE];
2969 } has_dependence_data;
2971 /* Start analyzing dependencies of INSN. */
2972 static void
2973 has_dependence_start_insn (insn_t insn ATTRIBUTE_UNUSED)
2975 gcc_assert (has_dependence_data.where == DEPS_IN_NOWHERE);
2977 has_dependence_data.where = DEPS_IN_INSN;
2980 /* Finish analyzing dependencies of an insn. */
2981 static void
2982 has_dependence_finish_insn (void)
2984 gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
2986 has_dependence_data.where = DEPS_IN_NOWHERE;
2989 /* Start analyzing dependencies of LHS. */
2990 static void
2991 has_dependence_start_lhs (rtx lhs ATTRIBUTE_UNUSED)
2993 gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
2995 if (VINSN_LHS (has_dependence_data.con) != NULL)
2996 has_dependence_data.where = DEPS_IN_LHS;
2999 /* Finish analyzing dependencies of an lhs. */
3000 static void
3001 has_dependence_finish_lhs (void)
3003 has_dependence_data.where = DEPS_IN_INSN;
3006 /* Start analyzing dependencies of RHS. */
3007 static void
3008 has_dependence_start_rhs (rtx rhs ATTRIBUTE_UNUSED)
3010 gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
3012 if (VINSN_RHS (has_dependence_data.con) != NULL)
3013 has_dependence_data.where = DEPS_IN_RHS;
3016 /* Start analyzing dependencies of an rhs. */
3017 static void
3018 has_dependence_finish_rhs (void)
3020 gcc_assert (has_dependence_data.where == DEPS_IN_RHS
3021 || has_dependence_data.where == DEPS_IN_INSN);
3023 has_dependence_data.where = DEPS_IN_INSN;
3026 /* Note a set of REGNO. */
3027 static void
3028 has_dependence_note_reg_set (int regno)
3030 struct deps_reg *reg_last = &has_dependence_data.dc->reg_last[regno];
3032 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3033 VINSN_INSN_RTX
3034 (has_dependence_data.con)))
3036 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3038 if (reg_last->sets != NULL
3039 || reg_last->clobbers != NULL)
3040 *dsp = (*dsp & ~SPECULATIVE) | DEP_OUTPUT;
3042 if (reg_last->uses)
3043 *dsp = (*dsp & ~SPECULATIVE) | DEP_ANTI;
3047 /* Note a clobber of REGNO. */
3048 static void
3049 has_dependence_note_reg_clobber (int regno)
3051 struct deps_reg *reg_last = &has_dependence_data.dc->reg_last[regno];
3053 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3054 VINSN_INSN_RTX
3055 (has_dependence_data.con)))
3057 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3059 if (reg_last->sets)
3060 *dsp = (*dsp & ~SPECULATIVE) | DEP_OUTPUT;
3062 if (reg_last->uses)
3063 *dsp = (*dsp & ~SPECULATIVE) | DEP_ANTI;
3067 /* Note a use of REGNO. */
3068 static void
3069 has_dependence_note_reg_use (int regno)
3071 struct deps_reg *reg_last = &has_dependence_data.dc->reg_last[regno];
3073 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3074 VINSN_INSN_RTX
3075 (has_dependence_data.con)))
3077 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3079 if (reg_last->sets)
3080 *dsp = (*dsp & ~SPECULATIVE) | DEP_TRUE;
3082 if (reg_last->clobbers)
3083 *dsp = (*dsp & ~SPECULATIVE) | DEP_ANTI;
3085 /* Handle BE_IN_SPEC. */
3086 if (reg_last->uses)
3088 ds_t pro_spec_checked_ds;
3090 pro_spec_checked_ds = INSN_SPEC_CHECKED_DS (has_dependence_data.pro);
3091 pro_spec_checked_ds = ds_get_max_dep_weak (pro_spec_checked_ds);
3093 if (pro_spec_checked_ds != 0)
3094 /* Merge BE_IN_SPEC bits into *DSP. */
3095 *dsp = ds_full_merge (*dsp, pro_spec_checked_ds,
3096 NULL_RTX, NULL_RTX);
3101 /* Note a memory dependence. */
3102 static void
3103 has_dependence_note_mem_dep (rtx mem ATTRIBUTE_UNUSED,
3104 rtx pending_mem ATTRIBUTE_UNUSED,
3105 insn_t pending_insn ATTRIBUTE_UNUSED,
3106 ds_t ds ATTRIBUTE_UNUSED)
3108 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3109 VINSN_INSN_RTX (has_dependence_data.con)))
3111 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3113 *dsp = ds_full_merge (ds, *dsp, pending_mem, mem);
3117 /* Note a dependence. */
3118 static void
3119 has_dependence_note_dep (insn_t pro ATTRIBUTE_UNUSED,
3120 ds_t ds ATTRIBUTE_UNUSED)
3122 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3123 VINSN_INSN_RTX (has_dependence_data.con)))
3125 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3127 *dsp = ds_full_merge (ds, *dsp, NULL_RTX, NULL_RTX);
3131 /* Mark the insn as having a hard dependence that prevents speculation. */
3132 void
3133 sel_mark_hard_insn (rtx insn)
3135 int i;
3137 /* Only work when we're in has_dependence_p mode.
3138 ??? This is a hack, this should actually be a hook. */
3139 if (!has_dependence_data.dc || !has_dependence_data.pro)
3140 return;
3142 gcc_assert (insn == VINSN_INSN_RTX (has_dependence_data.con));
3143 gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
3145 for (i = 0; i < DEPS_IN_NOWHERE; i++)
3146 has_dependence_data.has_dep_p[i] &= ~SPECULATIVE;
3149 /* This structure holds the hooks for the dependency analysis used when
3150 actually processing dependencies in the scheduler. */
3151 static struct sched_deps_info_def has_dependence_sched_deps_info;
3153 /* This initializes most of the fields of the above structure. */
3154 static const struct sched_deps_info_def const_has_dependence_sched_deps_info =
3156 NULL,
3158 has_dependence_start_insn,
3159 has_dependence_finish_insn,
3160 has_dependence_start_lhs,
3161 has_dependence_finish_lhs,
3162 has_dependence_start_rhs,
3163 has_dependence_finish_rhs,
3164 has_dependence_note_reg_set,
3165 has_dependence_note_reg_clobber,
3166 has_dependence_note_reg_use,
3167 has_dependence_note_mem_dep,
3168 has_dependence_note_dep,
3170 0, /* use_cselib */
3171 0, /* use_deps_list */
3172 0 /* generate_spec_deps */
3175 /* Initialize has_dependence_sched_deps_info with extra spec field. */
3176 static void
3177 setup_has_dependence_sched_deps_info (void)
3179 memcpy (&has_dependence_sched_deps_info,
3180 &const_has_dependence_sched_deps_info,
3181 sizeof (has_dependence_sched_deps_info));
3183 if (spec_info != NULL)
3184 has_dependence_sched_deps_info.generate_spec_deps = 1;
3186 sched_deps_info = &has_dependence_sched_deps_info;
3189 /* Remove all dependences found and recorded in has_dependence_data array. */
3190 void
3191 sel_clear_has_dependence (void)
3193 int i;
3195 for (i = 0; i < DEPS_IN_NOWHERE; i++)
3196 has_dependence_data.has_dep_p[i] = 0;
3199 /* Return nonzero if EXPR has is dependent upon PRED. Return the pointer
3200 to the dependence information array in HAS_DEP_PP. */
3201 ds_t
3202 has_dependence_p (expr_t expr, insn_t pred, ds_t **has_dep_pp)
3204 int i;
3205 ds_t ds;
3206 struct deps *dc;
3208 if (INSN_SIMPLEJUMP_P (pred))
3209 /* Unconditional jump is just a transfer of control flow.
3210 Ignore it. */
3211 return false;
3213 dc = &INSN_DEPS_CONTEXT (pred);
3214 if (!dc->readonly)
3216 has_dependence_data.pro = NULL;
3217 /* Initialize empty dep context with information about PRED. */
3218 advance_deps_context (dc, pred);
3219 dc->readonly = 1;
3222 has_dependence_data.where = DEPS_IN_NOWHERE;
3223 has_dependence_data.pro = pred;
3224 has_dependence_data.con = EXPR_VINSN (expr);
3225 has_dependence_data.dc = dc;
3227 sel_clear_has_dependence ();
3229 /* Now catch all dependencies that would be generated between PRED and
3230 INSN. */
3231 setup_has_dependence_sched_deps_info ();
3232 deps_analyze_insn (dc, EXPR_INSN_RTX (expr));
3233 has_dependence_data.dc = NULL;
3235 /* When a barrier was found, set DEPS_IN_INSN bits. */
3236 if (dc->last_reg_pending_barrier == TRUE_BARRIER)
3237 has_dependence_data.has_dep_p[DEPS_IN_INSN] = DEP_TRUE;
3238 else if (dc->last_reg_pending_barrier == MOVE_BARRIER)
3239 has_dependence_data.has_dep_p[DEPS_IN_INSN] = DEP_ANTI;
3241 /* Do not allow stores to memory to move through checks. Currently
3242 we don't move this to sched-deps.c as the check doesn't have
3243 obvious places to which this dependence can be attached.
3244 FIMXE: this should go to a hook. */
3245 if (EXPR_LHS (expr)
3246 && MEM_P (EXPR_LHS (expr))
3247 && sel_insn_is_speculation_check (pred))
3248 has_dependence_data.has_dep_p[DEPS_IN_INSN] = DEP_ANTI;
3250 *has_dep_pp = has_dependence_data.has_dep_p;
3251 ds = 0;
3252 for (i = 0; i < DEPS_IN_NOWHERE; i++)
3253 ds = ds_full_merge (ds, has_dependence_data.has_dep_p[i],
3254 NULL_RTX, NULL_RTX);
3256 return ds;
3260 /* Dependence hooks implementation that checks dependence latency constraints
3261 on the insns being scheduled. The entry point for these routines is
3262 tick_check_p predicate. */
3264 static struct
3266 /* An expr we are currently checking. */
3267 expr_t expr;
3269 /* A minimal cycle for its scheduling. */
3270 int cycle;
3272 /* Whether we have seen a true dependence while checking. */
3273 bool seen_true_dep_p;
3274 } tick_check_data;
3276 /* Update minimal scheduling cycle for tick_check_insn given that it depends
3277 on PRO with status DS and weight DW. */
3278 static void
3279 tick_check_dep_with_dw (insn_t pro_insn, ds_t ds, dw_t dw)
3281 expr_t con_expr = tick_check_data.expr;
3282 insn_t con_insn = EXPR_INSN_RTX (con_expr);
3284 if (con_insn != pro_insn)
3286 enum reg_note dt;
3287 int tick;
3289 if (/* PROducer was removed from above due to pipelining. */
3290 !INSN_IN_STREAM_P (pro_insn)
3291 /* Or PROducer was originally on the next iteration regarding the
3292 CONsumer. */
3293 || (INSN_SCHED_TIMES (pro_insn)
3294 - EXPR_SCHED_TIMES (con_expr)) > 1)
3295 /* Don't count this dependence. */
3296 return;
3298 dt = ds_to_dt (ds);
3299 if (dt == REG_DEP_TRUE)
3300 tick_check_data.seen_true_dep_p = true;
3302 gcc_assert (INSN_SCHED_CYCLE (pro_insn) > 0);
3305 dep_def _dep, *dep = &_dep;
3307 init_dep (dep, pro_insn, con_insn, dt);
3309 tick = INSN_SCHED_CYCLE (pro_insn) + dep_cost_1 (dep, dw);
3312 /* When there are several kinds of dependencies between pro and con,
3313 only REG_DEP_TRUE should be taken into account. */
3314 if (tick > tick_check_data.cycle
3315 && (dt == REG_DEP_TRUE || !tick_check_data.seen_true_dep_p))
3316 tick_check_data.cycle = tick;
3320 /* An implementation of note_dep hook. */
3321 static void
3322 tick_check_note_dep (insn_t pro, ds_t ds)
3324 tick_check_dep_with_dw (pro, ds, 0);
3327 /* An implementation of note_mem_dep hook. */
3328 static void
3329 tick_check_note_mem_dep (rtx mem1, rtx mem2, insn_t pro, ds_t ds)
3331 dw_t dw;
3333 dw = (ds_to_dt (ds) == REG_DEP_TRUE
3334 ? estimate_dep_weak (mem1, mem2)
3335 : 0);
3337 tick_check_dep_with_dw (pro, ds, dw);
3340 /* This structure contains hooks for dependence analysis used when determining
3341 whether an insn is ready for scheduling. */
3342 static struct sched_deps_info_def tick_check_sched_deps_info =
3344 NULL,
3346 NULL,
3347 NULL,
3348 NULL,
3349 NULL,
3350 NULL,
3351 NULL,
3352 haifa_note_reg_set,
3353 haifa_note_reg_clobber,
3354 haifa_note_reg_use,
3355 tick_check_note_mem_dep,
3356 tick_check_note_dep,
3358 0, 0, 0
3361 /* Estimate number of cycles from the current cycle of FENCE until EXPR can be
3362 scheduled. Return 0 if all data from producers in DC is ready. */
3364 tick_check_p (expr_t expr, deps_t dc, fence_t fence)
3366 int cycles_left;
3367 /* Initialize variables. */
3368 tick_check_data.expr = expr;
3369 tick_check_data.cycle = 0;
3370 tick_check_data.seen_true_dep_p = false;
3371 sched_deps_info = &tick_check_sched_deps_info;
3373 gcc_assert (!dc->readonly);
3374 dc->readonly = 1;
3375 deps_analyze_insn (dc, EXPR_INSN_RTX (expr));
3376 dc->readonly = 0;
3378 cycles_left = tick_check_data.cycle - FENCE_CYCLE (fence);
3380 return cycles_left >= 0 ? cycles_left : 0;
3384 /* Functions to work with insns. */
3386 /* Returns true if LHS of INSN is the same as DEST of an insn
3387 being moved. */
3388 bool
3389 lhs_of_insn_equals_to_dest_p (insn_t insn, rtx dest)
3391 rtx lhs = INSN_LHS (insn);
3393 if (lhs == NULL || dest == NULL)
3394 return false;
3396 return rtx_equal_p (lhs, dest);
3399 /* Return s_i_d entry of INSN. Callable from debugger. */
3400 sel_insn_data_def
3401 insn_sid (insn_t insn)
3403 return *SID (insn);
3406 /* True when INSN is a speculative check. We can tell this by looking
3407 at the data structures of the selective scheduler, not by examining
3408 the pattern. */
3409 bool
3410 sel_insn_is_speculation_check (rtx insn)
3412 return s_i_d && !! INSN_SPEC_CHECKED_DS (insn);
3415 /* Extracts machine mode MODE and destination location DST_LOC
3416 for given INSN. */
3417 void
3418 get_dest_and_mode (rtx insn, rtx *dst_loc, enum machine_mode *mode)
3420 rtx pat = PATTERN (insn);
3422 gcc_assert (dst_loc);
3423 gcc_assert (GET_CODE (pat) == SET);
3425 *dst_loc = SET_DEST (pat);
3427 gcc_assert (*dst_loc);
3428 gcc_assert (MEM_P (*dst_loc) || REG_P (*dst_loc));
3430 if (mode)
3431 *mode = GET_MODE (*dst_loc);
3434 /* Returns true when moving through JUMP will result in bookkeeping
3435 creation. */
3436 bool
3437 bookkeeping_can_be_created_if_moved_through_p (insn_t jump)
3439 insn_t succ;
3440 succ_iterator si;
3442 FOR_EACH_SUCC (succ, si, jump)
3443 if (sel_num_cfg_preds_gt_1 (succ))
3444 return true;
3446 return false;
3449 /* Return 'true' if INSN is the only one in its basic block. */
3450 static bool
3451 insn_is_the_only_one_in_bb_p (insn_t insn)
3453 return sel_bb_head_p (insn) && sel_bb_end_p (insn);
3456 #ifdef ENABLE_CHECKING
3457 /* Check that the region we're scheduling still has at most one
3458 backedge. */
3459 static void
3460 verify_backedges (void)
3462 if (pipelining_p)
3464 int i, n = 0;
3465 edge e;
3466 edge_iterator ei;
3468 for (i = 0; i < current_nr_blocks; i++)
3469 FOR_EACH_EDGE (e, ei, BASIC_BLOCK (BB_TO_BLOCK (i))->succs)
3470 if (in_current_region_p (e->dest)
3471 && BLOCK_TO_BB (e->dest->index) < i)
3472 n++;
3474 gcc_assert (n <= 1);
3477 #endif
3480 /* Functions to work with control flow. */
3482 /* Tidy the possibly empty block BB. */
3483 bool
3484 maybe_tidy_empty_bb (basic_block bb)
3486 basic_block succ_bb, pred_bb;
3487 edge e;
3488 edge_iterator ei;
3489 bool rescan_p;
3491 /* Keep empty bb only if this block immediately precedes EXIT and
3492 has incoming non-fallthrough edge. Otherwise remove it. */
3493 if (!sel_bb_empty_p (bb)
3494 || (single_succ_p (bb)
3495 && single_succ (bb) == EXIT_BLOCK_PTR
3496 && (!single_pred_p (bb)
3497 || !(single_pred_edge (bb)->flags & EDGE_FALLTHRU))))
3498 return false;
3500 /* Do not attempt to redirect complex edges. */
3501 FOR_EACH_EDGE (e, ei, bb->preds)
3502 if (e->flags & EDGE_COMPLEX)
3503 return false;
3505 free_data_sets (bb);
3507 /* Do not delete BB if it has more than one successor.
3508 That can occur when we moving a jump. */
3509 if (!single_succ_p (bb))
3511 gcc_assert (can_merge_blocks_p (bb->prev_bb, bb));
3512 sel_merge_blocks (bb->prev_bb, bb);
3513 return true;
3516 succ_bb = single_succ (bb);
3517 rescan_p = true;
3518 pred_bb = NULL;
3520 /* Redirect all non-fallthru edges to the next bb. */
3521 while (rescan_p)
3523 rescan_p = false;
3525 FOR_EACH_EDGE (e, ei, bb->preds)
3527 pred_bb = e->src;
3529 if (!(e->flags & EDGE_FALLTHRU))
3531 sel_redirect_edge_and_branch (e, succ_bb);
3532 rescan_p = true;
3533 break;
3538 /* If it is possible - merge BB with its predecessor. */
3539 if (can_merge_blocks_p (bb->prev_bb, bb))
3540 sel_merge_blocks (bb->prev_bb, bb);
3541 else
3542 /* Otherwise this is a block without fallthru predecessor.
3543 Just delete it. */
3545 gcc_assert (pred_bb != NULL);
3547 move_bb_info (pred_bb, bb);
3548 remove_empty_bb (bb, true);
3551 #ifdef ENABLE_CHECKING
3552 verify_backedges ();
3553 #endif
3555 return true;
3558 /* Tidy the control flow after we have removed original insn from
3559 XBB. Return true if we have removed some blocks. When FULL_TIDYING
3560 is true, also try to optimize control flow on non-empty blocks. */
3561 bool
3562 tidy_control_flow (basic_block xbb, bool full_tidying)
3564 bool changed = true;
3565 insn_t first, last;
3567 /* First check whether XBB is empty. */
3568 changed = maybe_tidy_empty_bb (xbb);
3569 if (changed || !full_tidying)
3570 return changed;
3572 /* Check if there is a unnecessary jump after insn left. */
3573 if (jump_leads_only_to_bb_p (BB_END (xbb), xbb->next_bb)
3574 && INSN_SCHED_TIMES (BB_END (xbb)) == 0
3575 && !IN_CURRENT_FENCE_P (BB_END (xbb)))
3577 if (sel_remove_insn (BB_END (xbb), false, false))
3578 return true;
3579 tidy_fallthru_edge (EDGE_SUCC (xbb, 0));
3582 first = sel_bb_head (xbb);
3583 last = sel_bb_end (xbb);
3584 if (MAY_HAVE_DEBUG_INSNS)
3586 if (first != last && DEBUG_INSN_P (first))
3588 first = NEXT_INSN (first);
3589 while (first != last && (DEBUG_INSN_P (first) || NOTE_P (first)));
3591 if (first != last && DEBUG_INSN_P (last))
3593 last = PREV_INSN (last);
3594 while (first != last && (DEBUG_INSN_P (last) || NOTE_P (last)));
3596 /* Check if there is an unnecessary jump in previous basic block leading
3597 to next basic block left after removing INSN from stream.
3598 If it is so, remove that jump and redirect edge to current
3599 basic block (where there was INSN before deletion). This way
3600 when NOP will be deleted several instructions later with its
3601 basic block we will not get a jump to next instruction, which
3602 can be harmful. */
3603 if (first == last
3604 && !sel_bb_empty_p (xbb)
3605 && INSN_NOP_P (last)
3606 /* Flow goes fallthru from current block to the next. */
3607 && EDGE_COUNT (xbb->succs) == 1
3608 && (EDGE_SUCC (xbb, 0)->flags & EDGE_FALLTHRU)
3609 /* When successor is an EXIT block, it may not be the next block. */
3610 && single_succ (xbb) != EXIT_BLOCK_PTR
3611 /* And unconditional jump in previous basic block leads to
3612 next basic block of XBB and this jump can be safely removed. */
3613 && in_current_region_p (xbb->prev_bb)
3614 && jump_leads_only_to_bb_p (BB_END (xbb->prev_bb), xbb->next_bb)
3615 && INSN_SCHED_TIMES (BB_END (xbb->prev_bb)) == 0
3616 /* Also this jump is not at the scheduling boundary. */
3617 && !IN_CURRENT_FENCE_P (BB_END (xbb->prev_bb)))
3619 /* Clear data structures of jump - jump itself will be removed
3620 by sel_redirect_edge_and_branch. */
3621 clear_expr (INSN_EXPR (BB_END (xbb->prev_bb)));
3622 sel_redirect_edge_and_branch (EDGE_SUCC (xbb->prev_bb, 0), xbb);
3623 gcc_assert (EDGE_SUCC (xbb->prev_bb, 0)->flags & EDGE_FALLTHRU);
3625 /* It can turn out that after removing unused jump, basic block
3626 that contained that jump, becomes empty too. In such case
3627 remove it too. */
3628 if (sel_bb_empty_p (xbb->prev_bb))
3629 changed = maybe_tidy_empty_bb (xbb->prev_bb);
3632 return changed;
3635 /* Rip-off INSN from the insn stream. When ONLY_DISCONNECT is true,
3636 do not delete insn's data, because it will be later re-emitted.
3637 Return true if we have removed some blocks afterwards. */
3638 bool
3639 sel_remove_insn (insn_t insn, bool only_disconnect, bool full_tidying)
3641 basic_block bb = BLOCK_FOR_INSN (insn);
3643 gcc_assert (INSN_IN_STREAM_P (insn));
3645 if (DEBUG_INSN_P (insn) && BB_AV_SET_VALID_P (bb))
3647 expr_t expr;
3648 av_set_iterator i;
3650 /* When we remove a debug insn that is head of a BB, it remains
3651 in the AV_SET of the block, but it shouldn't. */
3652 FOR_EACH_EXPR_1 (expr, i, &BB_AV_SET (bb))
3653 if (EXPR_INSN_RTX (expr) == insn)
3655 av_set_iter_remove (&i);
3656 break;
3660 if (only_disconnect)
3662 insn_t prev = PREV_INSN (insn);
3663 insn_t next = NEXT_INSN (insn);
3664 basic_block bb = BLOCK_FOR_INSN (insn);
3666 NEXT_INSN (prev) = next;
3667 PREV_INSN (next) = prev;
3669 if (BB_HEAD (bb) == insn)
3671 gcc_assert (BLOCK_FOR_INSN (prev) == bb);
3672 BB_HEAD (bb) = prev;
3674 if (BB_END (bb) == insn)
3675 BB_END (bb) = prev;
3677 else
3679 remove_insn (insn);
3680 clear_expr (INSN_EXPR (insn));
3683 /* It is necessary to null this fields before calling add_insn (). */
3684 PREV_INSN (insn) = NULL_RTX;
3685 NEXT_INSN (insn) = NULL_RTX;
3687 return tidy_control_flow (bb, full_tidying);
3690 /* Estimate number of the insns in BB. */
3691 static int
3692 sel_estimate_number_of_insns (basic_block bb)
3694 int res = 0;
3695 insn_t insn = NEXT_INSN (BB_HEAD (bb)), next_tail = NEXT_INSN (BB_END (bb));
3697 for (; insn != next_tail; insn = NEXT_INSN (insn))
3698 if (NONDEBUG_INSN_P (insn))
3699 res++;
3701 return res;
3704 /* We don't need separate luids for notes or labels. */
3705 static int
3706 sel_luid_for_non_insn (rtx x)
3708 gcc_assert (NOTE_P (x) || LABEL_P (x));
3710 return -1;
3713 /* Return seqno of the only predecessor of INSN. */
3714 static int
3715 get_seqno_of_a_pred (insn_t insn)
3717 int seqno;
3719 gcc_assert (INSN_SIMPLEJUMP_P (insn));
3721 if (!sel_bb_head_p (insn))
3722 seqno = INSN_SEQNO (PREV_INSN (insn));
3723 else
3725 basic_block bb = BLOCK_FOR_INSN (insn);
3727 if (single_pred_p (bb)
3728 && !in_current_region_p (single_pred (bb)))
3730 /* We can have preds outside a region when splitting edges
3731 for pipelining of an outer loop. Use succ instead.
3732 There should be only one of them. */
3733 insn_t succ = NULL;
3734 succ_iterator si;
3735 bool first = true;
3737 gcc_assert (flag_sel_sched_pipelining_outer_loops
3738 && current_loop_nest);
3739 FOR_EACH_SUCC_1 (succ, si, insn,
3740 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
3742 gcc_assert (first);
3743 first = false;
3746 gcc_assert (succ != NULL);
3747 seqno = INSN_SEQNO (succ);
3749 else
3751 insn_t *preds;
3752 int n;
3754 cfg_preds (BLOCK_FOR_INSN (insn), &preds, &n);
3755 gcc_assert (n == 1);
3757 seqno = INSN_SEQNO (preds[0]);
3759 free (preds);
3763 return seqno;
3766 /* Find the proper seqno for inserting at INSN. Returns -1 if no predecessors
3767 with positive seqno exist. */
3769 get_seqno_by_preds (rtx insn)
3771 basic_block bb = BLOCK_FOR_INSN (insn);
3772 rtx tmp = insn, head = BB_HEAD (bb);
3773 insn_t *preds;
3774 int n, i, seqno;
3776 while (tmp != head)
3777 if (INSN_P (tmp))
3778 return INSN_SEQNO (tmp);
3779 else
3780 tmp = PREV_INSN (tmp);
3782 cfg_preds (bb, &preds, &n);
3783 for (i = 0, seqno = -1; i < n; i++)
3784 seqno = MAX (seqno, INSN_SEQNO (preds[i]));
3786 return seqno;
3791 /* Extend pass-scope data structures for basic blocks. */
3792 void
3793 sel_extend_global_bb_info (void)
3795 VEC_safe_grow_cleared (sel_global_bb_info_def, heap, sel_global_bb_info,
3796 last_basic_block);
3799 /* Extend region-scope data structures for basic blocks. */
3800 static void
3801 extend_region_bb_info (void)
3803 VEC_safe_grow_cleared (sel_region_bb_info_def, heap, sel_region_bb_info,
3804 last_basic_block);
3807 /* Extend all data structures to fit for all basic blocks. */
3808 static void
3809 extend_bb_info (void)
3811 sel_extend_global_bb_info ();
3812 extend_region_bb_info ();
3815 /* Finalize pass-scope data structures for basic blocks. */
3816 void
3817 sel_finish_global_bb_info (void)
3819 VEC_free (sel_global_bb_info_def, heap, sel_global_bb_info);
3822 /* Finalize region-scope data structures for basic blocks. */
3823 static void
3824 finish_region_bb_info (void)
3826 VEC_free (sel_region_bb_info_def, heap, sel_region_bb_info);
3830 /* Data for each insn in current region. */
3831 VEC (sel_insn_data_def, heap) *s_i_d = NULL;
3833 /* A vector for the insns we've emitted. */
3834 static insn_vec_t new_insns = NULL;
3836 /* Extend data structures for insns from current region. */
3837 static void
3838 extend_insn_data (void)
3840 int reserve;
3842 sched_extend_target ();
3843 sched_deps_init (false);
3845 /* Extend data structures for insns from current region. */
3846 reserve = (sched_max_luid + 1
3847 - VEC_length (sel_insn_data_def, s_i_d));
3848 if (reserve > 0
3849 && ! VEC_space (sel_insn_data_def, s_i_d, reserve))
3850 VEC_safe_grow_cleared (sel_insn_data_def, heap, s_i_d,
3851 3 * sched_max_luid / 2);
3854 /* Finalize data structures for insns from current region. */
3855 static void
3856 finish_insns (void)
3858 unsigned i;
3860 /* Clear here all dependence contexts that may have left from insns that were
3861 removed during the scheduling. */
3862 for (i = 0; i < VEC_length (sel_insn_data_def, s_i_d); i++)
3864 sel_insn_data_def *sid_entry = VEC_index (sel_insn_data_def, s_i_d, i);
3866 if (sid_entry->live)
3867 return_regset_to_pool (sid_entry->live);
3868 if (sid_entry->analyzed_deps)
3870 BITMAP_FREE (sid_entry->analyzed_deps);
3871 BITMAP_FREE (sid_entry->found_deps);
3872 htab_delete (sid_entry->transformed_insns);
3873 free_deps (&sid_entry->deps_context);
3875 if (EXPR_VINSN (&sid_entry->expr))
3877 clear_expr (&sid_entry->expr);
3879 /* Also, clear CANT_MOVE bit here, because we really don't want it
3880 to be passed to the next region. */
3881 CANT_MOVE_BY_LUID (i) = 0;
3885 VEC_free (sel_insn_data_def, heap, s_i_d);
3888 /* A proxy to pass initialization data to init_insn (). */
3889 static sel_insn_data_def _insn_init_ssid;
3890 static sel_insn_data_t insn_init_ssid = &_insn_init_ssid;
3892 /* If true create a new vinsn. Otherwise use the one from EXPR. */
3893 static bool insn_init_create_new_vinsn_p;
3895 /* Set all necessary data for initialization of the new insn[s]. */
3896 static expr_t
3897 set_insn_init (expr_t expr, vinsn_t vi, int seqno)
3899 expr_t x = &insn_init_ssid->expr;
3901 copy_expr_onside (x, expr);
3902 if (vi != NULL)
3904 insn_init_create_new_vinsn_p = false;
3905 change_vinsn_in_expr (x, vi);
3907 else
3908 insn_init_create_new_vinsn_p = true;
3910 insn_init_ssid->seqno = seqno;
3911 return x;
3914 /* Init data for INSN. */
3915 static void
3916 init_insn_data (insn_t insn)
3918 expr_t expr;
3919 sel_insn_data_t ssid = insn_init_ssid;
3921 /* The fields mentioned below are special and hence are not being
3922 propagated to the new insns. */
3923 gcc_assert (!ssid->asm_p && ssid->sched_next == NULL
3924 && !ssid->after_stall_p && ssid->sched_cycle == 0);
3925 gcc_assert (INSN_P (insn) && INSN_LUID (insn) > 0);
3927 expr = INSN_EXPR (insn);
3928 copy_expr (expr, &ssid->expr);
3929 prepare_insn_expr (insn, ssid->seqno);
3931 if (insn_init_create_new_vinsn_p)
3932 change_vinsn_in_expr (expr, vinsn_create (insn, init_insn_force_unique_p));
3934 if (first_time_insn_init (insn))
3935 init_first_time_insn_data (insn);
3938 /* This is used to initialize spurious jumps generated by
3939 sel_redirect_edge (). */
3940 static void
3941 init_simplejump_data (insn_t insn)
3943 init_expr (INSN_EXPR (insn), vinsn_create (insn, false), 0,
3944 REG_BR_PROB_BASE, 0, 0, 0, 0, 0, 0, NULL, true, false, false,
3945 false, true);
3946 INSN_SEQNO (insn) = get_seqno_of_a_pred (insn);
3947 init_first_time_insn_data (insn);
3950 /* Perform deferred initialization of insns. This is used to process
3951 a new jump that may be created by redirect_edge. */
3952 void
3953 sel_init_new_insn (insn_t insn, int flags)
3955 /* We create data structures for bb when the first insn is emitted in it. */
3956 if (INSN_P (insn)
3957 && INSN_IN_STREAM_P (insn)
3958 && insn_is_the_only_one_in_bb_p (insn))
3960 extend_bb_info ();
3961 create_initial_data_sets (BLOCK_FOR_INSN (insn));
3964 if (flags & INSN_INIT_TODO_LUID)
3965 sched_init_luids (NULL, NULL, NULL, insn);
3967 if (flags & INSN_INIT_TODO_SSID)
3969 extend_insn_data ();
3970 init_insn_data (insn);
3971 clear_expr (&insn_init_ssid->expr);
3974 if (flags & INSN_INIT_TODO_SIMPLEJUMP)
3976 extend_insn_data ();
3977 init_simplejump_data (insn);
3980 gcc_assert (CONTAINING_RGN (BLOCK_NUM (insn))
3981 == CONTAINING_RGN (BB_TO_BLOCK (0)));
3985 /* Functions to init/finish work with lv sets. */
3987 /* Init BB_LV_SET of BB from DF_LR_IN set of BB. */
3988 static void
3989 init_lv_set (basic_block bb)
3991 gcc_assert (!BB_LV_SET_VALID_P (bb));
3993 BB_LV_SET (bb) = get_regset_from_pool ();
3994 COPY_REG_SET (BB_LV_SET (bb), DF_LR_IN (bb));
3995 BB_LV_SET_VALID_P (bb) = true;
3998 /* Copy liveness information to BB from FROM_BB. */
3999 static void
4000 copy_lv_set_from (basic_block bb, basic_block from_bb)
4002 gcc_assert (!BB_LV_SET_VALID_P (bb));
4004 COPY_REG_SET (BB_LV_SET (bb), BB_LV_SET (from_bb));
4005 BB_LV_SET_VALID_P (bb) = true;
4008 /* Initialize lv set of all bb headers. */
4009 void
4010 init_lv_sets (void)
4012 basic_block bb;
4014 /* Initialize of LV sets. */
4015 FOR_EACH_BB (bb)
4016 init_lv_set (bb);
4018 /* Don't forget EXIT_BLOCK. */
4019 init_lv_set (EXIT_BLOCK_PTR);
4022 /* Release lv set of HEAD. */
4023 static void
4024 free_lv_set (basic_block bb)
4026 gcc_assert (BB_LV_SET (bb) != NULL);
4028 return_regset_to_pool (BB_LV_SET (bb));
4029 BB_LV_SET (bb) = NULL;
4030 BB_LV_SET_VALID_P (bb) = false;
4033 /* Finalize lv sets of all bb headers. */
4034 void
4035 free_lv_sets (void)
4037 basic_block bb;
4039 /* Don't forget EXIT_BLOCK. */
4040 free_lv_set (EXIT_BLOCK_PTR);
4042 /* Free LV sets. */
4043 FOR_EACH_BB (bb)
4044 if (BB_LV_SET (bb))
4045 free_lv_set (bb);
4048 /* Initialize an invalid AV_SET for BB.
4049 This set will be updated next time compute_av () process BB. */
4050 static void
4051 invalidate_av_set (basic_block bb)
4053 gcc_assert (BB_AV_LEVEL (bb) <= 0
4054 && BB_AV_SET (bb) == NULL);
4056 BB_AV_LEVEL (bb) = -1;
4059 /* Create initial data sets for BB (they will be invalid). */
4060 static void
4061 create_initial_data_sets (basic_block bb)
4063 if (BB_LV_SET (bb))
4064 BB_LV_SET_VALID_P (bb) = false;
4065 else
4066 BB_LV_SET (bb) = get_regset_from_pool ();
4067 invalidate_av_set (bb);
4070 /* Free av set of BB. */
4071 static void
4072 free_av_set (basic_block bb)
4074 av_set_clear (&BB_AV_SET (bb));
4075 BB_AV_LEVEL (bb) = 0;
4078 /* Free data sets of BB. */
4079 void
4080 free_data_sets (basic_block bb)
4082 free_lv_set (bb);
4083 free_av_set (bb);
4086 /* Exchange lv sets of TO and FROM. */
4087 static void
4088 exchange_lv_sets (basic_block to, basic_block from)
4091 regset to_lv_set = BB_LV_SET (to);
4093 BB_LV_SET (to) = BB_LV_SET (from);
4094 BB_LV_SET (from) = to_lv_set;
4098 bool to_lv_set_valid_p = BB_LV_SET_VALID_P (to);
4100 BB_LV_SET_VALID_P (to) = BB_LV_SET_VALID_P (from);
4101 BB_LV_SET_VALID_P (from) = to_lv_set_valid_p;
4106 /* Exchange av sets of TO and FROM. */
4107 static void
4108 exchange_av_sets (basic_block to, basic_block from)
4111 av_set_t to_av_set = BB_AV_SET (to);
4113 BB_AV_SET (to) = BB_AV_SET (from);
4114 BB_AV_SET (from) = to_av_set;
4118 int to_av_level = BB_AV_LEVEL (to);
4120 BB_AV_LEVEL (to) = BB_AV_LEVEL (from);
4121 BB_AV_LEVEL (from) = to_av_level;
4125 /* Exchange data sets of TO and FROM. */
4126 void
4127 exchange_data_sets (basic_block to, basic_block from)
4129 exchange_lv_sets (to, from);
4130 exchange_av_sets (to, from);
4133 /* Copy data sets of FROM to TO. */
4134 void
4135 copy_data_sets (basic_block to, basic_block from)
4137 gcc_assert (!BB_LV_SET_VALID_P (to) && !BB_AV_SET_VALID_P (to));
4138 gcc_assert (BB_AV_SET (to) == NULL);
4140 BB_AV_LEVEL (to) = BB_AV_LEVEL (from);
4141 BB_LV_SET_VALID_P (to) = BB_LV_SET_VALID_P (from);
4143 if (BB_AV_SET_VALID_P (from))
4145 BB_AV_SET (to) = av_set_copy (BB_AV_SET (from));
4147 if (BB_LV_SET_VALID_P (from))
4149 gcc_assert (BB_LV_SET (to) != NULL);
4150 COPY_REG_SET (BB_LV_SET (to), BB_LV_SET (from));
4154 /* Return an av set for INSN, if any. */
4155 av_set_t
4156 get_av_set (insn_t insn)
4158 av_set_t av_set;
4160 gcc_assert (AV_SET_VALID_P (insn));
4162 if (sel_bb_head_p (insn))
4163 av_set = BB_AV_SET (BLOCK_FOR_INSN (insn));
4164 else
4165 av_set = NULL;
4167 return av_set;
4170 /* Implementation of AV_LEVEL () macro. Return AV_LEVEL () of INSN. */
4172 get_av_level (insn_t insn)
4174 int av_level;
4176 gcc_assert (INSN_P (insn));
4178 if (sel_bb_head_p (insn))
4179 av_level = BB_AV_LEVEL (BLOCK_FOR_INSN (insn));
4180 else
4181 av_level = INSN_WS_LEVEL (insn);
4183 return av_level;
4188 /* Variables to work with control-flow graph. */
4190 /* The basic block that already has been processed by the sched_data_update (),
4191 but hasn't been in sel_add_bb () yet. */
4192 static VEC (basic_block, heap) *last_added_blocks = NULL;
4194 /* A pool for allocating successor infos. */
4195 static struct
4197 /* A stack for saving succs_info structures. */
4198 struct succs_info *stack;
4200 /* Its size. */
4201 int size;
4203 /* Top of the stack. */
4204 int top;
4206 /* Maximal value of the top. */
4207 int max_top;
4208 } succs_info_pool;
4210 /* Functions to work with control-flow graph. */
4212 /* Return basic block note of BB. */
4213 insn_t
4214 sel_bb_head (basic_block bb)
4216 insn_t head;
4218 if (bb == EXIT_BLOCK_PTR)
4220 gcc_assert (exit_insn != NULL_RTX);
4221 head = exit_insn;
4223 else
4225 insn_t note;
4227 note = bb_note (bb);
4228 head = next_nonnote_insn (note);
4230 if (head && BLOCK_FOR_INSN (head) != bb)
4231 head = NULL_RTX;
4234 return head;
4237 /* Return true if INSN is a basic block header. */
4238 bool
4239 sel_bb_head_p (insn_t insn)
4241 return sel_bb_head (BLOCK_FOR_INSN (insn)) == insn;
4244 /* Return last insn of BB. */
4245 insn_t
4246 sel_bb_end (basic_block bb)
4248 if (sel_bb_empty_p (bb))
4249 return NULL_RTX;
4251 gcc_assert (bb != EXIT_BLOCK_PTR);
4253 return BB_END (bb);
4256 /* Return true if INSN is the last insn in its basic block. */
4257 bool
4258 sel_bb_end_p (insn_t insn)
4260 return insn == sel_bb_end (BLOCK_FOR_INSN (insn));
4263 /* Return true if BB consist of single NOTE_INSN_BASIC_BLOCK. */
4264 bool
4265 sel_bb_empty_p (basic_block bb)
4267 return sel_bb_head (bb) == NULL;
4270 /* True when BB belongs to the current scheduling region. */
4271 bool
4272 in_current_region_p (basic_block bb)
4274 if (bb->index < NUM_FIXED_BLOCKS)
4275 return false;
4277 return CONTAINING_RGN (bb->index) == CONTAINING_RGN (BB_TO_BLOCK (0));
4280 /* Return the block which is a fallthru bb of a conditional jump JUMP. */
4281 basic_block
4282 fallthru_bb_of_jump (rtx jump)
4284 if (!JUMP_P (jump))
4285 return NULL;
4287 if (any_uncondjump_p (jump))
4288 return single_succ (BLOCK_FOR_INSN (jump));
4290 if (!any_condjump_p (jump))
4291 return NULL;
4293 return FALLTHRU_EDGE (BLOCK_FOR_INSN (jump))->dest;
4296 /* Remove all notes from BB. */
4297 static void
4298 init_bb (basic_block bb)
4300 remove_notes (bb_note (bb), BB_END (bb));
4301 BB_NOTE_LIST (bb) = note_list;
4304 void
4305 sel_init_bbs (bb_vec_t bbs, basic_block bb)
4307 const struct sched_scan_info_def ssi =
4309 extend_bb_info, /* extend_bb */
4310 init_bb, /* init_bb */
4311 NULL, /* extend_insn */
4312 NULL /* init_insn */
4315 sched_scan (&ssi, bbs, bb, new_insns, NULL);
4318 /* Restore other notes for the whole region. */
4319 static void
4320 sel_restore_other_notes (void)
4322 int bb;
4324 for (bb = 0; bb < current_nr_blocks; bb++)
4326 basic_block first, last;
4328 first = EBB_FIRST_BB (bb);
4329 last = EBB_LAST_BB (bb)->next_bb;
4333 note_list = BB_NOTE_LIST (first);
4334 restore_other_notes (NULL, first);
4335 BB_NOTE_LIST (first) = NULL_RTX;
4337 first = first->next_bb;
4339 while (first != last);
4343 /* Free per-bb data structures. */
4344 void
4345 sel_finish_bbs (void)
4347 sel_restore_other_notes ();
4349 /* Remove current loop preheader from this loop. */
4350 if (current_loop_nest)
4351 sel_remove_loop_preheader ();
4353 finish_region_bb_info ();
4356 /* Return true if INSN has a single successor of type FLAGS. */
4357 bool
4358 sel_insn_has_single_succ_p (insn_t insn, int flags)
4360 insn_t succ;
4361 succ_iterator si;
4362 bool first_p = true;
4364 FOR_EACH_SUCC_1 (succ, si, insn, flags)
4366 if (first_p)
4367 first_p = false;
4368 else
4369 return false;
4372 return true;
4375 /* Allocate successor's info. */
4376 static struct succs_info *
4377 alloc_succs_info (void)
4379 if (succs_info_pool.top == succs_info_pool.max_top)
4381 int i;
4383 if (++succs_info_pool.max_top >= succs_info_pool.size)
4384 gcc_unreachable ();
4386 i = ++succs_info_pool.top;
4387 succs_info_pool.stack[i].succs_ok = VEC_alloc (rtx, heap, 10);
4388 succs_info_pool.stack[i].succs_other = VEC_alloc (rtx, heap, 10);
4389 succs_info_pool.stack[i].probs_ok = VEC_alloc (int, heap, 10);
4391 else
4392 succs_info_pool.top++;
4394 return &succs_info_pool.stack[succs_info_pool.top];
4397 /* Free successor's info. */
4398 void
4399 free_succs_info (struct succs_info * sinfo)
4401 gcc_assert (succs_info_pool.top >= 0
4402 && &succs_info_pool.stack[succs_info_pool.top] == sinfo);
4403 succs_info_pool.top--;
4405 /* Clear stale info. */
4406 VEC_block_remove (rtx, sinfo->succs_ok,
4407 0, VEC_length (rtx, sinfo->succs_ok));
4408 VEC_block_remove (rtx, sinfo->succs_other,
4409 0, VEC_length (rtx, sinfo->succs_other));
4410 VEC_block_remove (int, sinfo->probs_ok,
4411 0, VEC_length (int, sinfo->probs_ok));
4412 sinfo->all_prob = 0;
4413 sinfo->succs_ok_n = 0;
4414 sinfo->all_succs_n = 0;
4417 /* Compute successor info for INSN. FLAGS are the flags passed
4418 to the FOR_EACH_SUCC_1 iterator. */
4419 struct succs_info *
4420 compute_succs_info (insn_t insn, short flags)
4422 succ_iterator si;
4423 insn_t succ;
4424 struct succs_info *sinfo = alloc_succs_info ();
4426 /* Traverse *all* successors and decide what to do with each. */
4427 FOR_EACH_SUCC_1 (succ, si, insn, SUCCS_ALL)
4429 /* FIXME: this doesn't work for skipping to loop exits, as we don't
4430 perform code motion through inner loops. */
4431 short current_flags = si.current_flags & ~SUCCS_SKIP_TO_LOOP_EXITS;
4433 if (current_flags & flags)
4435 VEC_safe_push (rtx, heap, sinfo->succs_ok, succ);
4436 VEC_safe_push (int, heap, sinfo->probs_ok,
4437 /* FIXME: Improve calculation when skipping
4438 inner loop to exits. */
4439 (si.bb_end
4440 ? si.e1->probability
4441 : REG_BR_PROB_BASE));
4442 sinfo->succs_ok_n++;
4444 else
4445 VEC_safe_push (rtx, heap, sinfo->succs_other, succ);
4447 /* Compute all_prob. */
4448 if (!si.bb_end)
4449 sinfo->all_prob = REG_BR_PROB_BASE;
4450 else
4451 sinfo->all_prob += si.e1->probability;
4453 sinfo->all_succs_n++;
4456 return sinfo;
4459 /* Return the predecessors of BB in PREDS and their number in N.
4460 Empty blocks are skipped. SIZE is used to allocate PREDS. */
4461 static void
4462 cfg_preds_1 (basic_block bb, insn_t **preds, int *n, int *size)
4464 edge e;
4465 edge_iterator ei;
4467 gcc_assert (BLOCK_TO_BB (bb->index) != 0);
4469 FOR_EACH_EDGE (e, ei, bb->preds)
4471 basic_block pred_bb = e->src;
4472 insn_t bb_end = BB_END (pred_bb);
4474 /* ??? This code is not supposed to walk out of a region. */
4475 gcc_assert (in_current_region_p (pred_bb));
4477 if (sel_bb_empty_p (pred_bb))
4478 cfg_preds_1 (pred_bb, preds, n, size);
4479 else
4481 if (*n == *size)
4482 *preds = XRESIZEVEC (insn_t, *preds,
4483 (*size = 2 * *size + 1));
4484 (*preds)[(*n)++] = bb_end;
4488 gcc_assert (*n != 0);
4491 /* Find all predecessors of BB and record them in PREDS and their number
4492 in N. Empty blocks are skipped, and only normal (forward in-region)
4493 edges are processed. */
4494 static void
4495 cfg_preds (basic_block bb, insn_t **preds, int *n)
4497 int size = 0;
4499 *preds = NULL;
4500 *n = 0;
4501 cfg_preds_1 (bb, preds, n, &size);
4504 /* Returns true if we are moving INSN through join point. */
4505 bool
4506 sel_num_cfg_preds_gt_1 (insn_t insn)
4508 basic_block bb;
4510 if (!sel_bb_head_p (insn) || INSN_BB (insn) == 0)
4511 return false;
4513 bb = BLOCK_FOR_INSN (insn);
4515 while (1)
4517 if (EDGE_COUNT (bb->preds) > 1)
4518 return true;
4520 gcc_assert (EDGE_PRED (bb, 0)->dest == bb);
4521 bb = EDGE_PRED (bb, 0)->src;
4523 if (!sel_bb_empty_p (bb))
4524 break;
4527 return false;
4530 /* Returns true when BB should be the end of an ebb. Adapted from the
4531 code in sched-ebb.c. */
4532 bool
4533 bb_ends_ebb_p (basic_block bb)
4535 basic_block next_bb = bb_next_bb (bb);
4536 edge e;
4537 edge_iterator ei;
4539 if (next_bb == EXIT_BLOCK_PTR
4540 || bitmap_bit_p (forced_ebb_heads, next_bb->index)
4541 || (LABEL_P (BB_HEAD (next_bb))
4542 /* NB: LABEL_NUSES () is not maintained outside of jump.c.
4543 Work around that. */
4544 && !single_pred_p (next_bb)))
4545 return true;
4547 if (!in_current_region_p (next_bb))
4548 return true;
4550 FOR_EACH_EDGE (e, ei, bb->succs)
4551 if ((e->flags & EDGE_FALLTHRU) != 0)
4553 gcc_assert (e->dest == next_bb);
4555 return false;
4558 return true;
4561 /* Returns true when INSN and SUCC are in the same EBB, given that SUCC is a
4562 successor of INSN. */
4563 bool
4564 in_same_ebb_p (insn_t insn, insn_t succ)
4566 basic_block ptr = BLOCK_FOR_INSN (insn);
4568 for(;;)
4570 if (ptr == BLOCK_FOR_INSN (succ))
4571 return true;
4573 if (bb_ends_ebb_p (ptr))
4574 return false;
4576 ptr = bb_next_bb (ptr);
4579 gcc_unreachable ();
4580 return false;
4583 /* Recomputes the reverse topological order for the function and
4584 saves it in REV_TOP_ORDER_INDEX. REV_TOP_ORDER_INDEX_LEN is also
4585 modified appropriately. */
4586 static void
4587 recompute_rev_top_order (void)
4589 int *postorder;
4590 int n_blocks, i;
4592 if (!rev_top_order_index || rev_top_order_index_len < last_basic_block)
4594 rev_top_order_index_len = last_basic_block;
4595 rev_top_order_index = XRESIZEVEC (int, rev_top_order_index,
4596 rev_top_order_index_len);
4599 postorder = XNEWVEC (int, n_basic_blocks);
4601 n_blocks = post_order_compute (postorder, true, false);
4602 gcc_assert (n_basic_blocks == n_blocks);
4604 /* Build reverse function: for each basic block with BB->INDEX == K
4605 rev_top_order_index[K] is it's reverse topological sort number. */
4606 for (i = 0; i < n_blocks; i++)
4608 gcc_assert (postorder[i] < rev_top_order_index_len);
4609 rev_top_order_index[postorder[i]] = i;
4612 free (postorder);
4615 /* Clear all flags from insns in BB that could spoil its rescheduling. */
4616 void
4617 clear_outdated_rtx_info (basic_block bb)
4619 rtx insn;
4621 FOR_BB_INSNS (bb, insn)
4622 if (INSN_P (insn))
4624 SCHED_GROUP_P (insn) = 0;
4625 INSN_AFTER_STALL_P (insn) = 0;
4626 INSN_SCHED_TIMES (insn) = 0;
4627 EXPR_PRIORITY_ADJ (INSN_EXPR (insn)) = 0;
4629 /* We cannot use the changed caches, as previously we could ignore
4630 the LHS dependence due to enabled renaming and transform
4631 the expression, and currently we'll be unable to do this. */
4632 htab_empty (INSN_TRANSFORMED_INSNS (insn));
4636 /* Add BB_NOTE to the pool of available basic block notes. */
4637 static void
4638 return_bb_to_pool (basic_block bb)
4640 rtx note = bb_note (bb);
4642 gcc_assert (NOTE_BASIC_BLOCK (note) == bb
4643 && bb->aux == NULL);
4645 /* It turns out that current cfg infrastructure does not support
4646 reuse of basic blocks. Don't bother for now. */
4647 /*VEC_safe_push (rtx, heap, bb_note_pool, note);*/
4650 /* Get a bb_note from pool or return NULL_RTX if pool is empty. */
4651 static rtx
4652 get_bb_note_from_pool (void)
4654 if (VEC_empty (rtx, bb_note_pool))
4655 return NULL_RTX;
4656 else
4658 rtx note = VEC_pop (rtx, bb_note_pool);
4660 PREV_INSN (note) = NULL_RTX;
4661 NEXT_INSN (note) = NULL_RTX;
4663 return note;
4667 /* Free bb_note_pool. */
4668 void
4669 free_bb_note_pool (void)
4671 VEC_free (rtx, heap, bb_note_pool);
4674 /* Setup scheduler pool and successor structure. */
4675 void
4676 alloc_sched_pools (void)
4678 int succs_size;
4680 succs_size = MAX_WS + 1;
4681 succs_info_pool.stack = XCNEWVEC (struct succs_info, succs_size);
4682 succs_info_pool.size = succs_size;
4683 succs_info_pool.top = -1;
4684 succs_info_pool.max_top = -1;
4686 sched_lists_pool = create_alloc_pool ("sel-sched-lists",
4687 sizeof (struct _list_node), 500);
4690 /* Free the pools. */
4691 void
4692 free_sched_pools (void)
4694 int i;
4696 free_alloc_pool (sched_lists_pool);
4697 gcc_assert (succs_info_pool.top == -1);
4698 for (i = 0; i < succs_info_pool.max_top; i++)
4700 VEC_free (rtx, heap, succs_info_pool.stack[i].succs_ok);
4701 VEC_free (rtx, heap, succs_info_pool.stack[i].succs_other);
4702 VEC_free (int, heap, succs_info_pool.stack[i].probs_ok);
4704 free (succs_info_pool.stack);
4708 /* Returns a position in RGN where BB can be inserted retaining
4709 topological order. */
4710 static int
4711 find_place_to_insert_bb (basic_block bb, int rgn)
4713 bool has_preds_outside_rgn = false;
4714 edge e;
4715 edge_iterator ei;
4717 /* Find whether we have preds outside the region. */
4718 FOR_EACH_EDGE (e, ei, bb->preds)
4719 if (!in_current_region_p (e->src))
4721 has_preds_outside_rgn = true;
4722 break;
4725 /* Recompute the top order -- needed when we have > 1 pred
4726 and in case we don't have preds outside. */
4727 if (flag_sel_sched_pipelining_outer_loops
4728 && (has_preds_outside_rgn || EDGE_COUNT (bb->preds) > 1))
4730 int i, bbi = bb->index, cur_bbi;
4732 recompute_rev_top_order ();
4733 for (i = RGN_NR_BLOCKS (rgn) - 1; i >= 0; i--)
4735 cur_bbi = BB_TO_BLOCK (i);
4736 if (rev_top_order_index[bbi]
4737 < rev_top_order_index[cur_bbi])
4738 break;
4741 /* We skipped the right block, so we increase i. We accomodate
4742 it for increasing by step later, so we decrease i. */
4743 return (i + 1) - 1;
4745 else if (has_preds_outside_rgn)
4747 /* This is the case when we generate an extra empty block
4748 to serve as region head during pipelining. */
4749 e = EDGE_SUCC (bb, 0);
4750 gcc_assert (EDGE_COUNT (bb->succs) == 1
4751 && in_current_region_p (EDGE_SUCC (bb, 0)->dest)
4752 && (BLOCK_TO_BB (e->dest->index) == 0));
4753 return -1;
4756 /* We don't have preds outside the region. We should have
4757 the only pred, because the multiple preds case comes from
4758 the pipelining of outer loops, and that is handled above.
4759 Just take the bbi of this single pred. */
4760 if (EDGE_COUNT (bb->succs) > 0)
4762 int pred_bbi;
4764 gcc_assert (EDGE_COUNT (bb->preds) == 1);
4766 pred_bbi = EDGE_PRED (bb, 0)->src->index;
4767 return BLOCK_TO_BB (pred_bbi);
4769 else
4770 /* BB has no successors. It is safe to put it in the end. */
4771 return current_nr_blocks - 1;
4774 /* Deletes an empty basic block freeing its data. */
4775 static void
4776 delete_and_free_basic_block (basic_block bb)
4778 gcc_assert (sel_bb_empty_p (bb));
4780 if (BB_LV_SET (bb))
4781 free_lv_set (bb);
4783 bitmap_clear_bit (blocks_to_reschedule, bb->index);
4785 /* Can't assert av_set properties because we use sel_aremove_bb
4786 when removing loop preheader from the region. At the point of
4787 removing the preheader we already have deallocated sel_region_bb_info. */
4788 gcc_assert (BB_LV_SET (bb) == NULL
4789 && !BB_LV_SET_VALID_P (bb)
4790 && BB_AV_LEVEL (bb) == 0
4791 && BB_AV_SET (bb) == NULL);
4793 delete_basic_block (bb);
4796 /* Add BB to the current region and update the region data. */
4797 static void
4798 add_block_to_current_region (basic_block bb)
4800 int i, pos, bbi = -2, rgn;
4802 rgn = CONTAINING_RGN (BB_TO_BLOCK (0));
4803 bbi = find_place_to_insert_bb (bb, rgn);
4804 bbi += 1;
4805 pos = RGN_BLOCKS (rgn) + bbi;
4807 gcc_assert (RGN_HAS_REAL_EBB (rgn) == 0
4808 && ebb_head[bbi] == pos);
4810 /* Make a place for the new block. */
4811 extend_regions ();
4813 for (i = RGN_BLOCKS (rgn + 1) - 1; i >= pos; i--)
4814 BLOCK_TO_BB (rgn_bb_table[i])++;
4816 memmove (rgn_bb_table + pos + 1,
4817 rgn_bb_table + pos,
4818 (RGN_BLOCKS (nr_regions) - pos) * sizeof (*rgn_bb_table));
4820 /* Initialize data for BB. */
4821 rgn_bb_table[pos] = bb->index;
4822 BLOCK_TO_BB (bb->index) = bbi;
4823 CONTAINING_RGN (bb->index) = rgn;
4825 RGN_NR_BLOCKS (rgn)++;
4827 for (i = rgn + 1; i <= nr_regions; i++)
4828 RGN_BLOCKS (i)++;
4831 /* Remove BB from the current region and update the region data. */
4832 static void
4833 remove_bb_from_region (basic_block bb)
4835 int i, pos, bbi = -2, rgn;
4837 rgn = CONTAINING_RGN (BB_TO_BLOCK (0));
4838 bbi = BLOCK_TO_BB (bb->index);
4839 pos = RGN_BLOCKS (rgn) + bbi;
4841 gcc_assert (RGN_HAS_REAL_EBB (rgn) == 0
4842 && ebb_head[bbi] == pos);
4844 for (i = RGN_BLOCKS (rgn + 1) - 1; i >= pos; i--)
4845 BLOCK_TO_BB (rgn_bb_table[i])--;
4847 memmove (rgn_bb_table + pos,
4848 rgn_bb_table + pos + 1,
4849 (RGN_BLOCKS (nr_regions) - pos) * sizeof (*rgn_bb_table));
4851 RGN_NR_BLOCKS (rgn)--;
4852 for (i = rgn + 1; i <= nr_regions; i++)
4853 RGN_BLOCKS (i)--;
4856 /* Add BB to the current region and update all data. If BB is NULL, add all
4857 blocks from last_added_blocks vector. */
4858 static void
4859 sel_add_bb (basic_block bb)
4861 /* Extend luids so that new notes will receive zero luids. */
4862 sched_init_luids (NULL, NULL, NULL, NULL);
4863 sched_init_bbs ();
4864 sel_init_bbs (last_added_blocks, NULL);
4866 /* When bb is passed explicitly, the vector should contain
4867 the only element that equals to bb; otherwise, the vector
4868 should not be NULL. */
4869 gcc_assert (last_added_blocks != NULL);
4871 if (bb != NULL)
4873 gcc_assert (VEC_length (basic_block, last_added_blocks) == 1
4874 && VEC_index (basic_block,
4875 last_added_blocks, 0) == bb);
4876 add_block_to_current_region (bb);
4878 /* We associate creating/deleting data sets with the first insn
4879 appearing / disappearing in the bb. */
4880 if (!sel_bb_empty_p (bb) && BB_LV_SET (bb) == NULL)
4881 create_initial_data_sets (bb);
4883 VEC_free (basic_block, heap, last_added_blocks);
4885 else
4886 /* BB is NULL - process LAST_ADDED_BLOCKS instead. */
4888 int i;
4889 basic_block temp_bb = NULL;
4891 for (i = 0;
4892 VEC_iterate (basic_block, last_added_blocks, i, bb); i++)
4894 add_block_to_current_region (bb);
4895 temp_bb = bb;
4898 /* We need to fetch at least one bb so we know the region
4899 to update. */
4900 gcc_assert (temp_bb != NULL);
4901 bb = temp_bb;
4903 VEC_free (basic_block, heap, last_added_blocks);
4906 rgn_setup_region (CONTAINING_RGN (bb->index));
4909 /* Remove BB from the current region and update all data.
4910 If REMOVE_FROM_CFG_PBB is true, also remove the block cfom cfg. */
4911 static void
4912 sel_remove_bb (basic_block bb, bool remove_from_cfg_p)
4914 gcc_assert (bb != NULL && BB_NOTE_LIST (bb) == NULL_RTX);
4916 remove_bb_from_region (bb);
4917 return_bb_to_pool (bb);
4918 bitmap_clear_bit (blocks_to_reschedule, bb->index);
4920 if (remove_from_cfg_p)
4921 delete_and_free_basic_block (bb);
4923 rgn_setup_region (CONTAINING_RGN (bb->index));
4926 /* Concatenate info of EMPTY_BB to info of MERGE_BB. */
4927 static void
4928 move_bb_info (basic_block merge_bb, basic_block empty_bb)
4930 gcc_assert (in_current_region_p (merge_bb));
4932 concat_note_lists (BB_NOTE_LIST (empty_bb),
4933 &BB_NOTE_LIST (merge_bb));
4934 BB_NOTE_LIST (empty_bb) = NULL_RTX;
4938 /* Remove an empty basic block EMPTY_BB. When MERGE_UP_P is true, we put
4939 EMPTY_BB's note lists into its predecessor instead of putting them
4940 into the successor. When REMOVE_FROM_CFG_P is true, also remove
4941 the empty block. */
4942 void
4943 sel_remove_empty_bb (basic_block empty_bb, bool merge_up_p,
4944 bool remove_from_cfg_p)
4946 basic_block merge_bb;
4948 gcc_assert (sel_bb_empty_p (empty_bb));
4950 if (merge_up_p)
4952 merge_bb = empty_bb->prev_bb;
4953 gcc_assert (EDGE_COUNT (empty_bb->preds) == 1
4954 && EDGE_PRED (empty_bb, 0)->src == merge_bb);
4956 else
4958 edge e;
4959 edge_iterator ei;
4961 merge_bb = bb_next_bb (empty_bb);
4963 /* Redirect incoming edges (except fallthrough one) of EMPTY_BB to its
4964 successor block. */
4965 for (ei = ei_start (empty_bb->preds);
4966 (e = ei_safe_edge (ei)); )
4968 if (! (e->flags & EDGE_FALLTHRU))
4969 sel_redirect_edge_and_branch (e, merge_bb);
4970 else
4971 ei_next (&ei);
4974 gcc_assert (EDGE_COUNT (empty_bb->succs) == 1
4975 && EDGE_SUCC (empty_bb, 0)->dest == merge_bb);
4978 move_bb_info (merge_bb, empty_bb);
4979 remove_empty_bb (empty_bb, remove_from_cfg_p);
4982 /* Remove EMPTY_BB. If REMOVE_FROM_CFG_P is false, remove EMPTY_BB from
4983 region, but keep it in CFG. */
4984 static void
4985 remove_empty_bb (basic_block empty_bb, bool remove_from_cfg_p)
4987 /* The block should contain just a note or a label.
4988 We try to check whether it is unused below. */
4989 gcc_assert (BB_HEAD (empty_bb) == BB_END (empty_bb)
4990 || LABEL_P (BB_HEAD (empty_bb)));
4992 /* If basic block has predecessors or successors, redirect them. */
4993 if (remove_from_cfg_p
4994 && (EDGE_COUNT (empty_bb->preds) > 0
4995 || EDGE_COUNT (empty_bb->succs) > 0))
4997 basic_block pred;
4998 basic_block succ;
5000 /* We need to init PRED and SUCC before redirecting edges. */
5001 if (EDGE_COUNT (empty_bb->preds) > 0)
5003 edge e;
5005 gcc_assert (EDGE_COUNT (empty_bb->preds) == 1);
5007 e = EDGE_PRED (empty_bb, 0);
5008 gcc_assert (e->src == empty_bb->prev_bb
5009 && (e->flags & EDGE_FALLTHRU));
5011 pred = empty_bb->prev_bb;
5013 else
5014 pred = NULL;
5016 if (EDGE_COUNT (empty_bb->succs) > 0)
5018 /* We do not check fallthruness here as above, because
5019 after removing a jump the edge may actually be not fallthru. */
5020 gcc_assert (EDGE_COUNT (empty_bb->succs) == 1);
5021 succ = EDGE_SUCC (empty_bb, 0)->dest;
5023 else
5024 succ = NULL;
5026 if (EDGE_COUNT (empty_bb->preds) > 0 && succ != NULL)
5028 edge e = EDGE_PRED (empty_bb, 0);
5030 if (e->flags & EDGE_FALLTHRU)
5031 redirect_edge_succ_nodup (e, succ);
5032 else
5033 sel_redirect_edge_and_branch (EDGE_PRED (empty_bb, 0), succ);
5036 if (EDGE_COUNT (empty_bb->succs) > 0 && pred != NULL)
5038 edge e = EDGE_SUCC (empty_bb, 0);
5040 if (find_edge (pred, e->dest) == NULL)
5041 redirect_edge_pred (e, pred);
5045 /* Finish removing. */
5046 sel_remove_bb (empty_bb, remove_from_cfg_p);
5049 /* An implementation of create_basic_block hook, which additionally updates
5050 per-bb data structures. */
5051 static basic_block
5052 sel_create_basic_block (void *headp, void *endp, basic_block after)
5054 basic_block new_bb;
5055 insn_t new_bb_note;
5057 gcc_assert (flag_sel_sched_pipelining_outer_loops
5058 || last_added_blocks == NULL);
5060 new_bb_note = get_bb_note_from_pool ();
5062 if (new_bb_note == NULL_RTX)
5063 new_bb = orig_cfg_hooks.create_basic_block (headp, endp, after);
5064 else
5066 new_bb = create_basic_block_structure ((rtx) headp, (rtx) endp,
5067 new_bb_note, after);
5068 new_bb->aux = NULL;
5071 VEC_safe_push (basic_block, heap, last_added_blocks, new_bb);
5073 return new_bb;
5076 /* Implement sched_init_only_bb (). */
5077 static void
5078 sel_init_only_bb (basic_block bb, basic_block after)
5080 gcc_assert (after == NULL);
5082 extend_regions ();
5083 rgn_make_new_region_out_of_new_block (bb);
5086 /* Update the latch when we've splitted or merged it from FROM block to TO.
5087 This should be checked for all outer loops, too. */
5088 static void
5089 change_loops_latches (basic_block from, basic_block to)
5091 gcc_assert (from != to);
5093 if (current_loop_nest)
5095 struct loop *loop;
5097 for (loop = current_loop_nest; loop; loop = loop_outer (loop))
5098 if (considered_for_pipelining_p (loop) && loop->latch == from)
5100 gcc_assert (loop == current_loop_nest);
5101 loop->latch = to;
5102 gcc_assert (loop_latch_edge (loop));
5107 /* Splits BB on two basic blocks, adding it to the region and extending
5108 per-bb data structures. Returns the newly created bb. */
5109 static basic_block
5110 sel_split_block (basic_block bb, rtx after)
5112 basic_block new_bb;
5113 insn_t insn;
5115 new_bb = sched_split_block_1 (bb, after);
5116 sel_add_bb (new_bb);
5118 /* This should be called after sel_add_bb, because this uses
5119 CONTAINING_RGN for the new block, which is not yet initialized.
5120 FIXME: this function may be a no-op now. */
5121 change_loops_latches (bb, new_bb);
5123 /* Update ORIG_BB_INDEX for insns moved into the new block. */
5124 FOR_BB_INSNS (new_bb, insn)
5125 if (INSN_P (insn))
5126 EXPR_ORIG_BB_INDEX (INSN_EXPR (insn)) = new_bb->index;
5128 if (sel_bb_empty_p (bb))
5130 gcc_assert (!sel_bb_empty_p (new_bb));
5132 /* NEW_BB has data sets that need to be updated and BB holds
5133 data sets that should be removed. Exchange these data sets
5134 so that we won't lose BB's valid data sets. */
5135 exchange_data_sets (new_bb, bb);
5136 free_data_sets (bb);
5139 if (!sel_bb_empty_p (new_bb)
5140 && bitmap_bit_p (blocks_to_reschedule, bb->index))
5141 bitmap_set_bit (blocks_to_reschedule, new_bb->index);
5143 return new_bb;
5146 /* If BB ends with a jump insn whose ID is bigger then PREV_MAX_UID, return it.
5147 Otherwise returns NULL. */
5148 static rtx
5149 check_for_new_jump (basic_block bb, int prev_max_uid)
5151 rtx end;
5153 end = sel_bb_end (bb);
5154 if (end && INSN_UID (end) >= prev_max_uid)
5155 return end;
5156 return NULL;
5159 /* Look for a new jump either in FROM_BB block or in newly created JUMP_BB block.
5160 New means having UID at least equal to PREV_MAX_UID. */
5161 static rtx
5162 find_new_jump (basic_block from, basic_block jump_bb, int prev_max_uid)
5164 rtx jump;
5166 /* Return immediately if no new insns were emitted. */
5167 if (get_max_uid () == prev_max_uid)
5168 return NULL;
5170 /* Now check both blocks for new jumps. It will ever be only one. */
5171 if ((jump = check_for_new_jump (from, prev_max_uid)))
5172 return jump;
5174 if (jump_bb != NULL
5175 && (jump = check_for_new_jump (jump_bb, prev_max_uid)))
5176 return jump;
5177 return NULL;
5180 /* Splits E and adds the newly created basic block to the current region.
5181 Returns this basic block. */
5182 basic_block
5183 sel_split_edge (edge e)
5185 basic_block new_bb, src, other_bb = NULL;
5186 int prev_max_uid;
5187 rtx jump;
5189 src = e->src;
5190 prev_max_uid = get_max_uid ();
5191 new_bb = split_edge (e);
5193 if (flag_sel_sched_pipelining_outer_loops
5194 && current_loop_nest)
5196 int i;
5197 basic_block bb;
5199 /* Some of the basic blocks might not have been added to the loop.
5200 Add them here, until this is fixed in force_fallthru. */
5201 for (i = 0;
5202 VEC_iterate (basic_block, last_added_blocks, i, bb); i++)
5203 if (!bb->loop_father)
5205 add_bb_to_loop (bb, e->dest->loop_father);
5207 gcc_assert (!other_bb && (new_bb->index != bb->index));
5208 other_bb = bb;
5212 /* Add all last_added_blocks to the region. */
5213 sel_add_bb (NULL);
5215 jump = find_new_jump (src, new_bb, prev_max_uid);
5216 if (jump)
5217 sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP);
5219 /* Put the correct lv set on this block. */
5220 if (other_bb && !sel_bb_empty_p (other_bb))
5221 compute_live (sel_bb_head (other_bb));
5223 return new_bb;
5226 /* Implement sched_create_empty_bb (). */
5227 static basic_block
5228 sel_create_empty_bb (basic_block after)
5230 basic_block new_bb;
5232 new_bb = sched_create_empty_bb_1 (after);
5234 /* We'll explicitly initialize NEW_BB via sel_init_only_bb () a bit
5235 later. */
5236 gcc_assert (VEC_length (basic_block, last_added_blocks) == 1
5237 && VEC_index (basic_block, last_added_blocks, 0) == new_bb);
5239 VEC_free (basic_block, heap, last_added_blocks);
5240 return new_bb;
5243 /* Implement sched_create_recovery_block. ORIG_INSN is where block
5244 will be splitted to insert a check. */
5245 basic_block
5246 sel_create_recovery_block (insn_t orig_insn)
5248 basic_block first_bb, second_bb, recovery_block;
5249 basic_block before_recovery = NULL;
5250 rtx jump;
5252 first_bb = BLOCK_FOR_INSN (orig_insn);
5253 if (sel_bb_end_p (orig_insn))
5255 /* Avoid introducing an empty block while splitting. */
5256 gcc_assert (single_succ_p (first_bb));
5257 second_bb = single_succ (first_bb);
5259 else
5260 second_bb = sched_split_block (first_bb, orig_insn);
5262 recovery_block = sched_create_recovery_block (&before_recovery);
5263 if (before_recovery)
5264 copy_lv_set_from (before_recovery, EXIT_BLOCK_PTR);
5266 gcc_assert (sel_bb_empty_p (recovery_block));
5267 sched_create_recovery_edges (first_bb, recovery_block, second_bb);
5268 if (current_loops != NULL)
5269 add_bb_to_loop (recovery_block, first_bb->loop_father);
5271 sel_add_bb (recovery_block);
5273 jump = BB_END (recovery_block);
5274 gcc_assert (sel_bb_head (recovery_block) == jump);
5275 sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP);
5277 return recovery_block;
5280 /* Merge basic block B into basic block A. */
5281 void
5282 sel_merge_blocks (basic_block a, basic_block b)
5284 sel_remove_empty_bb (b, true, false);
5285 merge_blocks (a, b);
5287 change_loops_latches (b, a);
5290 /* A wrapper for redirect_edge_and_branch_force, which also initializes
5291 data structures for possibly created bb and insns. Returns the newly
5292 added bb or NULL, when a bb was not needed. */
5293 void
5294 sel_redirect_edge_and_branch_force (edge e, basic_block to)
5296 basic_block jump_bb, src;
5297 int prev_max_uid;
5298 rtx jump;
5300 gcc_assert (!sel_bb_empty_p (e->src));
5302 src = e->src;
5303 prev_max_uid = get_max_uid ();
5304 jump_bb = redirect_edge_and_branch_force (e, to);
5306 if (jump_bb != NULL)
5307 sel_add_bb (jump_bb);
5309 /* This function could not be used to spoil the loop structure by now,
5310 thus we don't care to update anything. But check it to be sure. */
5311 if (current_loop_nest
5312 && pipelining_p)
5313 gcc_assert (loop_latch_edge (current_loop_nest));
5315 jump = find_new_jump (src, jump_bb, prev_max_uid);
5316 if (jump)
5317 sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP);
5320 /* A wrapper for redirect_edge_and_branch. */
5321 void
5322 sel_redirect_edge_and_branch (edge e, basic_block to)
5324 bool latch_edge_p;
5325 basic_block src;
5326 int prev_max_uid;
5327 rtx jump;
5328 edge redirected;
5330 latch_edge_p = (pipelining_p
5331 && current_loop_nest
5332 && e == loop_latch_edge (current_loop_nest));
5334 src = e->src;
5335 prev_max_uid = get_max_uid ();
5337 redirected = redirect_edge_and_branch (e, to);
5339 gcc_assert (redirected && last_added_blocks == NULL);
5341 /* When we've redirected a latch edge, update the header. */
5342 if (latch_edge_p)
5344 current_loop_nest->header = to;
5345 gcc_assert (loop_latch_edge (current_loop_nest));
5348 jump = find_new_jump (src, NULL, prev_max_uid);
5349 if (jump)
5350 sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP);
5353 /* This variable holds the cfg hooks used by the selective scheduler. */
5354 static struct cfg_hooks sel_cfg_hooks;
5356 /* Register sel-sched cfg hooks. */
5357 void
5358 sel_register_cfg_hooks (void)
5360 sched_split_block = sel_split_block;
5362 orig_cfg_hooks = get_cfg_hooks ();
5363 sel_cfg_hooks = orig_cfg_hooks;
5365 sel_cfg_hooks.create_basic_block = sel_create_basic_block;
5367 set_cfg_hooks (sel_cfg_hooks);
5369 sched_init_only_bb = sel_init_only_bb;
5370 sched_split_block = sel_split_block;
5371 sched_create_empty_bb = sel_create_empty_bb;
5374 /* Unregister sel-sched cfg hooks. */
5375 void
5376 sel_unregister_cfg_hooks (void)
5378 sched_create_empty_bb = NULL;
5379 sched_split_block = NULL;
5380 sched_init_only_bb = NULL;
5382 set_cfg_hooks (orig_cfg_hooks);
5386 /* Emit an insn rtx based on PATTERN. If a jump insn is wanted,
5387 LABEL is where this jump should be directed. */
5389 create_insn_rtx_from_pattern (rtx pattern, rtx label)
5391 rtx insn_rtx;
5393 gcc_assert (!INSN_P (pattern));
5395 start_sequence ();
5397 if (label == NULL_RTX)
5398 insn_rtx = emit_insn (pattern);
5399 else if (DEBUG_INSN_P (label))
5400 insn_rtx = emit_debug_insn (pattern);
5401 else
5403 insn_rtx = emit_jump_insn (pattern);
5404 JUMP_LABEL (insn_rtx) = label;
5405 ++LABEL_NUSES (label);
5408 end_sequence ();
5410 sched_init_luids (NULL, NULL, NULL, NULL);
5411 sched_extend_target ();
5412 sched_deps_init (false);
5414 /* Initialize INSN_CODE now. */
5415 recog_memoized (insn_rtx);
5416 return insn_rtx;
5419 /* Create a new vinsn for INSN_RTX. FORCE_UNIQUE_P is true when the vinsn
5420 must not be clonable. */
5421 vinsn_t
5422 create_vinsn_from_insn_rtx (rtx insn_rtx, bool force_unique_p)
5424 gcc_assert (INSN_P (insn_rtx) && !INSN_IN_STREAM_P (insn_rtx));
5426 /* If VINSN_TYPE is not USE, retain its uniqueness. */
5427 return vinsn_create (insn_rtx, force_unique_p);
5430 /* Create a copy of INSN_RTX. */
5432 create_copy_of_insn_rtx (rtx insn_rtx)
5434 rtx res;
5436 if (DEBUG_INSN_P (insn_rtx))
5437 return create_insn_rtx_from_pattern (copy_rtx (PATTERN (insn_rtx)),
5438 insn_rtx);
5440 gcc_assert (NONJUMP_INSN_P (insn_rtx));
5442 res = create_insn_rtx_from_pattern (copy_rtx (PATTERN (insn_rtx)),
5443 NULL_RTX);
5444 return res;
5447 /* Change vinsn field of EXPR to hold NEW_VINSN. */
5448 void
5449 change_vinsn_in_expr (expr_t expr, vinsn_t new_vinsn)
5451 vinsn_detach (EXPR_VINSN (expr));
5453 EXPR_VINSN (expr) = new_vinsn;
5454 vinsn_attach (new_vinsn);
5457 /* Helpers for global init. */
5458 /* This structure is used to be able to call existing bundling mechanism
5459 and calculate insn priorities. */
5460 static struct haifa_sched_info sched_sel_haifa_sched_info =
5462 NULL, /* init_ready_list */
5463 NULL, /* can_schedule_ready_p */
5464 NULL, /* schedule_more_p */
5465 NULL, /* new_ready */
5466 NULL, /* rgn_rank */
5467 sel_print_insn, /* rgn_print_insn */
5468 contributes_to_priority,
5469 NULL, /* insn_finishes_block_p */
5471 NULL, NULL,
5472 NULL, NULL,
5473 0, 0,
5475 NULL, /* add_remove_insn */
5476 NULL, /* begin_schedule_ready */
5477 NULL, /* advance_target_bb */
5478 SEL_SCHED | NEW_BBS
5481 /* Setup special insns used in the scheduler. */
5482 void
5483 setup_nop_and_exit_insns (void)
5485 gcc_assert (nop_pattern == NULL_RTX
5486 && exit_insn == NULL_RTX);
5488 nop_pattern = gen_nop ();
5490 start_sequence ();
5491 emit_insn (nop_pattern);
5492 exit_insn = get_insns ();
5493 end_sequence ();
5494 set_block_for_insn (exit_insn, EXIT_BLOCK_PTR);
5497 /* Free special insns used in the scheduler. */
5498 void
5499 free_nop_and_exit_insns (void)
5501 exit_insn = NULL_RTX;
5502 nop_pattern = NULL_RTX;
5505 /* Setup a special vinsn used in new insns initialization. */
5506 void
5507 setup_nop_vinsn (void)
5509 nop_vinsn = vinsn_create (exit_insn, false);
5510 vinsn_attach (nop_vinsn);
5513 /* Free a special vinsn used in new insns initialization. */
5514 void
5515 free_nop_vinsn (void)
5517 gcc_assert (VINSN_COUNT (nop_vinsn) == 1);
5518 vinsn_detach (nop_vinsn);
5519 nop_vinsn = NULL;
5522 /* Call a set_sched_flags hook. */
5523 void
5524 sel_set_sched_flags (void)
5526 /* ??? This means that set_sched_flags were called, and we decided to
5527 support speculation. However, set_sched_flags also modifies flags
5528 on current_sched_info, doing this only at global init. And we
5529 sometimes change c_s_i later. So put the correct flags again. */
5530 if (spec_info && targetm.sched.set_sched_flags)
5531 targetm.sched.set_sched_flags (spec_info);
5534 /* Setup pointers to global sched info structures. */
5535 void
5536 sel_setup_sched_infos (void)
5538 rgn_setup_common_sched_info ();
5540 memcpy (&sel_common_sched_info, common_sched_info,
5541 sizeof (sel_common_sched_info));
5543 sel_common_sched_info.fix_recovery_cfg = NULL;
5544 sel_common_sched_info.add_block = NULL;
5545 sel_common_sched_info.estimate_number_of_insns
5546 = sel_estimate_number_of_insns;
5547 sel_common_sched_info.luid_for_non_insn = sel_luid_for_non_insn;
5548 sel_common_sched_info.sched_pass_id = SCHED_SEL_PASS;
5550 common_sched_info = &sel_common_sched_info;
5552 current_sched_info = &sched_sel_haifa_sched_info;
5553 current_sched_info->sched_max_insns_priority =
5554 get_rgn_sched_max_insns_priority ();
5556 sel_set_sched_flags ();
5560 /* Adds basic block BB to region RGN at the position *BB_ORD_INDEX,
5561 *BB_ORD_INDEX after that is increased. */
5562 static void
5563 sel_add_block_to_region (basic_block bb, int *bb_ord_index, int rgn)
5565 RGN_NR_BLOCKS (rgn) += 1;
5566 RGN_DONT_CALC_DEPS (rgn) = 0;
5567 RGN_HAS_REAL_EBB (rgn) = 0;
5568 CONTAINING_RGN (bb->index) = rgn;
5569 BLOCK_TO_BB (bb->index) = *bb_ord_index;
5570 rgn_bb_table[RGN_BLOCKS (rgn) + *bb_ord_index] = bb->index;
5571 (*bb_ord_index)++;
5573 /* FIXME: it is true only when not scheduling ebbs. */
5574 RGN_BLOCKS (rgn + 1) = RGN_BLOCKS (rgn) + RGN_NR_BLOCKS (rgn);
5577 /* Functions to support pipelining of outer loops. */
5579 /* Creates a new empty region and returns it's number. */
5580 static int
5581 sel_create_new_region (void)
5583 int new_rgn_number = nr_regions;
5585 RGN_NR_BLOCKS (new_rgn_number) = 0;
5587 /* FIXME: This will work only when EBBs are not created. */
5588 if (new_rgn_number != 0)
5589 RGN_BLOCKS (new_rgn_number) = RGN_BLOCKS (new_rgn_number - 1) +
5590 RGN_NR_BLOCKS (new_rgn_number - 1);
5591 else
5592 RGN_BLOCKS (new_rgn_number) = 0;
5594 /* Set the blocks of the next region so the other functions may
5595 calculate the number of blocks in the region. */
5596 RGN_BLOCKS (new_rgn_number + 1) = RGN_BLOCKS (new_rgn_number) +
5597 RGN_NR_BLOCKS (new_rgn_number);
5599 nr_regions++;
5601 return new_rgn_number;
5604 /* If X has a smaller topological sort number than Y, returns -1;
5605 if greater, returns 1. */
5606 static int
5607 bb_top_order_comparator (const void *x, const void *y)
5609 basic_block bb1 = *(const basic_block *) x;
5610 basic_block bb2 = *(const basic_block *) y;
5612 gcc_assert (bb1 == bb2
5613 || rev_top_order_index[bb1->index]
5614 != rev_top_order_index[bb2->index]);
5616 /* It's a reverse topological order in REV_TOP_ORDER_INDEX, so
5617 bbs with greater number should go earlier. */
5618 if (rev_top_order_index[bb1->index] > rev_top_order_index[bb2->index])
5619 return -1;
5620 else
5621 return 1;
5624 /* Create a region for LOOP and return its number. If we don't want
5625 to pipeline LOOP, return -1. */
5626 static int
5627 make_region_from_loop (struct loop *loop)
5629 unsigned int i;
5630 int new_rgn_number = -1;
5631 struct loop *inner;
5633 /* Basic block index, to be assigned to BLOCK_TO_BB. */
5634 int bb_ord_index = 0;
5635 basic_block *loop_blocks;
5636 basic_block preheader_block;
5638 if (loop->num_nodes
5639 > (unsigned) PARAM_VALUE (PARAM_MAX_PIPELINE_REGION_BLOCKS))
5640 return -1;
5642 /* Don't pipeline loops whose latch belongs to some of its inner loops. */
5643 for (inner = loop->inner; inner; inner = inner->inner)
5644 if (flow_bb_inside_loop_p (inner, loop->latch))
5645 return -1;
5647 loop->ninsns = num_loop_insns (loop);
5648 if ((int) loop->ninsns > PARAM_VALUE (PARAM_MAX_PIPELINE_REGION_INSNS))
5649 return -1;
5651 loop_blocks = get_loop_body_in_custom_order (loop, bb_top_order_comparator);
5653 for (i = 0; i < loop->num_nodes; i++)
5654 if (loop_blocks[i]->flags & BB_IRREDUCIBLE_LOOP)
5656 free (loop_blocks);
5657 return -1;
5660 preheader_block = loop_preheader_edge (loop)->src;
5661 gcc_assert (preheader_block);
5662 gcc_assert (loop_blocks[0] == loop->header);
5664 new_rgn_number = sel_create_new_region ();
5666 sel_add_block_to_region (preheader_block, &bb_ord_index, new_rgn_number);
5667 SET_BIT (bbs_in_loop_rgns, preheader_block->index);
5669 for (i = 0; i < loop->num_nodes; i++)
5671 /* Add only those blocks that haven't been scheduled in the inner loop.
5672 The exception is the basic blocks with bookkeeping code - they should
5673 be added to the region (and they actually don't belong to the loop
5674 body, but to the region containing that loop body). */
5676 gcc_assert (new_rgn_number >= 0);
5678 if (! TEST_BIT (bbs_in_loop_rgns, loop_blocks[i]->index))
5680 sel_add_block_to_region (loop_blocks[i], &bb_ord_index,
5681 new_rgn_number);
5682 SET_BIT (bbs_in_loop_rgns, loop_blocks[i]->index);
5686 free (loop_blocks);
5687 MARK_LOOP_FOR_PIPELINING (loop);
5689 return new_rgn_number;
5692 /* Create a new region from preheader blocks LOOP_BLOCKS. */
5693 void
5694 make_region_from_loop_preheader (VEC(basic_block, heap) **loop_blocks)
5696 unsigned int i;
5697 int new_rgn_number = -1;
5698 basic_block bb;
5700 /* Basic block index, to be assigned to BLOCK_TO_BB. */
5701 int bb_ord_index = 0;
5703 new_rgn_number = sel_create_new_region ();
5705 for (i = 0; VEC_iterate (basic_block, *loop_blocks, i, bb); i++)
5707 gcc_assert (new_rgn_number >= 0);
5709 sel_add_block_to_region (bb, &bb_ord_index, new_rgn_number);
5712 VEC_free (basic_block, heap, *loop_blocks);
5713 gcc_assert (*loop_blocks == NULL);
5717 /* Create region(s) from loop nest LOOP, such that inner loops will be
5718 pipelined before outer loops. Returns true when a region for LOOP
5719 is created. */
5720 static bool
5721 make_regions_from_loop_nest (struct loop *loop)
5723 struct loop *cur_loop;
5724 int rgn_number;
5726 /* Traverse all inner nodes of the loop. */
5727 for (cur_loop = loop->inner; cur_loop; cur_loop = cur_loop->next)
5728 if (! TEST_BIT (bbs_in_loop_rgns, cur_loop->header->index))
5729 return false;
5731 /* At this moment all regular inner loops should have been pipelined.
5732 Try to create a region from this loop. */
5733 rgn_number = make_region_from_loop (loop);
5735 if (rgn_number < 0)
5736 return false;
5738 VEC_safe_push (loop_p, heap, loop_nests, loop);
5739 return true;
5742 /* Initalize data structures needed. */
5743 void
5744 sel_init_pipelining (void)
5746 /* Collect loop information to be used in outer loops pipelining. */
5747 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
5748 | LOOPS_HAVE_FALLTHRU_PREHEADERS
5749 | LOOPS_HAVE_RECORDED_EXITS
5750 | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS);
5751 current_loop_nest = NULL;
5753 bbs_in_loop_rgns = sbitmap_alloc (last_basic_block);
5754 sbitmap_zero (bbs_in_loop_rgns);
5756 recompute_rev_top_order ();
5759 /* Returns a struct loop for region RGN. */
5760 loop_p
5761 get_loop_nest_for_rgn (unsigned int rgn)
5763 /* Regions created with extend_rgns don't have corresponding loop nests,
5764 because they don't represent loops. */
5765 if (rgn < VEC_length (loop_p, loop_nests))
5766 return VEC_index (loop_p, loop_nests, rgn);
5767 else
5768 return NULL;
5771 /* True when LOOP was included into pipelining regions. */
5772 bool
5773 considered_for_pipelining_p (struct loop *loop)
5775 if (loop_depth (loop) == 0)
5776 return false;
5778 /* Now, the loop could be too large or irreducible. Check whether its
5779 region is in LOOP_NESTS.
5780 We determine the region number of LOOP as the region number of its
5781 latch. We can't use header here, because this header could be
5782 just removed preheader and it will give us the wrong region number.
5783 Latch can't be used because it could be in the inner loop too. */
5784 if (LOOP_MARKED_FOR_PIPELINING_P (loop) && pipelining_p)
5786 int rgn = CONTAINING_RGN (loop->latch->index);
5788 gcc_assert ((unsigned) rgn < VEC_length (loop_p, loop_nests));
5789 return true;
5792 return false;
5795 /* Makes regions from the rest of the blocks, after loops are chosen
5796 for pipelining. */
5797 static void
5798 make_regions_from_the_rest (void)
5800 int cur_rgn_blocks;
5801 int *loop_hdr;
5802 int i;
5804 basic_block bb;
5805 edge e;
5806 edge_iterator ei;
5807 int *degree;
5808 int new_regions;
5810 /* Index in rgn_bb_table where to start allocating new regions. */
5811 cur_rgn_blocks = nr_regions ? RGN_BLOCKS (nr_regions) : 0;
5812 new_regions = nr_regions;
5814 /* Make regions from all the rest basic blocks - those that don't belong to
5815 any loop or belong to irreducible loops. Prepare the data structures
5816 for extend_rgns. */
5818 /* LOOP_HDR[I] == -1 if I-th bb doesn't belong to any loop,
5819 LOOP_HDR[I] == LOOP_HDR[J] iff basic blocks I and J reside within the same
5820 loop. */
5821 loop_hdr = XNEWVEC (int, last_basic_block);
5822 degree = XCNEWVEC (int, last_basic_block);
5825 /* For each basic block that belongs to some loop assign the number
5826 of innermost loop it belongs to. */
5827 for (i = 0; i < last_basic_block; i++)
5828 loop_hdr[i] = -1;
5830 FOR_EACH_BB (bb)
5832 if (bb->loop_father && !bb->loop_father->num == 0
5833 && !(bb->flags & BB_IRREDUCIBLE_LOOP))
5834 loop_hdr[bb->index] = bb->loop_father->num;
5837 /* For each basic block degree is calculated as the number of incoming
5838 edges, that are going out of bbs that are not yet scheduled.
5839 The basic blocks that are scheduled have degree value of zero. */
5840 FOR_EACH_BB (bb)
5842 degree[bb->index] = 0;
5844 if (!TEST_BIT (bbs_in_loop_rgns, bb->index))
5846 FOR_EACH_EDGE (e, ei, bb->preds)
5847 if (!TEST_BIT (bbs_in_loop_rgns, e->src->index))
5848 degree[bb->index]++;
5850 else
5851 degree[bb->index] = -1;
5854 extend_rgns (degree, &cur_rgn_blocks, bbs_in_loop_rgns, loop_hdr);
5856 /* Any block that did not end up in a region is placed into a region
5857 by itself. */
5858 FOR_EACH_BB (bb)
5859 if (degree[bb->index] >= 0)
5861 rgn_bb_table[cur_rgn_blocks] = bb->index;
5862 RGN_NR_BLOCKS (nr_regions) = 1;
5863 RGN_BLOCKS (nr_regions) = cur_rgn_blocks++;
5864 RGN_DONT_CALC_DEPS (nr_regions) = 0;
5865 RGN_HAS_REAL_EBB (nr_regions) = 0;
5866 CONTAINING_RGN (bb->index) = nr_regions++;
5867 BLOCK_TO_BB (bb->index) = 0;
5870 free (degree);
5871 free (loop_hdr);
5874 /* Free data structures used in pipelining of loops. */
5875 void sel_finish_pipelining (void)
5877 loop_iterator li;
5878 struct loop *loop;
5880 /* Release aux fields so we don't free them later by mistake. */
5881 FOR_EACH_LOOP (li, loop, 0)
5882 loop->aux = NULL;
5884 loop_optimizer_finalize ();
5886 VEC_free (loop_p, heap, loop_nests);
5888 free (rev_top_order_index);
5889 rev_top_order_index = NULL;
5892 /* This function replaces the find_rgns when
5893 FLAG_SEL_SCHED_PIPELINING_OUTER_LOOPS is set. */
5894 void
5895 sel_find_rgns (void)
5897 sel_init_pipelining ();
5898 extend_regions ();
5900 if (current_loops)
5902 loop_p loop;
5903 loop_iterator li;
5905 FOR_EACH_LOOP (li, loop, (flag_sel_sched_pipelining_outer_loops
5906 ? LI_FROM_INNERMOST
5907 : LI_ONLY_INNERMOST))
5908 make_regions_from_loop_nest (loop);
5911 /* Make regions from all the rest basic blocks and schedule them.
5912 These blocks include blocks that don't belong to any loop or belong
5913 to irreducible loops. */
5914 make_regions_from_the_rest ();
5916 /* We don't need bbs_in_loop_rgns anymore. */
5917 sbitmap_free (bbs_in_loop_rgns);
5918 bbs_in_loop_rgns = NULL;
5921 /* Adds the preheader blocks from previous loop to current region taking
5922 it from LOOP_PREHEADER_BLOCKS (current_loop_nest).
5923 This function is only used with -fsel-sched-pipelining-outer-loops. */
5924 void
5925 sel_add_loop_preheaders (void)
5927 int i;
5928 basic_block bb;
5929 VEC(basic_block, heap) *preheader_blocks
5930 = LOOP_PREHEADER_BLOCKS (current_loop_nest);
5932 for (i = 0;
5933 VEC_iterate (basic_block, preheader_blocks, i, bb);
5934 i++)
5935 sel_add_bb (bb);
5937 VEC_free (basic_block, heap, preheader_blocks);
5940 /* While pipelining outer loops, returns TRUE if BB is a loop preheader.
5941 Please note that the function should also work when pipelining_p is
5942 false, because it is used when deciding whether we should or should
5943 not reschedule pipelined code. */
5944 bool
5945 sel_is_loop_preheader_p (basic_block bb)
5947 if (current_loop_nest)
5949 struct loop *outer;
5951 if (preheader_removed)
5952 return false;
5954 /* Preheader is the first block in the region. */
5955 if (BLOCK_TO_BB (bb->index) == 0)
5956 return true;
5958 /* We used to find a preheader with the topological information.
5959 Check that the above code is equivalent to what we did before. */
5961 if (in_current_region_p (current_loop_nest->header))
5962 gcc_assert (!(BLOCK_TO_BB (bb->index)
5963 < BLOCK_TO_BB (current_loop_nest->header->index)));
5965 /* Support the situation when the latch block of outer loop
5966 could be from here. */
5967 for (outer = loop_outer (current_loop_nest);
5968 outer;
5969 outer = loop_outer (outer))
5970 if (considered_for_pipelining_p (outer) && outer->latch == bb)
5971 gcc_unreachable ();
5974 return false;
5977 /* Checks whether JUMP leads to basic block DEST_BB and no other blocks. */
5978 bool
5979 jump_leads_only_to_bb_p (insn_t jump, basic_block dest_bb)
5981 basic_block jump_bb = BLOCK_FOR_INSN (jump);
5983 /* It is not jump, jump with side-effects or jump can lead to several
5984 basic blocks. */
5985 if (!onlyjump_p (jump)
5986 || !any_uncondjump_p (jump))
5987 return false;
5989 /* Several outgoing edges, abnormal edge or destination of jump is
5990 not DEST_BB. */
5991 if (EDGE_COUNT (jump_bb->succs) != 1
5992 || EDGE_SUCC (jump_bb, 0)->flags & EDGE_ABNORMAL
5993 || EDGE_SUCC (jump_bb, 0)->dest != dest_bb)
5994 return false;
5996 /* If not anything of the upper. */
5997 return true;
6000 /* Removes the loop preheader from the current region and saves it in
6001 PREHEADER_BLOCKS of the father loop, so they will be added later to
6002 region that represents an outer loop. */
6003 static void
6004 sel_remove_loop_preheader (void)
6006 int i, old_len;
6007 int cur_rgn = CONTAINING_RGN (BB_TO_BLOCK (0));
6008 basic_block bb;
6009 bool all_empty_p = true;
6010 VEC(basic_block, heap) *preheader_blocks
6011 = LOOP_PREHEADER_BLOCKS (loop_outer (current_loop_nest));
6013 gcc_assert (current_loop_nest);
6014 old_len = VEC_length (basic_block, preheader_blocks);
6016 /* Add blocks that aren't within the current loop to PREHEADER_BLOCKS. */
6017 for (i = 0; i < RGN_NR_BLOCKS (cur_rgn); i++)
6019 bb = BASIC_BLOCK (BB_TO_BLOCK (i));
6021 /* If the basic block belongs to region, but doesn't belong to
6022 corresponding loop, then it should be a preheader. */
6023 if (sel_is_loop_preheader_p (bb))
6025 VEC_safe_push (basic_block, heap, preheader_blocks, bb);
6026 if (BB_END (bb) != bb_note (bb))
6027 all_empty_p = false;
6031 /* Remove these blocks only after iterating over the whole region. */
6032 for (i = VEC_length (basic_block, preheader_blocks) - 1;
6033 i >= old_len;
6034 i--)
6036 bb = VEC_index (basic_block, preheader_blocks, i);
6037 sel_remove_bb (bb, false);
6040 if (!considered_for_pipelining_p (loop_outer (current_loop_nest)))
6042 if (!all_empty_p)
6043 /* Immediately create new region from preheader. */
6044 make_region_from_loop_preheader (&preheader_blocks);
6045 else
6047 /* If all preheader blocks are empty - dont create new empty region.
6048 Instead, remove them completely. */
6049 for (i = 0; VEC_iterate (basic_block, preheader_blocks, i, bb); i++)
6051 edge e;
6052 edge_iterator ei;
6053 basic_block prev_bb = bb->prev_bb, next_bb = bb->next_bb;
6055 /* Redirect all incoming edges to next basic block. */
6056 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
6058 if (! (e->flags & EDGE_FALLTHRU))
6059 redirect_edge_and_branch (e, bb->next_bb);
6060 else
6061 redirect_edge_succ (e, bb->next_bb);
6063 gcc_assert (BB_NOTE_LIST (bb) == NULL);
6064 delete_and_free_basic_block (bb);
6066 /* Check if after deleting preheader there is a nonconditional
6067 jump in PREV_BB that leads to the next basic block NEXT_BB.
6068 If it is so - delete this jump and clear data sets of its
6069 basic block if it becomes empty. */
6070 if (next_bb->prev_bb == prev_bb
6071 && prev_bb != ENTRY_BLOCK_PTR
6072 && jump_leads_only_to_bb_p (BB_END (prev_bb), next_bb))
6074 redirect_edge_and_branch (EDGE_SUCC (prev_bb, 0), next_bb);
6075 if (BB_END (prev_bb) == bb_note (prev_bb))
6076 free_data_sets (prev_bb);
6080 VEC_free (basic_block, heap, preheader_blocks);
6082 else
6083 /* Store preheader within the father's loop structure. */
6084 SET_LOOP_PREHEADER_BLOCKS (loop_outer (current_loop_nest),
6085 preheader_blocks);
6087 #endif