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