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