Merge branch 'vendor/GCC44'
[dragonfly.git] / contrib / gcc-4.4 / gcc / sel-sched-ir.c
CommitLineData
c251ad9e 1/* Instruction scheduling pass. Selective scheduler and pipeliner.
4b1e227d 2 Copyright (C) 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
c251ad9e
SS
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along with GCC; see the file COPYING3. If not see
18<http://www.gnu.org/licenses/>. */
19
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"
46
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"
51
52/* A vector holding bb info for whole scheduling pass. */
53VEC(sel_global_bb_info_def, heap) *sel_global_bb_info = NULL;
54
55/* A vector holding bb info. */
56VEC(sel_region_bb_info_def, heap) *sel_region_bb_info = NULL;
57
58/* A pool for allocating all lists. */
59alloc_pool sched_lists_pool;
60
61/* This contains information about successors for compute_av_set. */
62struct succs_info current_succs;
63
64/* Data structure to describe interaction with the generic scheduler utils. */
65static struct common_sched_info_def sel_common_sched_info;
66
67/* The loop nest being pipelined. */
68struct loop *current_loop_nest;
69
70/* LOOP_NESTS is a vector containing the corresponding loop nest for
71 each region. */
72static VEC(loop_p, heap) *loop_nests = NULL;
73
74/* Saves blocks already in loop regions, indexed by bb->index. */
75static sbitmap bbs_in_loop_rgns = NULL;
76
77/* CFG hooks that are saved before changing create_basic_block hook. */
78static struct cfg_hooks orig_cfg_hooks;
79\f
80
81/* Array containing reverse topological index of function basic blocks,
82 indexed by BB->INDEX. */
83static int *rev_top_order_index = NULL;
84
85/* Length of the above array. */
86static int rev_top_order_index_len = -1;
87
88/* A regset pool structure. */
89static struct
90{
91 /* The stack to which regsets are returned. */
92 regset *v;
93
94 /* Its pointer. */
95 int n;
96
97 /* Its size. */
98 int s;
99
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;
104
105 /* The pointer of VV stack. */
106 int nn;
107
108 /* Its size. */
109 int ss;
110
111 /* The difference between allocated and returned regsets. */
112 int diff;
113} regset_pool = { NULL, 0, 0, NULL, 0, 0, 0 };
114
115/* This represents the nop pool. */
116static struct
117{
118 /* The vector which holds previously emitted nops. */
119 insn_t *v;
120
121 /* Its pointer. */
122 int n;
123
124 /* Its size. */
125 int s;
126} nop_pool = { NULL, 0, 0 };
127
128/* The pool for basic block notes. */
129static rtx_vec_t bb_note_pool;
130
131/* A NOP pattern used to emit placeholder insns. */
132rtx 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. */
135rtx exit_insn = NULL_RTX;
136
137/* TRUE if while scheduling current region, which is loop, its preheader
138 was removed. */
139bool preheader_removed = false;
140\f
141
142/* Forward static declarations. */
143static void fence_clear (fence_t);
144
145static void deps_init_id (idata_t, insn_t, bool);
146static void init_id_from_df (idata_t, insn_t, bool);
147static expr_t set_insn_init (expr_t, vinsn_t, int);
148
149static void cfg_preds (basic_block, insn_t **, int *);
150static void prepare_insn_expr (insn_t, int);
151static void free_history_vect (VEC (expr_history_def, heap) **);
152
153static void move_bb_info (basic_block, basic_block);
154static void remove_empty_bb (basic_block, bool);
155static void sel_remove_loop_preheader (void);
156
157static bool insn_is_the_only_one_in_bb_p (insn_t);
158static void create_initial_data_sets (basic_block);
159
160static void invalidate_av_set (basic_block);
161static void extend_insn_data (void);
162static void sel_init_new_insn (insn_t, int);
163static void finish_insns (void);
164\f
165/* Various list functions. */
166
167/* Copy an instruction list L. */
168ilist_t
169ilist_copy (ilist_t l)
170{
171 ilist_t head = NULL, *tailp = &head;
172
173 while (l)
174 {
175 ilist_add (tailp, ILIST_INSN (l));
176 tailp = &ILIST_NEXT (*tailp);
177 l = ILIST_NEXT (l);
178 }
179
180 return head;
181}
182
183/* Invert an instruction list L. */
184ilist_t
185ilist_invert (ilist_t l)
186{
187 ilist_t res = NULL;
188
189 while (l)
190 {
191 ilist_add (&res, ILIST_INSN (l));
192 l = ILIST_NEXT (l);
193 }
194
195 return res;
196}
197
198/* Add a new boundary to the LP list with parameters TO, PTR, and DC. */
199void
200blist_add (blist_t *lp, insn_t to, ilist_t ptr, deps_t dc)
201{
202 bnd_t bnd;
203
204 _list_add (lp);
205 bnd = BLIST_BND (*lp);
206
207 BND_TO (bnd) = to;
208 BND_PTR (bnd) = ptr;
209 BND_AV (bnd) = NULL;
210 BND_AV1 (bnd) = NULL;
211 BND_DC (bnd) = dc;
212}
213
214/* Remove the list note pointed to by LP. */
215void
216blist_remove (blist_t *lp)
217{
218 bnd_t b = BLIST_BND (*lp);
219
220 av_set_clear (&BND_AV (b));
221 av_set_clear (&BND_AV1 (b));
222 ilist_clear (&BND_PTR (b));
223
224 _list_remove (lp);
225}
226
227/* Init a fence tail L. */
228void
229flist_tail_init (flist_tail_t l)
230{
231 FLIST_TAIL_HEAD (l) = NULL;
232 FLIST_TAIL_TAILP (l) = &FLIST_TAIL_HEAD (l);
233}
234
235/* Try to find fence corresponding to INSN in L. */
236fence_t
237flist_lookup (flist_t l, insn_t insn)
238{
239 while (l)
240 {
241 if (FENCE_INSN (FLIST_FENCE (l)) == insn)
242 return FLIST_FENCE (l);
243
244 l = FLIST_NEXT (l);
245 }
246
247 return NULL;
248}
249
250/* Init the fields of F before running fill_insns. */
251static void
252init_fence_for_scheduling (fence_t f)
253{
254 FENCE_BNDS (f) = NULL;
255 FENCE_PROCESSED_P (f) = false;
256 FENCE_SCHEDULED_P (f) = false;
257}
258
259/* Add new fence consisting of INSN and STATE to the list pointed to by LP. */
260static void
4b1e227d
SW
261flist_add (flist_t *lp, insn_t insn, state_t state, deps_t dc, void *tc,
262 insn_t last_scheduled_insn, VEC(rtx,gc) *executing_insns,
263 int *ready_ticks, int ready_ticks_size, insn_t sched_next,
264 int cycle, int cycle_issued_insns, int issue_more,
c251ad9e
SS
265 bool starts_cycle_p, bool after_stall_p)
266{
267 fence_t f;
268
269 _list_add (lp);
270 f = FLIST_FENCE (*lp);
271
272 FENCE_INSN (f) = insn;
273
274 gcc_assert (state != NULL);
275 FENCE_STATE (f) = state;
276
277 FENCE_CYCLE (f) = cycle;
278 FENCE_ISSUED_INSNS (f) = cycle_issued_insns;
279 FENCE_STARTS_CYCLE_P (f) = starts_cycle_p;
280 FENCE_AFTER_STALL_P (f) = after_stall_p;
281
282 gcc_assert (dc != NULL);
283 FENCE_DC (f) = dc;
284
285 gcc_assert (tc != NULL || targetm.sched.alloc_sched_context == NULL);
286 FENCE_TC (f) = tc;
287
288 FENCE_LAST_SCHEDULED_INSN (f) = last_scheduled_insn;
4b1e227d 289 FENCE_ISSUE_MORE (f) = issue_more;
c251ad9e
SS
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;
294
295 init_fence_for_scheduling (f);
296}
297
298/* Remove the head node of the list pointed to by LP. */
299static void
300flist_remove (flist_t *lp)
301{
302 if (FENCE_INSN (FLIST_FENCE (*lp)))
303 fence_clear (FLIST_FENCE (*lp));
304 _list_remove (lp);
305}
306
307/* Clear the fence list pointed to by LP. */
308void
309flist_clear (flist_t *lp)
310{
311 while (*lp)
312 flist_remove (lp);
313}
314
315/* Add ORIGINAL_INSN the def list DL honoring CROSSES_CALL. */
316void
317def_list_add (def_list_t *dl, insn_t original_insn, bool crosses_call)
318{
319 def_t d;
320
321 _list_add (dl);
322 d = DEF_LIST_DEF (*dl);
323
324 d->orig_insn = original_insn;
325 d->crosses_call = crosses_call;
326}
327\f
328
329/* Functions to work with target contexts. */
330
331/* Bulk target context. It is convenient for debugging purposes to ensure
332 that there are no uninitialized (null) target contexts. */
333static tc_t bulk_tc = (tc_t) 1;
334
335/* Target hooks wrappers. In the future we can provide some default
336 implementations for them. */
337
338/* Allocate a store for the target context. */
339static tc_t
340alloc_target_context (void)
341{
342 return (targetm.sched.alloc_sched_context
343 ? targetm.sched.alloc_sched_context () : bulk_tc);
344}
345
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. */
349static void
350init_target_context (tc_t tc, bool clean_p)
351{
352 if (targetm.sched.init_sched_context)
353 targetm.sched.init_sched_context (tc, clean_p);
354}
355
356/* Allocate and initialize a target context. Meaning of CLEAN_P is the same as
357 int init_target_context (). */
358tc_t
359create_target_context (bool clean_p)
360{
361 tc_t tc = alloc_target_context ();
362
363 init_target_context (tc, clean_p);
364 return tc;
365}
366
367/* Copy TC to the current backend context. */
368void
369set_target_context (tc_t tc)
370{
371 if (targetm.sched.set_sched_context)
372 targetm.sched.set_sched_context (tc);
373}
374
375/* TC is about to be destroyed. Free any internal data. */
376static void
377clear_target_context (tc_t tc)
378{
379 if (targetm.sched.clear_sched_context)
380 targetm.sched.clear_sched_context (tc);
381}
382
383/* Clear and free it. */
384static void
385delete_target_context (tc_t tc)
386{
387 clear_target_context (tc);
388
389 if (targetm.sched.free_sched_context)
390 targetm.sched.free_sched_context (tc);
391}
392
393/* Make a copy of FROM in TO.
394 NB: May be this should be a hook. */
395static void
396copy_target_context (tc_t to, tc_t from)
397{
398 tc_t tmp = create_target_context (false);
399
400 set_target_context (from);
401 init_target_context (to, false);
402
403 set_target_context (tmp);
404 delete_target_context (tmp);
405}
406
407/* Create a copy of TC. */
408static tc_t
409create_copy_of_target_context (tc_t tc)
410{
411 tc_t copy = alloc_target_context ();
412
413 copy_target_context (copy, tc);
414
415 return copy;
416}
417
418/* Clear TC and initialize it according to CLEAN_P. The meaning of CLEAN_P
419 is the same as in init_target_context (). */
420void
421reset_target_context (tc_t tc, bool clean_p)
422{
423 clear_target_context (tc);
424 init_target_context (tc, clean_p);
425}
426\f
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. */
431
432/* Make a copy of FROM in TO. */
433static void
434copy_deps_context (deps_t to, deps_t from)
435{
4b1e227d 436 init_deps (to, false);
c251ad9e
SS
437 deps_join (to, from);
438}
439
440/* Allocate store for dep context. */
441static deps_t
442alloc_deps_context (void)
443{
444 return XNEW (struct deps);
445}
446
447/* Allocate and initialize dep context. */
448static deps_t
449create_deps_context (void)
450{
451 deps_t dc = alloc_deps_context ();
452
4b1e227d 453 init_deps (dc, false);
c251ad9e
SS
454 return dc;
455}
456
457/* Create a copy of FROM. */
458static deps_t
459create_copy_of_deps_context (deps_t from)
460{
461 deps_t to = alloc_deps_context ();
462
463 copy_deps_context (to, from);
464 return to;
465}
466
467/* Clean up internal data of DC. */
468static void
469clear_deps_context (deps_t dc)
470{
471 free_deps (dc);
472}
473
474/* Clear and free DC. */
475static void
476delete_deps_context (deps_t dc)
477{
478 clear_deps_context (dc);
479 free (dc);
480}
481
482/* Clear and init DC. */
483static void
484reset_deps_context (deps_t dc)
485{
486 clear_deps_context (dc);
4b1e227d 487 init_deps (dc, false);
c251ad9e
SS
488}
489
490/* This structure describes the dependence analysis hooks for advancing
491 dependence context. */
492static struct sched_deps_info_def advance_deps_context_sched_deps_info =
493 {
494 NULL,
495
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 */
507
508 0, 0, 0
509 };
510
511/* Process INSN and add its impact on DC. */
512void
513advance_deps_context (deps_t dc, insn_t insn)
514{
515 sched_deps_info = &advance_deps_context_sched_deps_info;
516 deps_analyze_insn (dc, insn);
517}
518\f
519
520/* Functions to work with DFA states. */
521
522/* Allocate store for a DFA state. */
523static state_t
524state_alloc (void)
525{
526 return xmalloc (dfa_state_size);
527}
528
529/* Allocate and initialize DFA state. */
530static state_t
531state_create (void)
532{
533 state_t state = state_alloc ();
534
535 state_reset (state);
536 advance_state (state);
537 return state;
538}
539
540/* Free DFA state. */
541static void
542state_free (state_t state)
543{
544 free (state);
545}
546
547/* Make a copy of FROM in TO. */
548static void
549state_copy (state_t to, state_t from)
550{
551 memcpy (to, from, dfa_state_size);
552}
553
554/* Create a copy of FROM. */
555static state_t
556state_create_copy (state_t from)
557{
558 state_t to = state_alloc ();
559
560 state_copy (to, from);
561 return to;
562}
563\f
564
565/* Functions to work with fences. */
566
567/* Clear the fence. */
568static void
569fence_clear (fence_t f)
570{
571 state_t s = FENCE_STATE (f);
572 deps_t dc = FENCE_DC (f);
573 void *tc = FENCE_TC (f);
574
575 ilist_clear (&FENCE_BNDS (f));
576
577 gcc_assert ((s != NULL && dc != NULL && tc != NULL)
578 || (s == NULL && dc == NULL && tc == NULL));
579
580 if (s != NULL)
581 free (s);
582
583 if (dc != NULL)
584 delete_deps_context (dc);
585
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;
591}
592
593/* Init a list of fences with successors of OLD_FENCE. */
594void
595init_fences (insn_t old_fence)
596{
597 insn_t succ;
598 succ_iterator si;
599 bool first = true;
600 int ready_ticks_size = get_max_uid () + 1;
601
602 FOR_EACH_SUCC_1 (succ, si, old_fence,
603 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
604 {
605
606 if (first)
607 first = false;
608 else
609 gcc_assert (flag_sel_sched_pipelining_outer_loops);
610
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 */,
4b1e227d
SW
620 1 /* cycle */, 0 /* cycle_issued_insns */,
621 issue_rate, /* issue_more */
622 1 /* starts_cycle_p */, 0 /* after_stall_p */);
c251ad9e
SS
623 }
624}
625
626/* Merges two fences (filling fields of fence F with resulting values) by
627 following rules: 1) state, target context and last scheduled insn are
628 propagated from fallthrough edge if it is available;
629 2) deps context and cycle is propagated from more probable edge;
630 3) all other fields are set to corresponding constant values.
631
4b1e227d
SW
632 INSN, STATE, DC, TC, LAST_SCHEDULED_INSN, EXECUTING_INSNS,
633 READY_TICKS, READY_TICKS_SIZE, SCHED_NEXT, CYCLE, ISSUE_MORE
634 and AFTER_STALL_P are the corresponding fields of the second fence. */
c251ad9e
SS
635static void
636merge_fences (fence_t f, insn_t insn,
637 state_t state, deps_t dc, void *tc,
638 rtx last_scheduled_insn, VEC(rtx, gc) *executing_insns,
639 int *ready_ticks, int ready_ticks_size,
4b1e227d 640 rtx sched_next, int cycle, int issue_more, bool after_stall_p)
c251ad9e
SS
641{
642 insn_t last_scheduled_insn_old = FENCE_LAST_SCHEDULED_INSN (f);
643
644 gcc_assert (sel_bb_head_p (FENCE_INSN (f))
645 && !sched_next && !FENCE_SCHED_NEXT (f));
646
647 /* Check if we can decide which path fences came.
648 If we can't (or don't want to) - reset all. */
649 if (last_scheduled_insn == NULL
650 || last_scheduled_insn_old == NULL
651 /* This is a case when INSN is reachable on several paths from
652 one insn (this can happen when pipelining of outer loops is on and
653 there are two edges: one going around of inner loop and the other -
654 right through it; in such case just reset everything). */
655 || last_scheduled_insn == last_scheduled_insn_old)
656 {
657 state_reset (FENCE_STATE (f));
658 state_free (state);
659
660 reset_deps_context (FENCE_DC (f));
661 delete_deps_context (dc);
662
663 reset_target_context (FENCE_TC (f), true);
664 delete_target_context (tc);
665
666 if (cycle > FENCE_CYCLE (f))
667 FENCE_CYCLE (f) = cycle;
668
669 FENCE_LAST_SCHEDULED_INSN (f) = NULL;
4b1e227d 670 FENCE_ISSUE_MORE (f) = issue_rate;
c251ad9e
SS
671 VEC_free (rtx, gc, executing_insns);
672 free (ready_ticks);
673 if (FENCE_EXECUTING_INSNS (f))
674 VEC_block_remove (rtx, FENCE_EXECUTING_INSNS (f), 0,
675 VEC_length (rtx, FENCE_EXECUTING_INSNS (f)));
676 if (FENCE_READY_TICKS (f))
677 memset (FENCE_READY_TICKS (f), 0, FENCE_READY_TICKS_SIZE (f));
678 }
679 else
680 {
681 edge edge_old = NULL, edge_new = NULL;
682 edge candidate;
683 succ_iterator si;
684 insn_t succ;
685
686 /* Find fallthrough edge. */
687 gcc_assert (BLOCK_FOR_INSN (insn)->prev_bb);
688 candidate = find_fallthru_edge (BLOCK_FOR_INSN (insn)->prev_bb);
689
690 if (!candidate
691 || (candidate->src != BLOCK_FOR_INSN (last_scheduled_insn)
692 && candidate->src != BLOCK_FOR_INSN (last_scheduled_insn_old)))
693 {
694 /* No fallthrough edge leading to basic block of INSN. */
695 state_reset (FENCE_STATE (f));
696 state_free (state);
697
698 reset_target_context (FENCE_TC (f), true);
699 delete_target_context (tc);
700
701 FENCE_LAST_SCHEDULED_INSN (f) = NULL;
4b1e227d 702 FENCE_ISSUE_MORE (f) = issue_rate;
c251ad9e
SS
703 }
704 else
705 if (candidate->src == BLOCK_FOR_INSN (last_scheduled_insn))
706 {
707 /* Would be weird if same insn is successor of several fallthrough
708 edges. */
709 gcc_assert (BLOCK_FOR_INSN (insn)->prev_bb
710 != BLOCK_FOR_INSN (last_scheduled_insn_old));
711
712 state_free (FENCE_STATE (f));
713 FENCE_STATE (f) = state;
714
715 delete_target_context (FENCE_TC (f));
716 FENCE_TC (f) = tc;
717
718 FENCE_LAST_SCHEDULED_INSN (f) = last_scheduled_insn;
4b1e227d 719 FENCE_ISSUE_MORE (f) = issue_more;
c251ad9e
SS
720 }
721 else
722 {
723 /* Leave STATE, TC and LAST_SCHEDULED_INSN fields untouched. */
724 state_free (state);
725 delete_target_context (tc);
726
727 gcc_assert (BLOCK_FOR_INSN (insn)->prev_bb
728 != BLOCK_FOR_INSN (last_scheduled_insn));
729 }
730
731 /* Find edge of first predecessor (last_scheduled_insn_old->insn). */
732 FOR_EACH_SUCC_1 (succ, si, last_scheduled_insn_old,
733 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
734 {
735 if (succ == insn)
736 {
737 /* No same successor allowed from several edges. */
738 gcc_assert (!edge_old);
739 edge_old = si.e1;
740 }
741 }
742 /* Find edge of second predecessor (last_scheduled_insn->insn). */
743 FOR_EACH_SUCC_1 (succ, si, last_scheduled_insn,
744 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
745 {
746 if (succ == insn)
747 {
748 /* No same successor allowed from several edges. */
749 gcc_assert (!edge_new);
750 edge_new = si.e1;
751 }
752 }
753
754 /* Check if we can choose most probable predecessor. */
755 if (edge_old == NULL || edge_new == NULL)
756 {
757 reset_deps_context (FENCE_DC (f));
758 delete_deps_context (dc);
759 VEC_free (rtx, gc, executing_insns);
760 free (ready_ticks);
761
762 FENCE_CYCLE (f) = MAX (FENCE_CYCLE (f), cycle);
763 if (FENCE_EXECUTING_INSNS (f))
764 VEC_block_remove (rtx, FENCE_EXECUTING_INSNS (f), 0,
765 VEC_length (rtx, FENCE_EXECUTING_INSNS (f)));
766 if (FENCE_READY_TICKS (f))
767 memset (FENCE_READY_TICKS (f), 0, FENCE_READY_TICKS_SIZE (f));
768 }
769 else
770 if (edge_new->probability > edge_old->probability)
771 {
772 delete_deps_context (FENCE_DC (f));
773 FENCE_DC (f) = dc;
774 VEC_free (rtx, gc, FENCE_EXECUTING_INSNS (f));
775 FENCE_EXECUTING_INSNS (f) = executing_insns;
776 free (FENCE_READY_TICKS (f));
777 FENCE_READY_TICKS (f) = ready_ticks;
778 FENCE_READY_TICKS_SIZE (f) = ready_ticks_size;
779 FENCE_CYCLE (f) = cycle;
780 }
781 else
782 {
783 /* Leave DC and CYCLE untouched. */
784 delete_deps_context (dc);
785 VEC_free (rtx, gc, executing_insns);
786 free (ready_ticks);
787 }
788 }
789
790 /* Fill remaining invariant fields. */
791 if (after_stall_p)
792 FENCE_AFTER_STALL_P (f) = 1;
793
794 FENCE_ISSUED_INSNS (f) = 0;
795 FENCE_STARTS_CYCLE_P (f) = 1;
796 FENCE_SCHED_NEXT (f) = NULL;
797}
798
799/* Add a new fence to NEW_FENCES list, initializing it from all
800 other parameters. */
801static void
802add_to_fences (flist_tail_t new_fences, insn_t insn,
4b1e227d
SW
803 state_t state, deps_t dc, void *tc, rtx last_scheduled_insn,
804 VEC(rtx, gc) *executing_insns, int *ready_ticks,
805 int ready_ticks_size, rtx sched_next, int cycle,
806 int cycle_issued_insns, int issue_rate,
807 bool starts_cycle_p, bool after_stall_p)
c251ad9e
SS
808{
809 fence_t f = flist_lookup (FLIST_TAIL_HEAD (new_fences), insn);
810
811 if (! f)
812 {
813 flist_add (FLIST_TAIL_TAILP (new_fences), insn, state, dc, tc,
814 last_scheduled_insn, executing_insns, ready_ticks,
815 ready_ticks_size, sched_next, cycle, cycle_issued_insns,
4b1e227d 816 issue_rate, starts_cycle_p, after_stall_p);
c251ad9e
SS
817
818 FLIST_TAIL_TAILP (new_fences)
819 = &FLIST_NEXT (*FLIST_TAIL_TAILP (new_fences));
820 }
821 else
822 {
4b1e227d
SW
823 merge_fences (f, insn, state, dc, tc, last_scheduled_insn,
824 executing_insns, ready_ticks, ready_ticks_size,
825 sched_next, cycle, issue_rate, after_stall_p);
c251ad9e
SS
826 }
827}
828
829/* Move the first fence in the OLD_FENCES list to NEW_FENCES. */
830void
831move_fence_to_fences (flist_t old_fences, flist_tail_t new_fences)
832{
833 fence_t f, old;
834 flist_t *tailp = FLIST_TAIL_TAILP (new_fences);
835
836 old = FLIST_FENCE (old_fences);
837 f = flist_lookup (FLIST_TAIL_HEAD (new_fences),
838 FENCE_INSN (FLIST_FENCE (old_fences)));
839 if (f)
840 {
841 merge_fences (f, old->insn, old->state, old->dc, old->tc,
842 old->last_scheduled_insn, old->executing_insns,
843 old->ready_ticks, old->ready_ticks_size,
4b1e227d 844 old->sched_next, old->cycle, old->issue_more,
c251ad9e
SS
845 old->after_stall_p);
846 }
847 else
848 {
849 _list_add (tailp);
850 FLIST_TAIL_TAILP (new_fences) = &FLIST_NEXT (*tailp);
851 *FLIST_FENCE (*tailp) = *old;
852 init_fence_for_scheduling (FLIST_FENCE (*tailp));
853 }
854 FENCE_INSN (old) = NULL;
855}
856
857/* Add a new fence to NEW_FENCES list and initialize most of its data
858 as a clean one. */
859void
860add_clean_fence_to_fences (flist_tail_t new_fences, insn_t succ, fence_t fence)
861{
862 int ready_ticks_size = get_max_uid () + 1;
863
864 add_to_fences (new_fences,
865 succ, state_create (), create_deps_context (),
866 create_target_context (true),
867 NULL_RTX, NULL,
868 XCNEWVEC (int, ready_ticks_size), ready_ticks_size,
869 NULL_RTX, FENCE_CYCLE (fence) + 1,
4b1e227d 870 0, issue_rate, 1, FENCE_AFTER_STALL_P (fence));
c251ad9e
SS
871}
872
873/* Add a new fence to NEW_FENCES list and initialize all of its data
874 from FENCE and SUCC. */
875void
876add_dirty_fence_to_fences (flist_tail_t new_fences, insn_t succ, fence_t fence)
877{
878 int * new_ready_ticks
879 = XNEWVEC (int, FENCE_READY_TICKS_SIZE (fence));
880
881 memcpy (new_ready_ticks, FENCE_READY_TICKS (fence),
882 FENCE_READY_TICKS_SIZE (fence) * sizeof (int));
883 add_to_fences (new_fences,
884 succ, state_create_copy (FENCE_STATE (fence)),
885 create_copy_of_deps_context (FENCE_DC (fence)),
886 create_copy_of_target_context (FENCE_TC (fence)),
887 FENCE_LAST_SCHEDULED_INSN (fence),
888 VEC_copy (rtx, gc, FENCE_EXECUTING_INSNS (fence)),
889 new_ready_ticks,
890 FENCE_READY_TICKS_SIZE (fence),
891 FENCE_SCHED_NEXT (fence),
892 FENCE_CYCLE (fence),
893 FENCE_ISSUED_INSNS (fence),
4b1e227d 894 FENCE_ISSUE_MORE (fence),
c251ad9e
SS
895 FENCE_STARTS_CYCLE_P (fence),
896 FENCE_AFTER_STALL_P (fence));
897}
898\f
899
900/* Functions to work with regset and nop pools. */
901
902/* Returns the new regset from pool. It might have some of the bits set
903 from the previous usage. */
904regset
905get_regset_from_pool (void)
906{
907 regset rs;
908
909 if (regset_pool.n != 0)
910 rs = regset_pool.v[--regset_pool.n];
911 else
912 /* We need to create the regset. */
913 {
914 rs = ALLOC_REG_SET (&reg_obstack);
915
916 if (regset_pool.nn == regset_pool.ss)
917 regset_pool.vv = XRESIZEVEC (regset, regset_pool.vv,
918 (regset_pool.ss = 2 * regset_pool.ss + 1));
919 regset_pool.vv[regset_pool.nn++] = rs;
920 }
921
922 regset_pool.diff++;
923
924 return rs;
925}
926
927/* Same as above, but returns the empty regset. */
928regset
929get_clear_regset_from_pool (void)
930{
931 regset rs = get_regset_from_pool ();
932
933 CLEAR_REG_SET (rs);
934 return rs;
935}
936
937/* Return regset RS to the pool for future use. */
938void
939return_regset_to_pool (regset rs)
940{
941 regset_pool.diff--;
942
943 if (regset_pool.n == regset_pool.s)
944 regset_pool.v = XRESIZEVEC (regset, regset_pool.v,
945 (regset_pool.s = 2 * regset_pool.s + 1));
946 regset_pool.v[regset_pool.n++] = rs;
947}
948
949#ifdef ENABLE_CHECKING
950/* This is used as a qsort callback for sorting regset pool stacks.
951 X and XX are addresses of two regsets. They are never equal. */
952static int
953cmp_v_in_regset_pool (const void *x, const void *xx)
954{
955 return *((const regset *) x) - *((const regset *) xx);
956}
957#endif
958
959/* Free the regset pool possibly checking for memory leaks. */
960void
961free_regset_pool (void)
962{
963#ifdef ENABLE_CHECKING
964 {
965 regset *v = regset_pool.v;
966 int i = 0;
967 int n = regset_pool.n;
968
969 regset *vv = regset_pool.vv;
970 int ii = 0;
971 int nn = regset_pool.nn;
972
973 int diff = 0;
974
975 gcc_assert (n <= nn);
976
977 /* Sort both vectors so it will be possible to compare them. */
978 qsort (v, n, sizeof (*v), cmp_v_in_regset_pool);
979 qsort (vv, nn, sizeof (*vv), cmp_v_in_regset_pool);
980
981 while (ii < nn)
982 {
983 if (v[i] == vv[ii])
984 i++;
985 else
986 /* VV[II] was lost. */
987 diff++;
988
989 ii++;
990 }
991
992 gcc_assert (diff == regset_pool.diff);
993 }
994#endif
995
996 /* If not true - we have a memory leak. */
997 gcc_assert (regset_pool.diff == 0);
998
999 while (regset_pool.n)
1000 {
1001 --regset_pool.n;
1002 FREE_REG_SET (regset_pool.v[regset_pool.n]);
1003 }
1004
1005 free (regset_pool.v);
1006 regset_pool.v = NULL;
1007 regset_pool.s = 0;
1008
1009 free (regset_pool.vv);
1010 regset_pool.vv = NULL;
1011 regset_pool.nn = 0;
1012 regset_pool.ss = 0;
1013
1014 regset_pool.diff = 0;
1015}
1016\f
1017
1018/* Functions to work with nop pools. NOP insns are used as temporary
1019 placeholders of the insns being scheduled to allow correct update of
1020 the data sets. When update is finished, NOPs are deleted. */
1021
1022/* A vinsn that is used to represent a nop. This vinsn is shared among all
1023 nops sel-sched generates. */
1024static vinsn_t nop_vinsn = NULL;
1025
1026/* Emit a nop before INSN, taking it from pool. */
1027insn_t
1028get_nop_from_pool (insn_t insn)
1029{
1030 insn_t nop;
1031 bool old_p = nop_pool.n != 0;
1032 int flags;
1033
1034 if (old_p)
1035 nop = nop_pool.v[--nop_pool.n];
1036 else
1037 nop = nop_pattern;
1038
1039 nop = emit_insn_before (nop, insn);
1040
1041 if (old_p)
1042 flags = INSN_INIT_TODO_SSID;
1043 else
1044 flags = INSN_INIT_TODO_LUID | INSN_INIT_TODO_SSID;
1045
1046 set_insn_init (INSN_EXPR (insn), nop_vinsn, INSN_SEQNO (insn));
1047 sel_init_new_insn (nop, flags);
1048
1049 return nop;
1050}
1051
1052/* Remove NOP from the instruction stream and return it to the pool. */
1053void
1054return_nop_to_pool (insn_t nop)
1055{
1056 gcc_assert (INSN_IN_STREAM_P (nop));
1057 sel_remove_insn (nop, false, true);
1058
1059 if (nop_pool.n == nop_pool.s)
1060 nop_pool.v = XRESIZEVEC (rtx, nop_pool.v,
1061 (nop_pool.s = 2 * nop_pool.s + 1));
1062 nop_pool.v[nop_pool.n++] = nop;
1063}
1064
1065/* Free the nop pool. */
1066void
1067free_nop_pool (void)
1068{
1069 nop_pool.n = 0;
1070 nop_pool.s = 0;
1071 free (nop_pool.v);
1072 nop_pool.v = NULL;
1073}
1074\f
1075
1076/* Skip unspec to support ia64 speculation. Called from rtx_equal_p_cb.
1077 The callback is given two rtxes XX and YY and writes the new rtxes
1078 to NX and NY in case some needs to be skipped. */
1079static int
1080skip_unspecs_callback (const_rtx *xx, const_rtx *yy, rtx *nx, rtx* ny)
1081{
1082 const_rtx x = *xx;
1083 const_rtx y = *yy;
1084
1085 if (GET_CODE (x) == UNSPEC
1086 && (targetm.sched.skip_rtx_p == NULL
1087 || targetm.sched.skip_rtx_p (x)))
1088 {
1089 *nx = XVECEXP (x, 0, 0);
1090 *ny = CONST_CAST_RTX (y);
1091 return 1;
1092 }
1093
1094 if (GET_CODE (y) == UNSPEC
1095 && (targetm.sched.skip_rtx_p == NULL
1096 || targetm.sched.skip_rtx_p (y)))
1097 {
1098 *nx = CONST_CAST_RTX (x);
1099 *ny = XVECEXP (y, 0, 0);
1100 return 1;
1101 }
1102
1103 return 0;
1104}
1105
1106/* Callback, called from hash_rtx_cb. Helps to hash UNSPEC rtx X in a correct way
1107 to support ia64 speculation. When changes are needed, new rtx X and new mode
1108 NMODE are written, and the callback returns true. */
1109static int
1110hash_with_unspec_callback (const_rtx x, enum machine_mode mode ATTRIBUTE_UNUSED,
1111 rtx *nx, enum machine_mode* nmode)
1112{
1113 if (GET_CODE (x) == UNSPEC
1114 && targetm.sched.skip_rtx_p
1115 && targetm.sched.skip_rtx_p (x))
1116 {
1117 *nx = XVECEXP (x, 0 ,0);
1118 *nmode = 0;
1119 return 1;
1120 }
1121
1122 return 0;
1123}
1124
1125/* Returns LHS and RHS are ok to be scheduled separately. */
1126static bool
1127lhs_and_rhs_separable_p (rtx lhs, rtx rhs)
1128{
1129 if (lhs == NULL || rhs == NULL)
1130 return false;
1131
1132 /* Do not schedule CONST, CONST_INT and CONST_DOUBLE etc as rhs: no point
1133 to use reg, if const can be used. Moreover, scheduling const as rhs may
1134 lead to mode mismatch cause consts don't have modes but they could be
1135 merged from branches where the same const used in different modes. */
1136 if (CONSTANT_P (rhs))
1137 return false;
1138
1139 /* ??? Do not rename predicate registers to avoid ICEs in bundling. */
1140 if (COMPARISON_P (rhs))
1141 return false;
1142
1143 /* Do not allow single REG to be an rhs. */
1144 if (REG_P (rhs))
1145 return false;
1146
1147 /* See comment at find_used_regs_1 (*1) for explanation of this
1148 restriction. */
1149 /* FIXME: remove this later. */
1150 if (MEM_P (lhs))
1151 return false;
1152
1153 /* This will filter all tricky things like ZERO_EXTRACT etc.
1154 For now we don't handle it. */
1155 if (!REG_P (lhs) && !MEM_P (lhs))
1156 return false;
1157
1158 return true;
1159}
1160
1161/* Initialize vinsn VI for INSN. Only for use from vinsn_create (). When
1162 FORCE_UNIQUE_P is true, the resulting vinsn will not be clonable. This is
1163 used e.g. for insns from recovery blocks. */
1164static void
1165vinsn_init (vinsn_t vi, insn_t insn, bool force_unique_p)
1166{
1167 hash_rtx_callback_function hrcf;
1168 int insn_class;
1169
1170 VINSN_INSN_RTX (vi) = insn;
1171 VINSN_COUNT (vi) = 0;
1172 vi->cost = -1;
1173
1174 if (DF_INSN_UID_SAFE_GET (INSN_UID (insn)) != NULL)
1175 init_id_from_df (VINSN_ID (vi), insn, force_unique_p);
1176 else
1177 deps_init_id (VINSN_ID (vi), insn, force_unique_p);
1178
1179 /* Hash vinsn depending on whether it is separable or not. */
1180 hrcf = targetm.sched.skip_rtx_p ? hash_with_unspec_callback : NULL;
1181 if (VINSN_SEPARABLE_P (vi))
1182 {
1183 rtx rhs = VINSN_RHS (vi);
1184
1185 VINSN_HASH (vi) = hash_rtx_cb (rhs, GET_MODE (rhs),
1186 NULL, NULL, false, hrcf);
1187 VINSN_HASH_RTX (vi) = hash_rtx_cb (VINSN_PATTERN (vi),
1188 VOIDmode, NULL, NULL,
1189 false, hrcf);
1190 }
1191 else
1192 {
1193 VINSN_HASH (vi) = hash_rtx_cb (VINSN_PATTERN (vi), VOIDmode,
1194 NULL, NULL, false, hrcf);
1195 VINSN_HASH_RTX (vi) = VINSN_HASH (vi);
1196 }
1197
1198 insn_class = haifa_classify_insn (insn);
1199 if (insn_class >= 2
1200 && (!targetm.sched.get_insn_spec_ds
1201 || ((targetm.sched.get_insn_spec_ds (insn) & BEGIN_CONTROL)
1202 == 0)))
1203 VINSN_MAY_TRAP_P (vi) = true;
1204 else
1205 VINSN_MAY_TRAP_P (vi) = false;
1206}
1207
1208/* Indicate that VI has become the part of an rtx object. */
1209void
1210vinsn_attach (vinsn_t vi)
1211{
1212 /* Assert that VI is not pending for deletion. */
1213 gcc_assert (VINSN_INSN_RTX (vi));
1214
1215 VINSN_COUNT (vi)++;
1216}
1217
1218/* Create and init VI from the INSN. Use UNIQUE_P for determining the correct
1219 VINSN_TYPE (VI). */
1220static vinsn_t
1221vinsn_create (insn_t insn, bool force_unique_p)
1222{
1223 vinsn_t vi = XCNEW (struct vinsn_def);
1224
1225 vinsn_init (vi, insn, force_unique_p);
1226 return vi;
1227}
1228
1229/* Return a copy of VI. When REATTACH_P is true, detach VI and attach
1230 the copy. */
1231vinsn_t
1232vinsn_copy (vinsn_t vi, bool reattach_p)
1233{
1234 rtx copy;
1235 bool unique = VINSN_UNIQUE_P (vi);
1236 vinsn_t new_vi;
1237
1238 copy = create_copy_of_insn_rtx (VINSN_INSN_RTX (vi));
1239 new_vi = create_vinsn_from_insn_rtx (copy, unique);
1240 if (reattach_p)
1241 {
1242 vinsn_detach (vi);
1243 vinsn_attach (new_vi);
1244 }
1245
1246 return new_vi;
1247}
1248
1249/* Delete the VI vinsn and free its data. */
1250static void
1251vinsn_delete (vinsn_t vi)
1252{
1253 gcc_assert (VINSN_COUNT (vi) == 0);
1254
1255 return_regset_to_pool (VINSN_REG_SETS (vi));
1256 return_regset_to_pool (VINSN_REG_USES (vi));
1257 return_regset_to_pool (VINSN_REG_CLOBBERS (vi));
1258
1259 free (vi);
1260}
1261
1262/* Indicate that VI is no longer a part of some rtx object.
1263 Remove VI if it is no longer needed. */
1264void
1265vinsn_detach (vinsn_t vi)
1266{
1267 gcc_assert (VINSN_COUNT (vi) > 0);
1268
1269 if (--VINSN_COUNT (vi) == 0)
1270 vinsn_delete (vi);
1271}
1272
1273/* Returns TRUE if VI is a branch. */
1274bool
1275vinsn_cond_branch_p (vinsn_t vi)
1276{
1277 insn_t insn;
1278
1279 if (!VINSN_UNIQUE_P (vi))
1280 return false;
1281
1282 insn = VINSN_INSN_RTX (vi);
1283 if (BB_END (BLOCK_FOR_INSN (insn)) != insn)
1284 return false;
1285
1286 return control_flow_insn_p (insn);
1287}
1288
1289/* Return latency of INSN. */
1290static int
1291sel_insn_rtx_cost (rtx insn)
1292{
1293 int cost;
1294
1295 /* A USE insn, or something else we don't need to
1296 understand. We can't pass these directly to
1297 result_ready_cost or insn_default_latency because it will
1298 trigger a fatal error for unrecognizable insns. */
1299 if (recog_memoized (insn) < 0)
1300 cost = 0;
1301 else
1302 {
1303 cost = insn_default_latency (insn);
1304
1305 if (cost < 0)
1306 cost = 0;
1307 }
1308
1309 return cost;
1310}
1311
1312/* Return the cost of the VI.
1313 !!! FIXME: Unify with haifa-sched.c: insn_cost (). */
1314int
1315sel_vinsn_cost (vinsn_t vi)
1316{
1317 int cost = vi->cost;
1318
1319 if (cost < 0)
1320 {
1321 cost = sel_insn_rtx_cost (VINSN_INSN_RTX (vi));
1322 vi->cost = cost;
1323 }
1324
1325 return cost;
1326}
1327\f
1328
1329/* Functions for insn emitting. */
1330
1331/* Emit new insn after AFTER based on PATTERN and initialize its data from
1332 EXPR and SEQNO. */
1333insn_t
1334sel_gen_insn_from_rtx_after (rtx pattern, expr_t expr, int seqno, insn_t after)
1335{
1336 insn_t new_insn;
1337
1338 gcc_assert (EXPR_TARGET_AVAILABLE (expr) == true);
1339
1340 new_insn = emit_insn_after (pattern, after);
1341 set_insn_init (expr, NULL, seqno);
1342 sel_init_new_insn (new_insn, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SSID);
1343
1344 return new_insn;
1345}
1346
1347/* Force newly generated vinsns to be unique. */
1348static bool init_insn_force_unique_p = false;
1349
1350/* Emit new speculation recovery insn after AFTER based on PATTERN and
1351 initialize its data from EXPR and SEQNO. */
1352insn_t
1353sel_gen_recovery_insn_from_rtx_after (rtx pattern, expr_t expr, int seqno,
1354 insn_t after)
1355{
1356 insn_t insn;
1357
1358 gcc_assert (!init_insn_force_unique_p);
1359
1360 init_insn_force_unique_p = true;
1361 insn = sel_gen_insn_from_rtx_after (pattern, expr, seqno, after);
1362 CANT_MOVE (insn) = 1;
1363 init_insn_force_unique_p = false;
1364
1365 return insn;
1366}
1367
1368/* Emit new insn after AFTER based on EXPR and SEQNO. If VINSN is not NULL,
1369 take it as a new vinsn instead of EXPR's vinsn.
1370 We simplify insns later, after scheduling region in
1371 simplify_changed_insns. */
1372insn_t
1373sel_gen_insn_from_expr_after (expr_t expr, vinsn_t vinsn, int seqno,
1374 insn_t after)
1375{
1376 expr_t emit_expr;
1377 insn_t insn;
1378 int flags;
1379
1380 emit_expr = set_insn_init (expr, vinsn ? vinsn : EXPR_VINSN (expr),
1381 seqno);
1382 insn = EXPR_INSN_RTX (emit_expr);
1383 add_insn_after (insn, after, BLOCK_FOR_INSN (insn));
1384
1385 flags = INSN_INIT_TODO_SSID;
1386 if (INSN_LUID (insn) == 0)
1387 flags |= INSN_INIT_TODO_LUID;
1388 sel_init_new_insn (insn, flags);
1389
1390 return insn;
1391}
1392
1393/* Move insn from EXPR after AFTER. */
1394insn_t
1395sel_move_insn (expr_t expr, int seqno, insn_t after)
1396{
1397 insn_t insn = EXPR_INSN_RTX (expr);
1398 basic_block bb = BLOCK_FOR_INSN (after);
1399 insn_t next = NEXT_INSN (after);
1400
1401 /* Assert that in move_op we disconnected this insn properly. */
1402 gcc_assert (EXPR_VINSN (INSN_EXPR (insn)) != NULL);
1403 PREV_INSN (insn) = after;
1404 NEXT_INSN (insn) = next;
1405
1406 NEXT_INSN (after) = insn;
1407 PREV_INSN (next) = insn;
1408
1409 /* Update links from insn to bb and vice versa. */
1410 df_insn_change_bb (insn, bb);
1411 if (BB_END (bb) == after)
1412 BB_END (bb) = insn;
1413
1414 prepare_insn_expr (insn, seqno);
1415 return insn;
1416}
1417
1418\f
1419/* Functions to work with right-hand sides. */
1420
1421/* Search for a hash value determined by UID/NEW_VINSN in a sorted vector
1422 VECT and return true when found. Use NEW_VINSN for comparison only when
1423 COMPARE_VINSNS is true. Write to INDP the index on which
1424 the search has stopped, such that inserting the new element at INDP will
1425 retain VECT's sort order. */
1426static bool
1427find_in_history_vect_1 (VEC(expr_history_def, heap) *vect,
1428 unsigned uid, vinsn_t new_vinsn,
1429 bool compare_vinsns, int *indp)
1430{
1431 expr_history_def *arr;
1432 int i, j, len = VEC_length (expr_history_def, vect);
1433
1434 if (len == 0)
1435 {
1436 *indp = 0;
1437 return false;
1438 }
1439
1440 arr = VEC_address (expr_history_def, vect);
1441 i = 0, j = len - 1;
1442
1443 while (i <= j)
1444 {
1445 unsigned auid = arr[i].uid;
1446 vinsn_t avinsn = arr[i].new_expr_vinsn;
1447
1448 if (auid == uid
1449 /* When undoing transformation on a bookkeeping copy, the new vinsn
1450 may not be exactly equal to the one that is saved in the vector.
1451 This is because the insn whose copy we're checking was possibly
1452 substituted itself. */
1453 && (! compare_vinsns
1454 || vinsn_equal_p (avinsn, new_vinsn)))
1455 {
1456 *indp = i;
1457 return true;
1458 }
1459 else if (auid > uid)
1460 break;
1461 i++;
1462 }
1463
1464 *indp = i;
1465 return false;
1466}
1467
1468/* Search for a uid of INSN and NEW_VINSN in a sorted vector VECT. Return
1469 the position found or -1, if no such value is in vector.
1470 Search also for UIDs of insn's originators, if ORIGINATORS_P is true. */
1471int
1472find_in_history_vect (VEC(expr_history_def, heap) *vect, rtx insn,
1473 vinsn_t new_vinsn, bool originators_p)
1474{
1475 int ind;
1476
1477 if (find_in_history_vect_1 (vect, INSN_UID (insn), new_vinsn,
1478 false, &ind))
1479 return ind;
1480
1481 if (INSN_ORIGINATORS (insn) && originators_p)
1482 {
1483 unsigned uid;
1484 bitmap_iterator bi;
1485
1486 EXECUTE_IF_SET_IN_BITMAP (INSN_ORIGINATORS (insn), 0, uid, bi)
1487 if (find_in_history_vect_1 (vect, uid, new_vinsn, false, &ind))
1488 return ind;
1489 }
1490
1491 return -1;
1492}
1493
1494/* Insert new element in a sorted history vector pointed to by PVECT,
1495 if it is not there already. The element is searched using
1496 UID/NEW_EXPR_VINSN pair. TYPE, OLD_EXPR_VINSN and SPEC_DS save
1497 the history of a transformation. */
1498void
1499insert_in_history_vect (VEC (expr_history_def, heap) **pvect,
1500 unsigned uid, enum local_trans_type type,
1501 vinsn_t old_expr_vinsn, vinsn_t new_expr_vinsn,
1502 ds_t spec_ds)
1503{
1504 VEC(expr_history_def, heap) *vect = *pvect;
1505 expr_history_def temp;
1506 bool res;
1507 int ind;
1508
1509 res = find_in_history_vect_1 (vect, uid, new_expr_vinsn, true, &ind);
1510
1511 if (res)
1512 {
1513 expr_history_def *phist = VEC_index (expr_history_def, vect, ind);
1514
c251ad9e
SS
1515 /* It is possible that speculation types of expressions that were
1516 propagated through different paths will be different here. In this
1517 case, merge the status to get the correct check later. */
1518 if (phist->spec_ds != spec_ds)
1519 phist->spec_ds = ds_max_merge (phist->spec_ds, spec_ds);
1520 return;
1521 }
1522
1523 temp.uid = uid;
1524 temp.old_expr_vinsn = old_expr_vinsn;
1525 temp.new_expr_vinsn = new_expr_vinsn;
1526 temp.spec_ds = spec_ds;
1527 temp.type = type;
1528
1529 vinsn_attach (old_expr_vinsn);
1530 vinsn_attach (new_expr_vinsn);
1531 VEC_safe_insert (expr_history_def, heap, vect, ind, &temp);
1532 *pvect = vect;
1533}
1534
1535/* Free history vector PVECT. */
1536static void
1537free_history_vect (VEC (expr_history_def, heap) **pvect)
1538{
1539 unsigned i;
1540 expr_history_def *phist;
1541
1542 if (! *pvect)
1543 return;
1544
1545 for (i = 0;
1546 VEC_iterate (expr_history_def, *pvect, i, phist);
1547 i++)
1548 {
1549 vinsn_detach (phist->old_expr_vinsn);
1550 vinsn_detach (phist->new_expr_vinsn);
1551 }
1552
1553 VEC_free (expr_history_def, heap, *pvect);
1554 *pvect = NULL;
1555}
1556
1557
1558/* Compare two vinsns as rhses if possible and as vinsns otherwise. */
1559bool
1560vinsn_equal_p (vinsn_t x, vinsn_t y)
1561{
1562 rtx_equal_p_callback_function repcf;
1563
1564 if (x == y)
1565 return true;
1566
1567 if (VINSN_TYPE (x) != VINSN_TYPE (y))
1568 return false;
1569
1570 if (VINSN_HASH (x) != VINSN_HASH (y))
1571 return false;
1572
1573 repcf = targetm.sched.skip_rtx_p ? skip_unspecs_callback : NULL;
1574 if (VINSN_SEPARABLE_P (x))
1575 {
1576 /* Compare RHSes of VINSNs. */
1577 gcc_assert (VINSN_RHS (x));
1578 gcc_assert (VINSN_RHS (y));
1579
1580 return rtx_equal_p_cb (VINSN_RHS (x), VINSN_RHS (y), repcf);
1581 }
1582
1583 return rtx_equal_p_cb (VINSN_PATTERN (x), VINSN_PATTERN (y), repcf);
1584}
1585\f
1586
1587/* Functions for working with expressions. */
1588
1589/* Initialize EXPR. */
1590static void
1591init_expr (expr_t expr, vinsn_t vi, int spec, int use, int priority,
1592 int sched_times, int orig_bb_index, ds_t spec_done_ds,
1593 ds_t spec_to_check_ds, int orig_sched_cycle,
1594 VEC(expr_history_def, heap) *history, bool target_available,
1595 bool was_substituted, bool was_renamed, bool needs_spec_check_p,
1596 bool cant_move)
1597{
1598 vinsn_attach (vi);
1599
1600 EXPR_VINSN (expr) = vi;
1601 EXPR_SPEC (expr) = spec;
1602 EXPR_USEFULNESS (expr) = use;
1603 EXPR_PRIORITY (expr) = priority;
1604 EXPR_PRIORITY_ADJ (expr) = 0;
1605 EXPR_SCHED_TIMES (expr) = sched_times;
1606 EXPR_ORIG_BB_INDEX (expr) = orig_bb_index;
1607 EXPR_ORIG_SCHED_CYCLE (expr) = orig_sched_cycle;
1608 EXPR_SPEC_DONE_DS (expr) = spec_done_ds;
1609 EXPR_SPEC_TO_CHECK_DS (expr) = spec_to_check_ds;
1610
1611 if (history)
1612 EXPR_HISTORY_OF_CHANGES (expr) = history;
1613 else
1614 EXPR_HISTORY_OF_CHANGES (expr) = NULL;
1615
1616 EXPR_TARGET_AVAILABLE (expr) = target_available;
1617 EXPR_WAS_SUBSTITUTED (expr) = was_substituted;
1618 EXPR_WAS_RENAMED (expr) = was_renamed;
1619 EXPR_NEEDS_SPEC_CHECK_P (expr) = needs_spec_check_p;
1620 EXPR_CANT_MOVE (expr) = cant_move;
1621}
1622
1623/* Make a copy of the expr FROM into the expr TO. */
1624void
1625copy_expr (expr_t to, expr_t from)
1626{
1627 VEC(expr_history_def, heap) *temp = NULL;
1628
1629 if (EXPR_HISTORY_OF_CHANGES (from))
1630 {
1631 unsigned i;
1632 expr_history_def *phist;
1633
1634 temp = VEC_copy (expr_history_def, heap, EXPR_HISTORY_OF_CHANGES (from));
1635 for (i = 0;
1636 VEC_iterate (expr_history_def, temp, i, phist);
1637 i++)
1638 {
1639 vinsn_attach (phist->old_expr_vinsn);
1640 vinsn_attach (phist->new_expr_vinsn);
1641 }
1642 }
1643
1644 init_expr (to, EXPR_VINSN (from), EXPR_SPEC (from),
1645 EXPR_USEFULNESS (from), EXPR_PRIORITY (from),
1646 EXPR_SCHED_TIMES (from), EXPR_ORIG_BB_INDEX (from),
1647 EXPR_SPEC_DONE_DS (from), EXPR_SPEC_TO_CHECK_DS (from),
1648 EXPR_ORIG_SCHED_CYCLE (from), temp,
1649 EXPR_TARGET_AVAILABLE (from), EXPR_WAS_SUBSTITUTED (from),
1650 EXPR_WAS_RENAMED (from), EXPR_NEEDS_SPEC_CHECK_P (from),
1651 EXPR_CANT_MOVE (from));
1652}
1653
1654/* Same, but the final expr will not ever be in av sets, so don't copy
1655 "uninteresting" data such as bitmap cache. */
1656void
1657copy_expr_onside (expr_t to, expr_t from)
1658{
1659 init_expr (to, EXPR_VINSN (from), EXPR_SPEC (from), EXPR_USEFULNESS (from),
1660 EXPR_PRIORITY (from), EXPR_SCHED_TIMES (from), 0,
1661 EXPR_SPEC_DONE_DS (from), EXPR_SPEC_TO_CHECK_DS (from), 0, NULL,
1662 EXPR_TARGET_AVAILABLE (from), EXPR_WAS_SUBSTITUTED (from),
1663 EXPR_WAS_RENAMED (from), EXPR_NEEDS_SPEC_CHECK_P (from),
1664 EXPR_CANT_MOVE (from));
1665}
1666
1667/* Prepare the expr of INSN for scheduling. Used when moving insn and when
1668 initializing new insns. */
1669static void
1670prepare_insn_expr (insn_t insn, int seqno)
1671{
1672 expr_t expr = INSN_EXPR (insn);
1673 ds_t ds;
1674
1675 INSN_SEQNO (insn) = seqno;
1676 EXPR_ORIG_BB_INDEX (expr) = BLOCK_NUM (insn);
1677 EXPR_SPEC (expr) = 0;
1678 EXPR_ORIG_SCHED_CYCLE (expr) = 0;
1679 EXPR_WAS_SUBSTITUTED (expr) = 0;
1680 EXPR_WAS_RENAMED (expr) = 0;
1681 EXPR_TARGET_AVAILABLE (expr) = 1;
1682 INSN_LIVE_VALID_P (insn) = false;
1683
1684 /* ??? If this expression is speculative, make its dependence
1685 as weak as possible. We can filter this expression later
1686 in process_spec_exprs, because we do not distinguish
1687 between the status we got during compute_av_set and the
1688 existing status. To be fixed. */
1689 ds = EXPR_SPEC_DONE_DS (expr);
1690 if (ds)
1691 EXPR_SPEC_DONE_DS (expr) = ds_get_max_dep_weak (ds);
1692
1693 free_history_vect (&EXPR_HISTORY_OF_CHANGES (expr));
1694}
1695
1696/* Update target_available bits when merging exprs TO and FROM. SPLIT_POINT
1697 is non-null when expressions are merged from different successors at
1698 a split point. */
1699static void
1700update_target_availability (expr_t to, expr_t from, insn_t split_point)
1701{
1702 if (EXPR_TARGET_AVAILABLE (to) < 0
1703 || EXPR_TARGET_AVAILABLE (from) < 0)
1704 EXPR_TARGET_AVAILABLE (to) = -1;
1705 else
1706 {
1707 /* We try to detect the case when one of the expressions
1708 can only be reached through another one. In this case,
1709 we can do better. */
1710 if (split_point == NULL)
1711 {
1712 int toind, fromind;
1713
1714 toind = EXPR_ORIG_BB_INDEX (to);
1715 fromind = EXPR_ORIG_BB_INDEX (from);
1716
1717 if (toind && toind == fromind)
1718 /* Do nothing -- everything is done in
1719 merge_with_other_exprs. */
1720 ;
1721 else
1722 EXPR_TARGET_AVAILABLE (to) = -1;
1723 }
1724 else
1725 EXPR_TARGET_AVAILABLE (to) &= EXPR_TARGET_AVAILABLE (from);
1726 }
1727}
1728
1729/* Update speculation bits when merging exprs TO and FROM. SPLIT_POINT
1730 is non-null when expressions are merged from different successors at
1731 a split point. */
1732static void
1733update_speculative_bits (expr_t to, expr_t from, insn_t split_point)
1734{
1735 ds_t old_to_ds, old_from_ds;
1736
1737 old_to_ds = EXPR_SPEC_DONE_DS (to);
1738 old_from_ds = EXPR_SPEC_DONE_DS (from);
1739
1740 EXPR_SPEC_DONE_DS (to) = ds_max_merge (old_to_ds, old_from_ds);
1741 EXPR_SPEC_TO_CHECK_DS (to) |= EXPR_SPEC_TO_CHECK_DS (from);
1742 EXPR_NEEDS_SPEC_CHECK_P (to) |= EXPR_NEEDS_SPEC_CHECK_P (from);
1743
1744 /* When merging e.g. control & data speculative exprs, or a control
1745 speculative with a control&data speculative one, we really have
1746 to change vinsn too. Also, when speculative status is changed,
1747 we also need to record this as a transformation in expr's history. */
1748 if ((old_to_ds & SPECULATIVE) || (old_from_ds & SPECULATIVE))
1749 {
1750 old_to_ds = ds_get_speculation_types (old_to_ds);
1751 old_from_ds = ds_get_speculation_types (old_from_ds);
1752
1753 if (old_to_ds != old_from_ds)
1754 {
1755 ds_t record_ds;
1756
1757 /* When both expressions are speculative, we need to change
1758 the vinsn first. */
1759 if ((old_to_ds & SPECULATIVE) && (old_from_ds & SPECULATIVE))
1760 {
1761 int res;
1762
1763 res = speculate_expr (to, EXPR_SPEC_DONE_DS (to));
1764 gcc_assert (res >= 0);
1765 }
1766
1767 if (split_point != NULL)
1768 {
1769 /* Record the change with proper status. */
1770 record_ds = EXPR_SPEC_DONE_DS (to) & SPECULATIVE;
1771 record_ds &= ~(old_to_ds & SPECULATIVE);
1772 record_ds &= ~(old_from_ds & SPECULATIVE);
1773
1774 insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (to),
1775 INSN_UID (split_point), TRANS_SPECULATION,
1776 EXPR_VINSN (from), EXPR_VINSN (to),
1777 record_ds);
1778 }
1779 }
1780 }
1781}
1782
1783
1784/* Merge bits of FROM expr to TO expr. When SPLIT_POINT is not NULL,
1785 this is done along different paths. */
1786void
1787merge_expr_data (expr_t to, expr_t from, insn_t split_point)
1788{
1789 int i;
1790 expr_history_def *phist;
1791
1792 /* For now, we just set the spec of resulting expr to be minimum of the specs
1793 of merged exprs. */
1794 if (EXPR_SPEC (to) > EXPR_SPEC (from))
1795 EXPR_SPEC (to) = EXPR_SPEC (from);
1796
1797 if (split_point)
1798 EXPR_USEFULNESS (to) += EXPR_USEFULNESS (from);
1799 else
1800 EXPR_USEFULNESS (to) = MAX (EXPR_USEFULNESS (to),
1801 EXPR_USEFULNESS (from));
1802
1803 if (EXPR_PRIORITY (to) < EXPR_PRIORITY (from))
1804 EXPR_PRIORITY (to) = EXPR_PRIORITY (from);
1805
1806 if (EXPR_SCHED_TIMES (to) > EXPR_SCHED_TIMES (from))
1807 EXPR_SCHED_TIMES (to) = EXPR_SCHED_TIMES (from);
1808
1809 if (EXPR_ORIG_BB_INDEX (to) != EXPR_ORIG_BB_INDEX (from))
1810 EXPR_ORIG_BB_INDEX (to) = 0;
1811
1812 EXPR_ORIG_SCHED_CYCLE (to) = MIN (EXPR_ORIG_SCHED_CYCLE (to),
1813 EXPR_ORIG_SCHED_CYCLE (from));
1814
1815 /* We keep this vector sorted. */
1816 for (i = 0;
1817 VEC_iterate (expr_history_def, EXPR_HISTORY_OF_CHANGES (from),
1818 i, phist);
1819 i++)
1820 insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (to),
1821 phist->uid, phist->type,
1822 phist->old_expr_vinsn, phist->new_expr_vinsn,
1823 phist->spec_ds);
1824
1825 EXPR_WAS_SUBSTITUTED (to) |= EXPR_WAS_SUBSTITUTED (from);
1826 EXPR_WAS_RENAMED (to) |= EXPR_WAS_RENAMED (from);
1827 EXPR_CANT_MOVE (to) |= EXPR_CANT_MOVE (from);
1828
1829 update_target_availability (to, from, split_point);
1830 update_speculative_bits (to, from, split_point);
1831}
1832
1833/* Merge bits of FROM expr to TO expr. Vinsns in the exprs should be equal
1834 in terms of vinsn_equal_p. SPLIT_POINT is non-null when expressions
1835 are merged from different successors at a split point. */
1836void
1837merge_expr (expr_t to, expr_t from, insn_t split_point)
1838{
1839 vinsn_t to_vi = EXPR_VINSN (to);
1840 vinsn_t from_vi = EXPR_VINSN (from);
1841
1842 gcc_assert (vinsn_equal_p (to_vi, from_vi));
1843
1844 /* Make sure that speculative pattern is propagated into exprs that
1845 have non-speculative one. This will provide us with consistent
1846 speculative bits and speculative patterns inside expr. */
1847 if (EXPR_SPEC_DONE_DS (to) == 0
1848 && EXPR_SPEC_DONE_DS (from) != 0)
1849 change_vinsn_in_expr (to, EXPR_VINSN (from));
1850
1851 merge_expr_data (to, from, split_point);
1852 gcc_assert (EXPR_USEFULNESS (to) <= REG_BR_PROB_BASE);
1853}
1854
1855/* Clear the information of this EXPR. */
1856void
1857clear_expr (expr_t expr)
1858{
1859
1860 vinsn_detach (EXPR_VINSN (expr));
1861 EXPR_VINSN (expr) = NULL;
1862
1863 free_history_vect (&EXPR_HISTORY_OF_CHANGES (expr));
1864}
1865
1866/* For a given LV_SET, mark EXPR having unavailable target register. */
1867static void
1868set_unavailable_target_for_expr (expr_t expr, regset lv_set)
1869{
1870 if (EXPR_SEPARABLE_P (expr))
1871 {
1872 if (REG_P (EXPR_LHS (expr))
1873 && bitmap_bit_p (lv_set, REGNO (EXPR_LHS (expr))))
1874 {
1875 /* If it's an insn like r1 = use (r1, ...), and it exists in
1876 different forms in each of the av_sets being merged, we can't say
1877 whether original destination register is available or not.
1878 However, this still works if destination register is not used
1879 in the original expression: if the branch at which LV_SET we're
1880 looking here is not actually 'other branch' in sense that same
1881 expression is available through it (but it can't be determined
1882 at computation stage because of transformations on one of the
1883 branches), it still won't affect the availability.
1884 Liveness of a register somewhere on a code motion path means
1885 it's either read somewhere on a codemotion path, live on
1886 'other' branch, live at the point immediately following
1887 the original operation, or is read by the original operation.
1888 The latter case is filtered out in the condition below.
1889 It still doesn't cover the case when register is defined and used
1890 somewhere within the code motion path, and in this case we could
1891 miss a unifying code motion along both branches using a renamed
1892 register, but it won't affect a code correctness since upon
1893 an actual code motion a bookkeeping code would be generated. */
1894 if (bitmap_bit_p (VINSN_REG_USES (EXPR_VINSN (expr)),
1895 REGNO (EXPR_LHS (expr))))
1896 EXPR_TARGET_AVAILABLE (expr) = -1;
1897 else
1898 EXPR_TARGET_AVAILABLE (expr) = false;
1899 }
1900 }
1901 else
1902 {
1903 unsigned regno;
1904 reg_set_iterator rsi;
1905
1906 EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_SETS (EXPR_VINSN (expr)),
1907 0, regno, rsi)
1908 if (bitmap_bit_p (lv_set, regno))
1909 {
1910 EXPR_TARGET_AVAILABLE (expr) = false;
1911 break;
1912 }
1913
1914 EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_CLOBBERS (EXPR_VINSN (expr)),
1915 0, regno, rsi)
1916 if (bitmap_bit_p (lv_set, regno))
1917 {
1918 EXPR_TARGET_AVAILABLE (expr) = false;
1919 break;
1920 }
1921 }
1922}
1923
1924/* Try to make EXPR speculative. Return 1 when EXPR's pattern
1925 or dependence status have changed, 2 when also the target register
1926 became unavailable, 0 if nothing had to be changed. */
1927int
1928speculate_expr (expr_t expr, ds_t ds)
1929{
1930 int res;
1931 rtx orig_insn_rtx;
1932 rtx spec_pat;
1933 ds_t target_ds, current_ds;
1934
1935 /* Obtain the status we need to put on EXPR. */
1936 target_ds = (ds & SPECULATIVE);
1937 current_ds = EXPR_SPEC_DONE_DS (expr);
1938 ds = ds_full_merge (current_ds, target_ds, NULL_RTX, NULL_RTX);
1939
1940 orig_insn_rtx = EXPR_INSN_RTX (expr);
1941
1942 res = sched_speculate_insn (orig_insn_rtx, ds, &spec_pat);
1943
1944 switch (res)
1945 {
1946 case 0:
1947 EXPR_SPEC_DONE_DS (expr) = ds;
1948 return current_ds != ds ? 1 : 0;
1949
1950 case 1:
1951 {
1952 rtx spec_insn_rtx = create_insn_rtx_from_pattern (spec_pat, NULL_RTX);
1953 vinsn_t spec_vinsn = create_vinsn_from_insn_rtx (spec_insn_rtx, false);
1954
1955 change_vinsn_in_expr (expr, spec_vinsn);
1956 EXPR_SPEC_DONE_DS (expr) = ds;
1957 EXPR_NEEDS_SPEC_CHECK_P (expr) = true;
1958
1959 /* Do not allow clobbering the address register of speculative
1960 insns. */
1961 if (bitmap_bit_p (VINSN_REG_USES (EXPR_VINSN (expr)),
1962 expr_dest_regno (expr)))
1963 {
1964 EXPR_TARGET_AVAILABLE (expr) = false;
1965 return 2;
1966 }
1967
1968 return 1;
1969 }
1970
1971 case -1:
1972 return -1;
1973
1974 default:
1975 gcc_unreachable ();
1976 return -1;
1977 }
1978}
1979
1980/* Return a destination register, if any, of EXPR. */
1981rtx
1982expr_dest_reg (expr_t expr)
1983{
1984 rtx dest = VINSN_LHS (EXPR_VINSN (expr));
1985
1986 if (dest != NULL_RTX && REG_P (dest))
1987 return dest;
1988
1989 return NULL_RTX;
1990}
1991
1992/* Returns the REGNO of the R's destination. */
1993unsigned
1994expr_dest_regno (expr_t expr)
1995{
1996 rtx dest = expr_dest_reg (expr);
1997
1998 gcc_assert (dest != NULL_RTX);
1999 return REGNO (dest);
2000}
2001
2002/* For a given LV_SET, mark all expressions in JOIN_SET, but not present in
2003 AV_SET having unavailable target register. */
2004void
2005mark_unavailable_targets (av_set_t join_set, av_set_t av_set, regset lv_set)
2006{
2007 expr_t expr;
2008 av_set_iterator avi;
2009
2010 FOR_EACH_EXPR (expr, avi, join_set)
2011 if (av_set_lookup (av_set, EXPR_VINSN (expr)) == NULL)
2012 set_unavailable_target_for_expr (expr, lv_set);
2013}
2014\f
2015
2016/* Av set functions. */
2017
2018/* Add a new element to av set SETP.
2019 Return the element added. */
2020static av_set_t
2021av_set_add_element (av_set_t *setp)
2022{
2023 /* Insert at the beginning of the list. */
2024 _list_add (setp);
2025 return *setp;
2026}
2027
2028/* Add EXPR to SETP. */
2029void
2030av_set_add (av_set_t *setp, expr_t expr)
2031{
2032 av_set_t elem;
2033
2034 gcc_assert (!INSN_NOP_P (EXPR_INSN_RTX (expr)));
2035 elem = av_set_add_element (setp);
2036 copy_expr (_AV_SET_EXPR (elem), expr);
2037}
2038
2039/* Same, but do not copy EXPR. */
2040static void
2041av_set_add_nocopy (av_set_t *setp, expr_t expr)
2042{
2043 av_set_t elem;
2044
2045 elem = av_set_add_element (setp);
2046 *_AV_SET_EXPR (elem) = *expr;
2047}
2048
2049/* Remove expr pointed to by IP from the av_set. */
2050void
2051av_set_iter_remove (av_set_iterator *ip)
2052{
2053 clear_expr (_AV_SET_EXPR (*ip->lp));
2054 _list_iter_remove (ip);
2055}
2056
2057/* Search for an expr in SET, such that it's equivalent to SOUGHT_VINSN in the
2058 sense of vinsn_equal_p function. Return NULL if no such expr is
2059 in SET was found. */
2060expr_t
2061av_set_lookup (av_set_t set, vinsn_t sought_vinsn)
2062{
2063 expr_t expr;
2064 av_set_iterator i;
2065
2066 FOR_EACH_EXPR (expr, i, set)
2067 if (vinsn_equal_p (EXPR_VINSN (expr), sought_vinsn))
2068 return expr;
2069 return NULL;
2070}
2071
2072/* Same, but also remove the EXPR found. */
2073static expr_t
2074av_set_lookup_and_remove (av_set_t *setp, vinsn_t sought_vinsn)
2075{
2076 expr_t expr;
2077 av_set_iterator i;
2078
2079 FOR_EACH_EXPR_1 (expr, i, setp)
2080 if (vinsn_equal_p (EXPR_VINSN (expr), sought_vinsn))
2081 {
2082 _list_iter_remove_nofree (&i);
2083 return expr;
2084 }
2085 return NULL;
2086}
2087
2088/* Search for an expr in SET, such that it's equivalent to EXPR in the
2089 sense of vinsn_equal_p function of their vinsns, but not EXPR itself.
2090 Returns NULL if no such expr is in SET was found. */
2091static expr_t
2092av_set_lookup_other_equiv_expr (av_set_t set, expr_t expr)
2093{
2094 expr_t cur_expr;
2095 av_set_iterator i;
2096
2097 FOR_EACH_EXPR (cur_expr, i, set)
2098 {
2099 if (cur_expr == expr)
2100 continue;
2101 if (vinsn_equal_p (EXPR_VINSN (cur_expr), EXPR_VINSN (expr)))
2102 return cur_expr;
2103 }
2104
2105 return NULL;
2106}
2107
2108/* If other expression is already in AVP, remove one of them. */
2109expr_t
2110merge_with_other_exprs (av_set_t *avp, av_set_iterator *ip, expr_t expr)
2111{
2112 expr_t expr2;
2113
2114 expr2 = av_set_lookup_other_equiv_expr (*avp, expr);
2115 if (expr2 != NULL)
2116 {
2117 /* Reset target availability on merge, since taking it only from one
2118 of the exprs would be controversial for different code. */
2119 EXPR_TARGET_AVAILABLE (expr2) = -1;
2120 EXPR_USEFULNESS (expr2) = 0;
2121
2122 merge_expr (expr2, expr, NULL);
2123
2124 /* Fix usefulness as it should be now REG_BR_PROB_BASE. */
2125 EXPR_USEFULNESS (expr2) = REG_BR_PROB_BASE;
2126
2127 av_set_iter_remove (ip);
2128 return expr2;
2129 }
2130
2131 return expr;
2132}
2133
2134/* Return true if there is an expr that correlates to VI in SET. */
2135bool
2136av_set_is_in_p (av_set_t set, vinsn_t vi)
2137{
2138 return av_set_lookup (set, vi) != NULL;
2139}
2140
2141/* Return a copy of SET. */
2142av_set_t
2143av_set_copy (av_set_t set)
2144{
2145 expr_t expr;
2146 av_set_iterator i;
2147 av_set_t res = NULL;
2148
2149 FOR_EACH_EXPR (expr, i, set)
2150 av_set_add (&res, expr);
2151
2152 return res;
2153}
2154
2155/* Join two av sets that do not have common elements by attaching second set
2156 (pointed to by FROMP) to the end of first set (TO_TAILP must point to
2157 _AV_SET_NEXT of first set's last element). */
2158static void
2159join_distinct_sets (av_set_t *to_tailp, av_set_t *fromp)
2160{
2161 gcc_assert (*to_tailp == NULL);
2162 *to_tailp = *fromp;
2163 *fromp = NULL;
2164}
2165
2166/* Makes set pointed to by TO to be the union of TO and FROM. Clear av_set
2167 pointed to by FROMP afterwards. */
2168void
2169av_set_union_and_clear (av_set_t *top, av_set_t *fromp, insn_t insn)
2170{
2171 expr_t expr1;
2172 av_set_iterator i;
2173
2174 /* Delete from TOP all exprs, that present in FROMP. */
2175 FOR_EACH_EXPR_1 (expr1, i, top)
2176 {
2177 expr_t expr2 = av_set_lookup (*fromp, EXPR_VINSN (expr1));
2178
2179 if (expr2)
2180 {
2181 merge_expr (expr2, expr1, insn);
2182 av_set_iter_remove (&i);
2183 }
2184 }
2185
2186 join_distinct_sets (i.lp, fromp);
2187}
2188
2189/* Same as above, but also update availability of target register in
2190 TOP judging by TO_LV_SET and FROM_LV_SET. */
2191void
2192av_set_union_and_live (av_set_t *top, av_set_t *fromp, regset to_lv_set,
2193 regset from_lv_set, insn_t insn)
2194{
2195 expr_t expr1;
2196 av_set_iterator i;
2197 av_set_t *to_tailp, in_both_set = NULL;
2198
2199 /* Delete from TOP all expres, that present in FROMP. */
2200 FOR_EACH_EXPR_1 (expr1, i, top)
2201 {
2202 expr_t expr2 = av_set_lookup_and_remove (fromp, EXPR_VINSN (expr1));
2203
2204 if (expr2)
2205 {
2206 /* It may be that the expressions have different destination
2207 registers, in which case we need to check liveness here. */
2208 if (EXPR_SEPARABLE_P (expr1))
2209 {
2210 int regno1 = (REG_P (EXPR_LHS (expr1))
2211 ? (int) expr_dest_regno (expr1) : -1);
2212 int regno2 = (REG_P (EXPR_LHS (expr2))
2213 ? (int) expr_dest_regno (expr2) : -1);
2214
2215 /* ??? We don't have a way to check restrictions for
2216 *other* register on the current path, we did it only
2217 for the current target register. Give up. */
2218 if (regno1 != regno2)
2219 EXPR_TARGET_AVAILABLE (expr2) = -1;
2220 }
2221 else if (EXPR_INSN_RTX (expr1) != EXPR_INSN_RTX (expr2))
2222 EXPR_TARGET_AVAILABLE (expr2) = -1;
2223
2224 merge_expr (expr2, expr1, insn);
2225 av_set_add_nocopy (&in_both_set, expr2);
2226 av_set_iter_remove (&i);
2227 }
2228 else
2229 /* EXPR1 is present in TOP, but not in FROMP. Check it on
2230 FROM_LV_SET. */
2231 set_unavailable_target_for_expr (expr1, from_lv_set);
2232 }
2233 to_tailp = i.lp;
2234
2235 /* These expressions are not present in TOP. Check liveness
2236 restrictions on TO_LV_SET. */
2237 FOR_EACH_EXPR (expr1, i, *fromp)
2238 set_unavailable_target_for_expr (expr1, to_lv_set);
2239
2240 join_distinct_sets (i.lp, &in_both_set);
2241 join_distinct_sets (to_tailp, fromp);
2242}
2243
2244/* Clear av_set pointed to by SETP. */
2245void
2246av_set_clear (av_set_t *setp)
2247{
2248 expr_t expr;
2249 av_set_iterator i;
2250
2251 FOR_EACH_EXPR_1 (expr, i, setp)
2252 av_set_iter_remove (&i);
2253
2254 gcc_assert (*setp == NULL);
2255}
2256
2257/* Leave only one non-speculative element in the SETP. */
2258void
2259av_set_leave_one_nonspec (av_set_t *setp)
2260{
2261 expr_t expr;
2262 av_set_iterator i;
2263 bool has_one_nonspec = false;
2264
2265 /* Keep all speculative exprs, and leave one non-speculative
2266 (the first one). */
2267 FOR_EACH_EXPR_1 (expr, i, setp)
2268 {
2269 if (!EXPR_SPEC_DONE_DS (expr))
2270 {
2271 if (has_one_nonspec)
2272 av_set_iter_remove (&i);
2273 else
2274 has_one_nonspec = true;
2275 }
2276 }
2277}
2278
2279/* Return the N'th element of the SET. */
2280expr_t
2281av_set_element (av_set_t set, int n)
2282{
2283 expr_t expr;
2284 av_set_iterator i;
2285
2286 FOR_EACH_EXPR (expr, i, set)
2287 if (n-- == 0)
2288 return expr;
2289
2290 gcc_unreachable ();
2291 return NULL;
2292}
2293
2294/* Deletes all expressions from AVP that are conditional branches (IFs). */
2295void
2296av_set_substract_cond_branches (av_set_t *avp)
2297{
2298 av_set_iterator i;
2299 expr_t expr;
2300
2301 FOR_EACH_EXPR_1 (expr, i, avp)
2302 if (vinsn_cond_branch_p (EXPR_VINSN (expr)))
2303 av_set_iter_remove (&i);
2304}
2305
2306/* Multiplies usefulness attribute of each member of av-set *AVP by
2307 value PROB / ALL_PROB. */
2308void
2309av_set_split_usefulness (av_set_t av, int prob, int all_prob)
2310{
2311 av_set_iterator i;
2312 expr_t expr;
2313
2314 FOR_EACH_EXPR (expr, i, av)
2315 EXPR_USEFULNESS (expr) = (all_prob
2316 ? (EXPR_USEFULNESS (expr) * prob) / all_prob
2317 : 0);
2318}
2319
2320/* Leave in AVP only those expressions, which are present in AV,
2321 and return it. */
2322void
2323av_set_intersect (av_set_t *avp, av_set_t av)
2324{
2325 av_set_iterator i;
2326 expr_t expr;
2327
2328 FOR_EACH_EXPR_1 (expr, i, avp)
2329 if (av_set_lookup (av, EXPR_VINSN (expr)) == NULL)
2330 av_set_iter_remove (&i);
2331}
2332
2333\f
2334
2335/* Dependence hooks to initialize insn data. */
2336
2337/* This is used in hooks callable from dependence analysis when initializing
2338 instruction's data. */
2339static struct
2340{
2341 /* Where the dependence was found (lhs/rhs). */
2342 deps_where_t where;
2343
2344 /* The actual data object to initialize. */
2345 idata_t id;
2346
2347 /* True when the insn should not be made clonable. */
2348 bool force_unique_p;
2349
2350 /* True when insn should be treated as of type USE, i.e. never renamed. */
2351 bool force_use_p;
2352} deps_init_id_data;
2353
2354
2355/* Setup ID for INSN. FORCE_UNIQUE_P is true when INSN should not be
2356 clonable. */
2357static void
2358setup_id_for_insn (idata_t id, insn_t insn, bool force_unique_p)
2359{
2360 int type;
2361
2362 /* Determine whether INSN could be cloned and return appropriate vinsn type.
2363 That clonable insns which can be separated into lhs and rhs have type SET.
2364 Other clonable insns have type USE. */
2365 type = GET_CODE (insn);
2366
2367 /* Only regular insns could be cloned. */
2368 if (type == INSN && !force_unique_p)
2369 type = SET;
2370 else if (type == JUMP_INSN && simplejump_p (insn))
2371 type = PC;
2372
2373 IDATA_TYPE (id) = type;
2374 IDATA_REG_SETS (id) = get_clear_regset_from_pool ();
2375 IDATA_REG_USES (id) = get_clear_regset_from_pool ();
2376 IDATA_REG_CLOBBERS (id) = get_clear_regset_from_pool ();
2377}
2378
2379/* Start initializing insn data. */
2380static void
2381deps_init_id_start_insn (insn_t insn)
2382{
2383 gcc_assert (deps_init_id_data.where == DEPS_IN_NOWHERE);
2384
2385 setup_id_for_insn (deps_init_id_data.id, insn,
2386 deps_init_id_data.force_unique_p);
2387 deps_init_id_data.where = DEPS_IN_INSN;
2388}
2389
2390/* Start initializing lhs data. */
2391static void
2392deps_init_id_start_lhs (rtx lhs)
2393{
2394 gcc_assert (deps_init_id_data.where == DEPS_IN_INSN);
2395 gcc_assert (IDATA_LHS (deps_init_id_data.id) == NULL);
2396
2397 if (IDATA_TYPE (deps_init_id_data.id) == SET)
2398 {
2399 IDATA_LHS (deps_init_id_data.id) = lhs;
2400 deps_init_id_data.where = DEPS_IN_LHS;
2401 }
2402}
2403
2404/* Finish initializing lhs data. */
2405static void
2406deps_init_id_finish_lhs (void)
2407{
2408 deps_init_id_data.where = DEPS_IN_INSN;
2409}
2410
2411/* Note a set of REGNO. */
2412static void
2413deps_init_id_note_reg_set (int regno)
2414{
2415 haifa_note_reg_set (regno);
2416
2417 if (deps_init_id_data.where == DEPS_IN_RHS)
2418 deps_init_id_data.force_use_p = true;
2419
2420 if (IDATA_TYPE (deps_init_id_data.id) != PC)
2421 SET_REGNO_REG_SET (IDATA_REG_SETS (deps_init_id_data.id), regno);
2422
2423#ifdef STACK_REGS
2424 /* Make instructions that set stack registers to be ineligible for
2425 renaming to avoid issues with find_used_regs. */
2426 if (IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG))
2427 deps_init_id_data.force_use_p = true;
2428#endif
2429}
2430
2431/* Note a clobber of REGNO. */
2432static void
2433deps_init_id_note_reg_clobber (int regno)
2434{
2435 haifa_note_reg_clobber (regno);
2436
2437 if (deps_init_id_data.where == DEPS_IN_RHS)
2438 deps_init_id_data.force_use_p = true;
2439
2440 if (IDATA_TYPE (deps_init_id_data.id) != PC)
2441 SET_REGNO_REG_SET (IDATA_REG_CLOBBERS (deps_init_id_data.id), regno);
2442}
2443
2444/* Note a use of REGNO. */
2445static void
2446deps_init_id_note_reg_use (int regno)
2447{
2448 haifa_note_reg_use (regno);
2449
2450 if (IDATA_TYPE (deps_init_id_data.id) != PC)
2451 SET_REGNO_REG_SET (IDATA_REG_USES (deps_init_id_data.id), regno);
2452}
2453
2454/* Start initializing rhs data. */
2455static void
2456deps_init_id_start_rhs (rtx rhs)
2457{
2458 gcc_assert (deps_init_id_data.where == DEPS_IN_INSN);
2459
2460 /* And there was no sel_deps_reset_to_insn (). */
2461 if (IDATA_LHS (deps_init_id_data.id) != NULL)
2462 {
2463 IDATA_RHS (deps_init_id_data.id) = rhs;
2464 deps_init_id_data.where = DEPS_IN_RHS;
2465 }
2466}
2467
2468/* Finish initializing rhs data. */
2469static void
2470deps_init_id_finish_rhs (void)
2471{
2472 gcc_assert (deps_init_id_data.where == DEPS_IN_RHS
2473 || deps_init_id_data.where == DEPS_IN_INSN);
2474 deps_init_id_data.where = DEPS_IN_INSN;
2475}
2476
2477/* Finish initializing insn data. */
2478static void
2479deps_init_id_finish_insn (void)
2480{
2481 gcc_assert (deps_init_id_data.where == DEPS_IN_INSN);
2482
2483 if (IDATA_TYPE (deps_init_id_data.id) == SET)
2484 {
2485 rtx lhs = IDATA_LHS (deps_init_id_data.id);
2486 rtx rhs = IDATA_RHS (deps_init_id_data.id);
2487
2488 if (lhs == NULL || rhs == NULL || !lhs_and_rhs_separable_p (lhs, rhs)
2489 || deps_init_id_data.force_use_p)
2490 {
2491 /* This should be a USE, as we don't want to schedule its RHS
2492 separately. However, we still want to have them recorded
2493 for the purposes of substitution. That's why we don't
2494 simply call downgrade_to_use () here. */
2495 gcc_assert (IDATA_TYPE (deps_init_id_data.id) == SET);
2496 gcc_assert (!lhs == !rhs);
2497
2498 IDATA_TYPE (deps_init_id_data.id) = USE;
2499 }
2500 }
2501
2502 deps_init_id_data.where = DEPS_IN_NOWHERE;
2503}
2504
2505/* This is dependence info used for initializing insn's data. */
2506static struct sched_deps_info_def deps_init_id_sched_deps_info;
2507
2508/* This initializes most of the static part of the above structure. */
2509static const struct sched_deps_info_def const_deps_init_id_sched_deps_info =
2510 {
2511 NULL,
2512
2513 deps_init_id_start_insn,
2514 deps_init_id_finish_insn,
2515 deps_init_id_start_lhs,
2516 deps_init_id_finish_lhs,
2517 deps_init_id_start_rhs,
2518 deps_init_id_finish_rhs,
2519 deps_init_id_note_reg_set,
2520 deps_init_id_note_reg_clobber,
2521 deps_init_id_note_reg_use,
2522 NULL, /* note_mem_dep */
2523 NULL, /* note_dep */
2524
2525 0, /* use_cselib */
2526 0, /* use_deps_list */
2527 0 /* generate_spec_deps */
2528 };
2529
2530/* Initialize INSN's lhs and rhs in ID. When FORCE_UNIQUE_P is true,
2531 we don't actually need information about lhs and rhs. */
2532static void
2533setup_id_lhs_rhs (idata_t id, insn_t insn, bool force_unique_p)
2534{
2535 rtx pat = PATTERN (insn);
2536
2537 if (GET_CODE (insn) == INSN
2538 && GET_CODE (pat) == SET
2539 && !force_unique_p)
2540 {
2541 IDATA_RHS (id) = SET_SRC (pat);
2542 IDATA_LHS (id) = SET_DEST (pat);
2543 }
2544 else
2545 IDATA_LHS (id) = IDATA_RHS (id) = NULL;
2546}
2547
2548/* Possibly downgrade INSN to USE. */
2549static void
2550maybe_downgrade_id_to_use (idata_t id, insn_t insn)
2551{
2552 bool must_be_use = false;
2553 unsigned uid = INSN_UID (insn);
2554 df_ref *rec;
2555 rtx lhs = IDATA_LHS (id);
2556 rtx rhs = IDATA_RHS (id);
2557
2558 /* We downgrade only SETs. */
2559 if (IDATA_TYPE (id) != SET)
2560 return;
2561
2562 if (!lhs || !lhs_and_rhs_separable_p (lhs, rhs))
2563 {
2564 IDATA_TYPE (id) = USE;
2565 return;
2566 }
2567
2568 for (rec = DF_INSN_UID_DEFS (uid); *rec; rec++)
2569 {
2570 df_ref def = *rec;
2571
2572 if (DF_REF_INSN (def)
2573 && DF_REF_FLAGS_IS_SET (def, DF_REF_PRE_POST_MODIFY)
2574 && loc_mentioned_in_p (DF_REF_LOC (def), IDATA_RHS (id)))
2575 {
2576 must_be_use = true;
2577 break;
2578 }
2579
2580#ifdef STACK_REGS
2581 /* Make instructions that set stack registers to be ineligible for
2582 renaming to avoid issues with find_used_regs. */
2583 if (IN_RANGE (DF_REF_REGNO (def), FIRST_STACK_REG, LAST_STACK_REG))
2584 {
2585 must_be_use = true;
2586 break;
2587 }
2588#endif
2589 }
2590
2591 if (must_be_use)
2592 IDATA_TYPE (id) = USE;
2593}
2594
2595/* Setup register sets describing INSN in ID. */
2596static void
2597setup_id_reg_sets (idata_t id, insn_t insn)
2598{
2599 unsigned uid = INSN_UID (insn);
2600 df_ref *rec;
2601 regset tmp = get_clear_regset_from_pool ();
2602
2603 for (rec = DF_INSN_UID_DEFS (uid); *rec; rec++)
2604 {
2605 df_ref def = *rec;
2606 unsigned int regno = DF_REF_REGNO (def);
2607
2608 /* Post modifies are treated like clobbers by sched-deps.c. */
2609 if (DF_REF_FLAGS_IS_SET (def, (DF_REF_MUST_CLOBBER
2610 | DF_REF_PRE_POST_MODIFY)))
2611 SET_REGNO_REG_SET (IDATA_REG_CLOBBERS (id), regno);
2612 else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
2613 {
2614 SET_REGNO_REG_SET (IDATA_REG_SETS (id), regno);
2615
2616#ifdef STACK_REGS
2617 /* For stack registers, treat writes to them as writes
2618 to the first one to be consistent with sched-deps.c. */
2619 if (IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG))
2620 SET_REGNO_REG_SET (IDATA_REG_SETS (id), FIRST_STACK_REG);
2621#endif
2622 }
2623 /* Mark special refs that generate read/write def pair. */
2624 if (DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL)
2625 || regno == STACK_POINTER_REGNUM)
2626 bitmap_set_bit (tmp, regno);
2627 }
2628
2629 for (rec = DF_INSN_UID_USES (uid); *rec; rec++)
2630 {
2631 df_ref use = *rec;
2632 unsigned int regno = DF_REF_REGNO (use);
2633
2634 /* When these refs are met for the first time, skip them, as
2635 these uses are just counterparts of some defs. */
2636 if (bitmap_bit_p (tmp, regno))
2637 bitmap_clear_bit (tmp, regno);
2638 else if (! DF_REF_FLAGS_IS_SET (use, DF_REF_CALL_STACK_USAGE))
2639 {
2640 SET_REGNO_REG_SET (IDATA_REG_USES (id), regno);
2641
2642#ifdef STACK_REGS
2643 /* For stack registers, treat reads from them as reads from
2644 the first one to be consistent with sched-deps.c. */
2645 if (IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG))
2646 SET_REGNO_REG_SET (IDATA_REG_USES (id), FIRST_STACK_REG);
2647#endif
2648 }
2649 }
2650
2651 return_regset_to_pool (tmp);
2652}
2653
2654/* Initialize instruction data for INSN in ID using DF's data. */
2655static void
2656init_id_from_df (idata_t id, insn_t insn, bool force_unique_p)
2657{
2658 gcc_assert (DF_INSN_UID_SAFE_GET (INSN_UID (insn)) != NULL);
2659
2660 setup_id_for_insn (id, insn, force_unique_p);
2661 setup_id_lhs_rhs (id, insn, force_unique_p);
2662
2663 if (INSN_NOP_P (insn))
2664 return;
2665
2666 maybe_downgrade_id_to_use (id, insn);
2667 setup_id_reg_sets (id, insn);
2668}
2669
2670/* Initialize instruction data for INSN in ID. */
2671static void
2672deps_init_id (idata_t id, insn_t insn, bool force_unique_p)
2673{
2674 struct deps _dc, *dc = &_dc;
2675
2676 deps_init_id_data.where = DEPS_IN_NOWHERE;
2677 deps_init_id_data.id = id;
2678 deps_init_id_data.force_unique_p = force_unique_p;
2679 deps_init_id_data.force_use_p = false;
2680
4b1e227d 2681 init_deps (dc, false);
c251ad9e
SS
2682
2683 memcpy (&deps_init_id_sched_deps_info,
2684 &const_deps_init_id_sched_deps_info,
2685 sizeof (deps_init_id_sched_deps_info));
2686
2687 if (spec_info != NULL)
2688 deps_init_id_sched_deps_info.generate_spec_deps = 1;
2689
2690 sched_deps_info = &deps_init_id_sched_deps_info;
2691
2692 deps_analyze_insn (dc, insn);
2693
2694 free_deps (dc);
2695
2696 deps_init_id_data.id = NULL;
2697}
2698
2699\f
2700
2701/* Implement hooks for collecting fundamental insn properties like if insn is
2702 an ASM or is within a SCHED_GROUP. */
2703
2704/* True when a "one-time init" data for INSN was already inited. */
2705static bool
2706first_time_insn_init (insn_t insn)
2707{
2708 return INSN_LIVE (insn) == NULL;
2709}
2710
2711/* Hash an entry in a transformed_insns hashtable. */
2712static hashval_t
2713hash_transformed_insns (const void *p)
2714{
2715 return VINSN_HASH_RTX (((const struct transformed_insns *) p)->vinsn_old);
2716}
2717
2718/* Compare the entries in a transformed_insns hashtable. */
2719static int
2720eq_transformed_insns (const void *p, const void *q)
2721{
2722 rtx i1 = VINSN_INSN_RTX (((const struct transformed_insns *) p)->vinsn_old);
2723 rtx i2 = VINSN_INSN_RTX (((const struct transformed_insns *) q)->vinsn_old);
2724
2725 if (INSN_UID (i1) == INSN_UID (i2))
2726 return 1;
2727 return rtx_equal_p (PATTERN (i1), PATTERN (i2));
2728}
2729
2730/* Free an entry in a transformed_insns hashtable. */
2731static void
2732free_transformed_insns (void *p)
2733{
2734 struct transformed_insns *pti = (struct transformed_insns *) p;
2735
2736 vinsn_detach (pti->vinsn_old);
2737 vinsn_detach (pti->vinsn_new);
2738 free (pti);
2739}
2740
2741/* Init the s_i_d data for INSN which should be inited just once, when
2742 we first see the insn. */
2743static void
2744init_first_time_insn_data (insn_t insn)
2745{
2746 /* This should not be set if this is the first time we init data for
2747 insn. */
2748 gcc_assert (first_time_insn_init (insn));
2749
2750 /* These are needed for nops too. */
2751 INSN_LIVE (insn) = get_regset_from_pool ();
2752 INSN_LIVE_VALID_P (insn) = false;
4b1e227d 2753
c251ad9e
SS
2754 if (!INSN_NOP_P (insn))
2755 {
2756 INSN_ANALYZED_DEPS (insn) = BITMAP_ALLOC (NULL);
2757 INSN_FOUND_DEPS (insn) = BITMAP_ALLOC (NULL);
2758 INSN_TRANSFORMED_INSNS (insn)
2759 = htab_create (16, hash_transformed_insns,
2760 eq_transformed_insns, free_transformed_insns);
4b1e227d 2761 init_deps (&INSN_DEPS_CONTEXT (insn), true);
c251ad9e
SS
2762 }
2763}
2764
4b1e227d
SW
2765/* Free almost all above data for INSN that is scheduled already.
2766 Used for extra-large basic blocks. */
2767void
2768free_data_for_scheduled_insn (insn_t insn)
c251ad9e
SS
2769{
2770 gcc_assert (! first_time_insn_init (insn));
2771
4b1e227d
SW
2772 if (! INSN_ANALYZED_DEPS (insn))
2773 return;
2774
c251ad9e
SS
2775 BITMAP_FREE (INSN_ANALYZED_DEPS (insn));
2776 BITMAP_FREE (INSN_FOUND_DEPS (insn));
2777 htab_delete (INSN_TRANSFORMED_INSNS (insn));
c251ad9e
SS
2778
2779 /* This is allocated only for bookkeeping insns. */
2780 if (INSN_ORIGINATORS (insn))
2781 BITMAP_FREE (INSN_ORIGINATORS (insn));
2782 free_deps (&INSN_DEPS_CONTEXT (insn));
4b1e227d
SW
2783
2784 INSN_ANALYZED_DEPS (insn) = NULL;
2785
2786 /* Clear the readonly flag so we would ICE when trying to recalculate
2787 the deps context (as we believe that it should not happen). */
2788 (&INSN_DEPS_CONTEXT (insn))->readonly = 0;
2789}
2790
2791/* Free the same data as above for INSN. */
2792static void
2793free_first_time_insn_data (insn_t insn)
2794{
2795 gcc_assert (! first_time_insn_init (insn));
2796
2797 free_data_for_scheduled_insn (insn);
2798 return_regset_to_pool (INSN_LIVE (insn));
2799 INSN_LIVE (insn) = NULL;
2800 INSN_LIVE_VALID_P (insn) = false;
c251ad9e
SS
2801}
2802
2803/* Initialize region-scope data structures for basic blocks. */
2804static void
2805init_global_and_expr_for_bb (basic_block bb)
2806{
2807 if (sel_bb_empty_p (bb))
2808 return;
2809
2810 invalidate_av_set (bb);
2811}
2812
2813/* Data for global dependency analysis (to initialize CANT_MOVE and
2814 SCHED_GROUP_P). */
2815static struct
2816{
2817 /* Previous insn. */
2818 insn_t prev_insn;
2819} init_global_data;
2820
2821/* Determine if INSN is in the sched_group, is an asm or should not be
2822 cloned. After that initialize its expr. */
2823static void
2824init_global_and_expr_for_insn (insn_t insn)
2825{
2826 if (LABEL_P (insn))
2827 return;
2828
2829 if (NOTE_INSN_BASIC_BLOCK_P (insn))
2830 {
2831 init_global_data.prev_insn = NULL_RTX;
2832 return;
2833 }
2834
2835 gcc_assert (INSN_P (insn));
2836
2837 if (SCHED_GROUP_P (insn))
2838 /* Setup a sched_group. */
2839 {
2840 insn_t prev_insn = init_global_data.prev_insn;
2841
2842 if (prev_insn)
2843 INSN_SCHED_NEXT (prev_insn) = insn;
2844
2845 init_global_data.prev_insn = insn;
2846 }
2847 else
2848 init_global_data.prev_insn = NULL_RTX;
2849
2850 if (GET_CODE (PATTERN (insn)) == ASM_INPUT
2851 || asm_noperands (PATTERN (insn)) >= 0)
2852 /* Mark INSN as an asm. */
2853 INSN_ASM_P (insn) = true;
2854
2855 {
2856 bool force_unique_p;
2857 ds_t spec_done_ds;
2858
2859 /* Certain instructions cannot be cloned. */
2860 if (CANT_MOVE (insn)
2861 || INSN_ASM_P (insn)
2862 || SCHED_GROUP_P (insn)
2863 || prologue_epilogue_contains (insn)
2864 /* Exception handling insns are always unique. */
2865 || (flag_non_call_exceptions && can_throw_internal (insn))
2866 /* TRAP_IF though have an INSN code is control_flow_insn_p (). */
2867 || control_flow_insn_p (insn))
2868 force_unique_p = true;
2869 else
2870 force_unique_p = false;
2871
2872 if (targetm.sched.get_insn_spec_ds)
2873 {
2874 spec_done_ds = targetm.sched.get_insn_spec_ds (insn);
2875 spec_done_ds = ds_get_max_dep_weak (spec_done_ds);
2876 }
2877 else
2878 spec_done_ds = 0;
2879
2880 /* Initialize INSN's expr. */
2881 init_expr (INSN_EXPR (insn), vinsn_create (insn, force_unique_p), 0,
2882 REG_BR_PROB_BASE, INSN_PRIORITY (insn), 0, BLOCK_NUM (insn),
2883 spec_done_ds, 0, 0, NULL, true, false, false, false,
2884 CANT_MOVE (insn));
2885 }
2886
2887 init_first_time_insn_data (insn);
2888}
2889
2890/* Scan the region and initialize instruction data for basic blocks BBS. */
2891void
2892sel_init_global_and_expr (bb_vec_t bbs)
2893{
2894 /* ??? It would be nice to implement push / pop scheme for sched_infos. */
2895 const struct sched_scan_info_def ssi =
2896 {
2897 NULL, /* extend_bb */
2898 init_global_and_expr_for_bb, /* init_bb */
2899 extend_insn_data, /* extend_insn */
2900 init_global_and_expr_for_insn /* init_insn */
2901 };
2902
2903 sched_scan (&ssi, bbs, NULL, NULL, NULL);
2904}
2905
2906/* Finalize region-scope data structures for basic blocks. */
2907static void
2908finish_global_and_expr_for_bb (basic_block bb)
2909{
2910 av_set_clear (&BB_AV_SET (bb));
2911 BB_AV_LEVEL (bb) = 0;
2912}
2913
2914/* Finalize INSN's data. */
2915static void
2916finish_global_and_expr_insn (insn_t insn)
2917{
2918 if (LABEL_P (insn) || NOTE_INSN_BASIC_BLOCK_P (insn))
2919 return;
2920
2921 gcc_assert (INSN_P (insn));
2922
2923 if (INSN_LUID (insn) > 0)
2924 {
2925 free_first_time_insn_data (insn);
2926 INSN_WS_LEVEL (insn) = 0;
2927 CANT_MOVE (insn) = 0;
2928
2929 /* We can no longer assert this, as vinsns of this insn could be
2930 easily live in other insn's caches. This should be changed to
2931 a counter-like approach among all vinsns. */
2932 gcc_assert (true || VINSN_COUNT (INSN_VINSN (insn)) == 1);
2933 clear_expr (INSN_EXPR (insn));
2934 }
2935}
2936
2937/* Finalize per instruction data for the whole region. */
2938void
2939sel_finish_global_and_expr (void)
2940{
2941 {
2942 bb_vec_t bbs;
2943 int i;
2944
2945 bbs = VEC_alloc (basic_block, heap, current_nr_blocks);
2946
2947 for (i = 0; i < current_nr_blocks; i++)
2948 VEC_quick_push (basic_block, bbs, BASIC_BLOCK (BB_TO_BLOCK (i)));
2949
2950 /* Clear AV_SETs and INSN_EXPRs. */
2951 {
2952 const struct sched_scan_info_def ssi =
2953 {
2954 NULL, /* extend_bb */
2955 finish_global_and_expr_for_bb, /* init_bb */
2956 NULL, /* extend_insn */
2957 finish_global_and_expr_insn /* init_insn */
2958 };
2959
2960 sched_scan (&ssi, bbs, NULL, NULL, NULL);
2961 }
2962
2963 VEC_free (basic_block, heap, bbs);
2964 }
2965
2966 finish_insns ();
2967}
2968\f
2969
2970/* In the below hooks, we merely calculate whether or not a dependence
2971 exists, and in what part of insn. However, we will need more data
2972 when we'll start caching dependence requests. */
2973
2974/* Container to hold information for dependency analysis. */
2975static struct
2976{
2977 deps_t dc;
2978
2979 /* A variable to track which part of rtx we are scanning in
2980 sched-deps.c: sched_analyze_insn (). */
2981 deps_where_t where;
2982
2983 /* Current producer. */
2984 insn_t pro;
2985
2986 /* Current consumer. */
2987 vinsn_t con;
2988
2989 /* Is SEL_DEPS_HAS_DEP_P[DEPS_IN_X] is true, then X has a dependence.
2990 X is from { INSN, LHS, RHS }. */
2991 ds_t has_dep_p[DEPS_IN_NOWHERE];
2992} has_dependence_data;
2993
2994/* Start analyzing dependencies of INSN. */
2995static void
2996has_dependence_start_insn (insn_t insn ATTRIBUTE_UNUSED)
2997{
2998 gcc_assert (has_dependence_data.where == DEPS_IN_NOWHERE);
2999
3000 has_dependence_data.where = DEPS_IN_INSN;
3001}
3002
3003/* Finish analyzing dependencies of an insn. */
3004static void
3005has_dependence_finish_insn (void)
3006{
3007 gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
3008
3009 has_dependence_data.where = DEPS_IN_NOWHERE;
3010}
3011
3012/* Start analyzing dependencies of LHS. */
3013static void
3014has_dependence_start_lhs (rtx lhs ATTRIBUTE_UNUSED)
3015{
3016 gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
3017
3018 if (VINSN_LHS (has_dependence_data.con) != NULL)
3019 has_dependence_data.where = DEPS_IN_LHS;
3020}
3021
3022/* Finish analyzing dependencies of an lhs. */
3023static void
3024has_dependence_finish_lhs (void)
3025{
3026 has_dependence_data.where = DEPS_IN_INSN;
3027}
3028
3029/* Start analyzing dependencies of RHS. */
3030static void
3031has_dependence_start_rhs (rtx rhs ATTRIBUTE_UNUSED)
3032{
3033 gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
3034
3035 if (VINSN_RHS (has_dependence_data.con) != NULL)
3036 has_dependence_data.where = DEPS_IN_RHS;
3037}
3038
3039/* Start analyzing dependencies of an rhs. */
3040static void
3041has_dependence_finish_rhs (void)
3042{
3043 gcc_assert (has_dependence_data.where == DEPS_IN_RHS
3044 || has_dependence_data.where == DEPS_IN_INSN);
3045
3046 has_dependence_data.where = DEPS_IN_INSN;
3047}
3048
3049/* Note a set of REGNO. */
3050static void
3051has_dependence_note_reg_set (int regno)
3052{
3053 struct deps_reg *reg_last = &has_dependence_data.dc->reg_last[regno];
3054
3055 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3056 VINSN_INSN_RTX
3057 (has_dependence_data.con)))
3058 {
3059 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3060
3061 if (reg_last->sets != NULL
3062 || reg_last->clobbers != NULL)
3063 *dsp = (*dsp & ~SPECULATIVE) | DEP_OUTPUT;
3064
3065 if (reg_last->uses)
3066 *dsp = (*dsp & ~SPECULATIVE) | DEP_ANTI;
3067 }
3068}
3069
3070/* Note a clobber of REGNO. */
3071static void
3072has_dependence_note_reg_clobber (int regno)
3073{
3074 struct deps_reg *reg_last = &has_dependence_data.dc->reg_last[regno];
3075
3076 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3077 VINSN_INSN_RTX
3078 (has_dependence_data.con)))
3079 {
3080 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3081
3082 if (reg_last->sets)
3083 *dsp = (*dsp & ~SPECULATIVE) | DEP_OUTPUT;
3084
3085 if (reg_last->uses)
3086 *dsp = (*dsp & ~SPECULATIVE) | DEP_ANTI;
3087 }
3088}
3089
3090/* Note a use of REGNO. */
3091static void
3092has_dependence_note_reg_use (int regno)
3093{
3094 struct deps_reg *reg_last = &has_dependence_data.dc->reg_last[regno];
3095
3096 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3097 VINSN_INSN_RTX
3098 (has_dependence_data.con)))
3099 {
3100 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3101
3102 if (reg_last->sets)
3103 *dsp = (*dsp & ~SPECULATIVE) | DEP_TRUE;
3104
3105 if (reg_last->clobbers)
3106 *dsp = (*dsp & ~SPECULATIVE) | DEP_ANTI;
3107
3108 /* Handle BE_IN_SPEC. */
3109 if (reg_last->uses)
3110 {
3111 ds_t pro_spec_checked_ds;
3112
3113 pro_spec_checked_ds = INSN_SPEC_CHECKED_DS (has_dependence_data.pro);
3114 pro_spec_checked_ds = ds_get_max_dep_weak (pro_spec_checked_ds);
3115
3116 if (pro_spec_checked_ds != 0)
3117 /* Merge BE_IN_SPEC bits into *DSP. */
3118 *dsp = ds_full_merge (*dsp, pro_spec_checked_ds,
3119 NULL_RTX, NULL_RTX);
3120 }
3121 }
3122}
3123
3124/* Note a memory dependence. */
3125static void
3126has_dependence_note_mem_dep (rtx mem ATTRIBUTE_UNUSED,
3127 rtx pending_mem ATTRIBUTE_UNUSED,
3128 insn_t pending_insn ATTRIBUTE_UNUSED,
3129 ds_t ds ATTRIBUTE_UNUSED)
3130{
3131 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3132 VINSN_INSN_RTX (has_dependence_data.con)))
3133 {
3134 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3135
3136 *dsp = ds_full_merge (ds, *dsp, pending_mem, mem);
3137 }
3138}
3139
3140/* Note a dependence. */
3141static void
3142has_dependence_note_dep (insn_t pro ATTRIBUTE_UNUSED,
3143 ds_t ds ATTRIBUTE_UNUSED)
3144{
3145 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3146 VINSN_INSN_RTX (has_dependence_data.con)))
3147 {
3148 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3149
3150 *dsp = ds_full_merge (ds, *dsp, NULL_RTX, NULL_RTX);
3151 }
3152}
3153
3154/* Mark the insn as having a hard dependence that prevents speculation. */
3155void
3156sel_mark_hard_insn (rtx insn)
3157{
3158 int i;
3159
3160 /* Only work when we're in has_dependence_p mode.
3161 ??? This is a hack, this should actually be a hook. */
3162 if (!has_dependence_data.dc || !has_dependence_data.pro)
3163 return;
3164
3165 gcc_assert (insn == VINSN_INSN_RTX (has_dependence_data.con));
3166 gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
3167
3168 for (i = 0; i < DEPS_IN_NOWHERE; i++)
3169 has_dependence_data.has_dep_p[i] &= ~SPECULATIVE;
3170}
3171
3172/* This structure holds the hooks for the dependency analysis used when
3173 actually processing dependencies in the scheduler. */
3174static struct sched_deps_info_def has_dependence_sched_deps_info;
3175
3176/* This initializes most of the fields of the above structure. */
3177static const struct sched_deps_info_def const_has_dependence_sched_deps_info =
3178 {
3179 NULL,
3180
3181 has_dependence_start_insn,
3182 has_dependence_finish_insn,
3183 has_dependence_start_lhs,
3184 has_dependence_finish_lhs,
3185 has_dependence_start_rhs,
3186 has_dependence_finish_rhs,
3187 has_dependence_note_reg_set,
3188 has_dependence_note_reg_clobber,
3189 has_dependence_note_reg_use,
3190 has_dependence_note_mem_dep,
3191 has_dependence_note_dep,
3192
3193 0, /* use_cselib */
3194 0, /* use_deps_list */
3195 0 /* generate_spec_deps */
3196 };
3197
3198/* Initialize has_dependence_sched_deps_info with extra spec field. */
3199static void
3200setup_has_dependence_sched_deps_info (void)
3201{
3202 memcpy (&has_dependence_sched_deps_info,
3203 &const_has_dependence_sched_deps_info,
3204 sizeof (has_dependence_sched_deps_info));
3205
3206 if (spec_info != NULL)
3207 has_dependence_sched_deps_info.generate_spec_deps = 1;
3208
3209 sched_deps_info = &has_dependence_sched_deps_info;
3210}
3211
3212/* Remove all dependences found and recorded in has_dependence_data array. */
3213void
3214sel_clear_has_dependence (void)
3215{
3216 int i;
3217
3218 for (i = 0; i < DEPS_IN_NOWHERE; i++)
3219 has_dependence_data.has_dep_p[i] = 0;
3220}
3221
3222/* Return nonzero if EXPR has is dependent upon PRED. Return the pointer
3223 to the dependence information array in HAS_DEP_PP. */
3224ds_t
3225has_dependence_p (expr_t expr, insn_t pred, ds_t **has_dep_pp)
3226{
3227 int i;
3228 ds_t ds;
3229 struct deps *dc;
3230
3231 if (INSN_SIMPLEJUMP_P (pred))
3232 /* Unconditional jump is just a transfer of control flow.
3233 Ignore it. */
3234 return false;
3235
3236 dc = &INSN_DEPS_CONTEXT (pred);
4b1e227d
SW
3237
3238 /* We init this field lazily. */
3239 if (dc->reg_last == NULL)
3240 init_deps_reg_last (dc);
3241
c251ad9e
SS
3242 if (!dc->readonly)
3243 {
3244 has_dependence_data.pro = NULL;
3245 /* Initialize empty dep context with information about PRED. */
3246 advance_deps_context (dc, pred);
3247 dc->readonly = 1;
3248 }
3249
3250 has_dependence_data.where = DEPS_IN_NOWHERE;
3251 has_dependence_data.pro = pred;
3252 has_dependence_data.con = EXPR_VINSN (expr);
3253 has_dependence_data.dc = dc;
3254
3255 sel_clear_has_dependence ();
3256
3257 /* Now catch all dependencies that would be generated between PRED and
3258 INSN. */
3259 setup_has_dependence_sched_deps_info ();
3260 deps_analyze_insn (dc, EXPR_INSN_RTX (expr));
3261 has_dependence_data.dc = NULL;
3262
3263 /* When a barrier was found, set DEPS_IN_INSN bits. */
3264 if (dc->last_reg_pending_barrier == TRUE_BARRIER)
3265 has_dependence_data.has_dep_p[DEPS_IN_INSN] = DEP_TRUE;
3266 else if (dc->last_reg_pending_barrier == MOVE_BARRIER)
3267 has_dependence_data.has_dep_p[DEPS_IN_INSN] = DEP_ANTI;
3268
3269 /* Do not allow stores to memory to move through checks. Currently
3270 we don't move this to sched-deps.c as the check doesn't have
3271 obvious places to which this dependence can be attached.
3272 FIMXE: this should go to a hook. */
3273 if (EXPR_LHS (expr)
3274 && MEM_P (EXPR_LHS (expr))
3275 && sel_insn_is_speculation_check (pred))
3276 has_dependence_data.has_dep_p[DEPS_IN_INSN] = DEP_ANTI;
3277
3278 *has_dep_pp = has_dependence_data.has_dep_p;
3279 ds = 0;
3280 for (i = 0; i < DEPS_IN_NOWHERE; i++)
3281 ds = ds_full_merge (ds, has_dependence_data.has_dep_p[i],
3282 NULL_RTX, NULL_RTX);
3283
3284 return ds;
3285}
3286\f
3287
3288/* Dependence hooks implementation that checks dependence latency constraints
3289 on the insns being scheduled. The entry point for these routines is
3290 tick_check_p predicate. */
3291
3292static struct
3293{
3294 /* An expr we are currently checking. */
3295 expr_t expr;
3296
3297 /* A minimal cycle for its scheduling. */
3298 int cycle;
3299
3300 /* Whether we have seen a true dependence while checking. */
3301 bool seen_true_dep_p;
3302} tick_check_data;
3303
3304/* Update minimal scheduling cycle for tick_check_insn given that it depends
3305 on PRO with status DS and weight DW. */
3306static void
3307tick_check_dep_with_dw (insn_t pro_insn, ds_t ds, dw_t dw)
3308{
3309 expr_t con_expr = tick_check_data.expr;
3310 insn_t con_insn = EXPR_INSN_RTX (con_expr);
3311
3312 if (con_insn != pro_insn)
3313 {
3314 enum reg_note dt;
3315 int tick;
3316
3317 if (/* PROducer was removed from above due to pipelining. */
3318 !INSN_IN_STREAM_P (pro_insn)
3319 /* Or PROducer was originally on the next iteration regarding the
3320 CONsumer. */
3321 || (INSN_SCHED_TIMES (pro_insn)
3322 - EXPR_SCHED_TIMES (con_expr)) > 1)
3323 /* Don't count this dependence. */
3324 return;
3325
3326 dt = ds_to_dt (ds);
3327 if (dt == REG_DEP_TRUE)
3328 tick_check_data.seen_true_dep_p = true;
3329
3330 gcc_assert (INSN_SCHED_CYCLE (pro_insn) > 0);
3331
3332 {
3333 dep_def _dep, *dep = &_dep;
3334
3335 init_dep (dep, pro_insn, con_insn, dt);
3336
3337 tick = INSN_SCHED_CYCLE (pro_insn) + dep_cost_1 (dep, dw);
3338 }
3339
3340 /* When there are several kinds of dependencies between pro and con,
3341 only REG_DEP_TRUE should be taken into account. */
3342 if (tick > tick_check_data.cycle
3343 && (dt == REG_DEP_TRUE || !tick_check_data.seen_true_dep_p))
3344 tick_check_data.cycle = tick;
3345 }
3346}
3347
3348/* An implementation of note_dep hook. */
3349static void
3350tick_check_note_dep (insn_t pro, ds_t ds)
3351{
3352 tick_check_dep_with_dw (pro, ds, 0);
3353}
3354
3355/* An implementation of note_mem_dep hook. */
3356static void
3357tick_check_note_mem_dep (rtx mem1, rtx mem2, insn_t pro, ds_t ds)
3358{
3359 dw_t dw;
3360
3361 dw = (ds_to_dt (ds) == REG_DEP_TRUE
3362 ? estimate_dep_weak (mem1, mem2)
3363 : 0);
3364
3365 tick_check_dep_with_dw (pro, ds, dw);
3366}
3367
3368/* This structure contains hooks for dependence analysis used when determining
3369 whether an insn is ready for scheduling. */
3370static struct sched_deps_info_def tick_check_sched_deps_info =
3371 {
3372 NULL,
3373
3374 NULL,
3375 NULL,
3376 NULL,
3377 NULL,
3378 NULL,
3379 NULL,
3380 haifa_note_reg_set,
3381 haifa_note_reg_clobber,
3382 haifa_note_reg_use,
3383 tick_check_note_mem_dep,
3384 tick_check_note_dep,
3385
3386 0, 0, 0
3387 };
3388
3389/* Estimate number of cycles from the current cycle of FENCE until EXPR can be
3390 scheduled. Return 0 if all data from producers in DC is ready. */
3391int
3392tick_check_p (expr_t expr, deps_t dc, fence_t fence)
3393{
3394 int cycles_left;
3395 /* Initialize variables. */
3396 tick_check_data.expr = expr;
3397 tick_check_data.cycle = 0;
3398 tick_check_data.seen_true_dep_p = false;
3399 sched_deps_info = &tick_check_sched_deps_info;
3400
3401 gcc_assert (!dc->readonly);
3402 dc->readonly = 1;
3403 deps_analyze_insn (dc, EXPR_INSN_RTX (expr));
3404 dc->readonly = 0;
3405
3406 cycles_left = tick_check_data.cycle - FENCE_CYCLE (fence);
3407
3408 return cycles_left >= 0 ? cycles_left : 0;
3409}
3410\f
3411
3412/* Functions to work with insns. */
3413
3414/* Returns true if LHS of INSN is the same as DEST of an insn
3415 being moved. */
3416bool
3417lhs_of_insn_equals_to_dest_p (insn_t insn, rtx dest)
3418{
3419 rtx lhs = INSN_LHS (insn);
3420
3421 if (lhs == NULL || dest == NULL)
3422 return false;
3423
3424 return rtx_equal_p (lhs, dest);
3425}
3426
3427/* Return s_i_d entry of INSN. Callable from debugger. */
3428sel_insn_data_def
3429insn_sid (insn_t insn)
3430{
3431 return *SID (insn);
3432}
3433
3434/* True when INSN is a speculative check. We can tell this by looking
3435 at the data structures of the selective scheduler, not by examining
3436 the pattern. */
3437bool
3438sel_insn_is_speculation_check (rtx insn)
3439{
3440 return s_i_d && !! INSN_SPEC_CHECKED_DS (insn);
3441}
3442
3443/* Extracts machine mode MODE and destination location DST_LOC
3444 for given INSN. */
3445void
3446get_dest_and_mode (rtx insn, rtx *dst_loc, enum machine_mode *mode)
3447{
3448 rtx pat = PATTERN (insn);
3449
3450 gcc_assert (dst_loc);
3451 gcc_assert (GET_CODE (pat) == SET);
3452
3453 *dst_loc = SET_DEST (pat);
3454
3455 gcc_assert (*dst_loc);
3456 gcc_assert (MEM_P (*dst_loc) || REG_P (*dst_loc));
3457
3458 if (mode)
3459 *mode = GET_MODE (*dst_loc);
3460}
3461
3462/* Returns true when moving through JUMP will result in bookkeeping
3463 creation. */
3464bool
3465bookkeeping_can_be_created_if_moved_through_p (insn_t jump)
3466{
3467 insn_t succ;
3468 succ_iterator si;
3469
3470 FOR_EACH_SUCC (succ, si, jump)
3471 if (sel_num_cfg_preds_gt_1 (succ))
3472 return true;
3473
3474 return false;
3475}
3476
3477/* Return 'true' if INSN is the only one in its basic block. */
3478static bool
3479insn_is_the_only_one_in_bb_p (insn_t insn)
3480{
3481 return sel_bb_head_p (insn) && sel_bb_end_p (insn);
3482}
3483
3484#ifdef ENABLE_CHECKING
3485/* Check that the region we're scheduling still has at most one
3486 backedge. */
3487static void
3488verify_backedges (void)
3489{
3490 if (pipelining_p)
3491 {
3492 int i, n = 0;
3493 edge e;
3494 edge_iterator ei;
3495
3496 for (i = 0; i < current_nr_blocks; i++)
3497 FOR_EACH_EDGE (e, ei, BASIC_BLOCK (BB_TO_BLOCK (i))->succs)
3498 if (in_current_region_p (e->dest)
3499 && BLOCK_TO_BB (e->dest->index) < i)
3500 n++;
3501
3502 gcc_assert (n <= 1);
3503 }
3504}
3505#endif
3506\f
3507
3508/* Functions to work with control flow. */
3509
4b1e227d
SW
3510/* Recompute BLOCK_TO_BB and BB_FOR_BLOCK for current region so that blocks
3511 are sorted in topological order (it might have been invalidated by
3512 redirecting an edge). */
3513static void
3514sel_recompute_toporder (void)
3515{
3516 int i, n, rgn;
3517 int *postorder, n_blocks;
3518
3519 postorder = XALLOCAVEC (int, n_basic_blocks);
3520 n_blocks = post_order_compute (postorder, false, false);
3521
3522 rgn = CONTAINING_RGN (BB_TO_BLOCK (0));
3523 for (n = 0, i = n_blocks - 1; i >= 0; i--)
3524 if (CONTAINING_RGN (postorder[i]) == rgn)
3525 {
3526 BLOCK_TO_BB (postorder[i]) = n;
3527 BB_TO_BLOCK (n) = postorder[i];
3528 n++;
3529 }
3530
3531 /* Assert that we updated info for all blocks. We may miss some blocks if
3532 this function is called when redirecting an edge made a block
3533 unreachable, but that block is not deleted yet. */
3534 gcc_assert (n == RGN_NR_BLOCKS (rgn));
3535}
3536
c251ad9e 3537/* Tidy the possibly empty block BB. */
4b1e227d
SW
3538static bool
3539maybe_tidy_empty_bb (basic_block bb, bool recompute_toporder_p)
c251ad9e
SS
3540{
3541 basic_block succ_bb, pred_bb;
4b1e227d
SW
3542 edge e;
3543 edge_iterator ei;
c251ad9e
SS
3544 bool rescan_p;
3545
3546 /* Keep empty bb only if this block immediately precedes EXIT and
4b1e227d
SW
3547 has incoming non-fallthrough edge, or it has no predecessors or
3548 successors. Otherwise remove it. */
3549 if (!sel_bb_empty_p (bb)
3550 || (single_succ_p (bb)
c251ad9e 3551 && single_succ (bb) == EXIT_BLOCK_PTR
4b1e227d
SW
3552 && (!single_pred_p (bb)
3553 || !(single_pred_edge (bb)->flags & EDGE_FALLTHRU)))
3554 || EDGE_COUNT (bb->preds) == 0
3555 || EDGE_COUNT (bb->succs) == 0)
c251ad9e
SS
3556 return false;
3557
4b1e227d
SW
3558 /* Do not attempt to redirect complex edges. */
3559 FOR_EACH_EDGE (e, ei, bb->preds)
3560 if (e->flags & EDGE_COMPLEX)
3561 return false;
3562
c251ad9e
SS
3563 free_data_sets (bb);
3564
3565 /* Do not delete BB if it has more than one successor.
3566 That can occur when we moving a jump. */
3567 if (!single_succ_p (bb))
3568 {
3569 gcc_assert (can_merge_blocks_p (bb->prev_bb, bb));
3570 sel_merge_blocks (bb->prev_bb, bb);
3571 return true;
3572 }
3573
3574 succ_bb = single_succ (bb);
3575 rescan_p = true;
3576 pred_bb = NULL;
3577
3578 /* Redirect all non-fallthru edges to the next bb. */
3579 while (rescan_p)
3580 {
c251ad9e
SS
3581 rescan_p = false;
3582
3583 FOR_EACH_EDGE (e, ei, bb->preds)
3584 {
3585 pred_bb = e->src;
3586
3587 if (!(e->flags & EDGE_FALLTHRU))
3588 {
4b1e227d 3589 recompute_toporder_p |= sel_redirect_edge_and_branch (e, succ_bb);
c251ad9e
SS
3590 rescan_p = true;
3591 break;
3592 }
3593 }
3594 }
3595
3596 /* If it is possible - merge BB with its predecessor. */
3597 if (can_merge_blocks_p (bb->prev_bb, bb))
3598 sel_merge_blocks (bb->prev_bb, bb);
3599 else
3600 /* Otherwise this is a block without fallthru predecessor.
3601 Just delete it. */
3602 {
3603 gcc_assert (pred_bb != NULL);
3604
4b1e227d
SW
3605 if (in_current_region_p (pred_bb))
3606 move_bb_info (pred_bb, bb);
c251ad9e
SS
3607 remove_empty_bb (bb, true);
3608 }
3609
4b1e227d
SW
3610 if (recompute_toporder_p)
3611 sel_recompute_toporder ();
3612
c251ad9e
SS
3613#ifdef ENABLE_CHECKING
3614 verify_backedges ();
3615#endif
3616
3617 return true;
3618}
3619
3620/* Tidy the control flow after we have removed original insn from
3621 XBB. Return true if we have removed some blocks. When FULL_TIDYING
3622 is true, also try to optimize control flow on non-empty blocks. */
3623bool
3624tidy_control_flow (basic_block xbb, bool full_tidying)
3625{
3626 bool changed = true;
3627
3628 /* First check whether XBB is empty. */
4b1e227d 3629 changed = maybe_tidy_empty_bb (xbb, false);
c251ad9e
SS
3630 if (changed || !full_tidying)
3631 return changed;
3632
3633 /* Check if there is a unnecessary jump after insn left. */
3634 if (jump_leads_only_to_bb_p (BB_END (xbb), xbb->next_bb)
3635 && INSN_SCHED_TIMES (BB_END (xbb)) == 0
3636 && !IN_CURRENT_FENCE_P (BB_END (xbb)))
3637 {
3638 if (sel_remove_insn (BB_END (xbb), false, false))
3639 return true;
3640 tidy_fallthru_edge (EDGE_SUCC (xbb, 0));
3641 }
3642
3643 /* Check if there is an unnecessary jump in previous basic block leading
3644 to next basic block left after removing INSN from stream.
3645 If it is so, remove that jump and redirect edge to current
3646 basic block (where there was INSN before deletion). This way
3647 when NOP will be deleted several instructions later with its
3648 basic block we will not get a jump to next instruction, which
3649 can be harmful. */
3650 if (sel_bb_head (xbb) == sel_bb_end (xbb)
3651 && !sel_bb_empty_p (xbb)
3652 && INSN_NOP_P (sel_bb_end (xbb))
3653 /* Flow goes fallthru from current block to the next. */
3654 && EDGE_COUNT (xbb->succs) == 1
3655 && (EDGE_SUCC (xbb, 0)->flags & EDGE_FALLTHRU)
3656 /* When successor is an EXIT block, it may not be the next block. */
3657 && single_succ (xbb) != EXIT_BLOCK_PTR
3658 /* And unconditional jump in previous basic block leads to
3659 next basic block of XBB and this jump can be safely removed. */
3660 && in_current_region_p (xbb->prev_bb)
3661 && jump_leads_only_to_bb_p (BB_END (xbb->prev_bb), xbb->next_bb)
3662 && INSN_SCHED_TIMES (BB_END (xbb->prev_bb)) == 0
3663 /* Also this jump is not at the scheduling boundary. */
3664 && !IN_CURRENT_FENCE_P (BB_END (xbb->prev_bb)))
3665 {
4b1e227d 3666 bool recompute_toporder_p;
c251ad9e
SS
3667 /* Clear data structures of jump - jump itself will be removed
3668 by sel_redirect_edge_and_branch. */
3669 clear_expr (INSN_EXPR (BB_END (xbb->prev_bb)));
4b1e227d
SW
3670 recompute_toporder_p
3671 = sel_redirect_edge_and_branch (EDGE_SUCC (xbb->prev_bb, 0), xbb);
3672
c251ad9e
SS
3673 gcc_assert (EDGE_SUCC (xbb->prev_bb, 0)->flags & EDGE_FALLTHRU);
3674
3675 /* It can turn out that after removing unused jump, basic block
3676 that contained that jump, becomes empty too. In such case
3677 remove it too. */
3678 if (sel_bb_empty_p (xbb->prev_bb))
4b1e227d
SW
3679 changed = maybe_tidy_empty_bb (xbb->prev_bb, recompute_toporder_p);
3680 else if (recompute_toporder_p)
3681 sel_recompute_toporder ();
c251ad9e
SS
3682 }
3683
3684 return changed;
3685}
3686
4b1e227d
SW
3687/* Purge meaningless empty blocks in the middle of a region. */
3688void
3689purge_empty_blocks (void)
3690{
3691 /* Do not attempt to delete preheader. */
3692 int i = sel_is_loop_preheader_p (BASIC_BLOCK (BB_TO_BLOCK (0))) ? 1 : 0;
3693
3694 while (i < current_nr_blocks)
3695 {
3696 basic_block b = BASIC_BLOCK (BB_TO_BLOCK (i));
3697
3698 if (maybe_tidy_empty_bb (b, false))
3699 continue;
3700
3701 i++;
3702 }
3703}
3704
3705/* Rip-off INSN from the insn stream. When ONLY_DISCONNECT is true,
3706 do not delete insn's data, because it will be later re-emitted.
c251ad9e
SS
3707 Return true if we have removed some blocks afterwards. */
3708bool
3709sel_remove_insn (insn_t insn, bool only_disconnect, bool full_tidying)
3710{
3711 basic_block bb = BLOCK_FOR_INSN (insn);
3712
3713 gcc_assert (INSN_IN_STREAM_P (insn));
3714
3715 if (only_disconnect)
3716 {
3717 insn_t prev = PREV_INSN (insn);
3718 insn_t next = NEXT_INSN (insn);
3719 basic_block bb = BLOCK_FOR_INSN (insn);
3720
3721 NEXT_INSN (prev) = next;
3722 PREV_INSN (next) = prev;
3723
3724 if (BB_HEAD (bb) == insn)
3725 {
3726 gcc_assert (BLOCK_FOR_INSN (prev) == bb);
3727 BB_HEAD (bb) = prev;
3728 }
3729 if (BB_END (bb) == insn)
3730 BB_END (bb) = prev;
3731 }
3732 else
3733 {
3734 remove_insn (insn);
3735 clear_expr (INSN_EXPR (insn));
3736 }
3737
3738 /* It is necessary to null this fields before calling add_insn (). */
3739 PREV_INSN (insn) = NULL_RTX;
3740 NEXT_INSN (insn) = NULL_RTX;
3741
3742 return tidy_control_flow (bb, full_tidying);
3743}
3744
3745/* Estimate number of the insns in BB. */
3746static int
3747sel_estimate_number_of_insns (basic_block bb)
3748{
3749 int res = 0;
3750 insn_t insn = NEXT_INSN (BB_HEAD (bb)), next_tail = NEXT_INSN (BB_END (bb));
3751
3752 for (; insn != next_tail; insn = NEXT_INSN (insn))
3753 if (INSN_P (insn))
3754 res++;
3755
3756 return res;
3757}
3758
3759/* We don't need separate luids for notes or labels. */
3760static int
3761sel_luid_for_non_insn (rtx x)
3762{
3763 gcc_assert (NOTE_P (x) || LABEL_P (x));
3764
3765 return -1;
3766}
3767
3768/* Return seqno of the only predecessor of INSN. */
3769static int
3770get_seqno_of_a_pred (insn_t insn)
3771{
3772 int seqno;
3773
3774 gcc_assert (INSN_SIMPLEJUMP_P (insn));
3775
3776 if (!sel_bb_head_p (insn))
3777 seqno = INSN_SEQNO (PREV_INSN (insn));
3778 else
3779 {
3780 basic_block bb = BLOCK_FOR_INSN (insn);
3781
3782 if (single_pred_p (bb)
3783 && !in_current_region_p (single_pred (bb)))
3784 {
3785 /* We can have preds outside a region when splitting edges
3786 for pipelining of an outer loop. Use succ instead.
3787 There should be only one of them. */
3788 insn_t succ = NULL;
3789 succ_iterator si;
3790 bool first = true;
3791