OSDN Git Service

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