Import gcc-4.4.2
[dragonfly.git] / contrib / gcc-4.4 / gcc / sel-sched-ir.h
CommitLineData
c251ad9e
SS
1/* Instruction scheduling pass. This file contains definitions used
2 internally in the scheduler.
3 Copyright (C) 2006, 2007, 2008 Free Software Foundation, Inc.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
21#ifndef GCC_SEL_SCHED_IR_H
22#define GCC_SEL_SCHED_IR_H
23
24/* For state_t. */
25#include "insn-attr.h"
26/* For regset_head. */
27#include "basic-block.h"
28/* For reg_note. */
29#include "rtl.h"
30#include "ggc.h"
31#include "bitmap.h"
32#include "vecprim.h"
33#include "sched-int.h"
34#include "cfgloop.h"
35
36/* tc_t is a short for target context. This is a state of the target
37 backend. */
38typedef void *tc_t;
39
40/* List data types used for av sets, fences, paths, and boundaries. */
41
42/* Forward declarations for types that are part of some list nodes. */
43struct _list_node;
44
45/* List backend. */
46typedef struct _list_node *_list_t;
47#define _LIST_NEXT(L) ((L)->next)
48
49/* Instruction data that is part of vinsn type. */
50struct idata_def;
51typedef struct idata_def *idata_t;
52
53/* A virtual instruction, i.e. an instruction as seen by the scheduler. */
54struct vinsn_def;
55typedef struct vinsn_def *vinsn_t;
56
57/* RTX list.
58 This type is the backend for ilist. */
59typedef _list_t _xlist_t;
60#define _XLIST_X(L) ((L)->u.x)
61#define _XLIST_NEXT(L) (_LIST_NEXT (L))
62
63/* Instruction. */
64typedef rtx insn_t;
65
66/* List of insns. */
67typedef _xlist_t ilist_t;
68#define ILIST_INSN(L) (_XLIST_X (L))
69#define ILIST_NEXT(L) (_XLIST_NEXT (L))
70
71/* This lists possible transformations that done locally, i.e. in
72 moveup_expr. */
73enum local_trans_type
74 {
75 TRANS_SUBSTITUTION,
76 TRANS_SPECULATION
77 };
78
79/* This struct is used to record the history of expression's
80 transformations. */
81struct expr_history_def_1
82{
83 /* UID of the insn. */
84 unsigned uid;
85
86 /* How the expression looked like. */
87 vinsn_t old_expr_vinsn;
88
89 /* How the expression looks after the transformation. */
90 vinsn_t new_expr_vinsn;
91
92 /* And its speculative status. */
93 ds_t spec_ds;
94
95 /* Type of the transformation. */
96 enum local_trans_type type;
97};
98
99typedef struct expr_history_def_1 expr_history_def;
100
101DEF_VEC_O (expr_history_def);
102DEF_VEC_ALLOC_O (expr_history_def, heap);
103
104/* Expression information. */
105struct _expr
106{
107 /* Insn description. */
108 vinsn_t vinsn;
109
110 /* SPEC is the degree of speculativeness.
111 FIXME: now spec is increased when an rhs is moved through a
112 conditional, thus showing only control speculativeness. In the
113 future we'd like to count data spec separately to allow a better
114 control on scheduling. */
115 int spec;
116
117 /* Degree of speculativeness measured as probability of executing
118 instruction's original basic block given relative to
119 the current scheduling point. */
120 int usefulness;
121
122 /* A priority of this expression. */
123 int priority;
124
125 /* A priority adjustment of this expression. */
126 int priority_adj;
127
128 /* Number of times the insn was scheduled. */
129 int sched_times;
130
131 /* A basic block index this was originated from. Zero when there is
132 more than one originator. */
133 int orig_bb_index;
134
135 /* Instruction should be of SPEC_DONE_DS type in order to be moved to this
136 point. */
137 ds_t spec_done_ds;
138
139 /* SPEC_TO_CHECK_DS hold speculation types that should be checked
140 (used only during move_op ()). */
141 ds_t spec_to_check_ds;
142
143 /* Cycle on which original insn was scheduled. Zero when it has not yet
144 been scheduled or more than one originator. */
145 int orig_sched_cycle;
146
147 /* This vector contains the history of insn's transformations. */
148 VEC(expr_history_def, heap) *history_of_changes;
149
150 /* True (1) when original target (register or memory) of this instruction
151 is available for scheduling, false otherwise. -1 means we're not sure;
152 please run find_used_regs to clarify. */
153 signed char target_available;
154
155 /* True when this expression needs a speculation check to be scheduled.
156 This is used during find_used_regs. */
157 BOOL_BITFIELD needs_spec_check_p : 1;
158
159 /* True when the expression was substituted. Used for statistical
160 purposes. */
161 BOOL_BITFIELD was_substituted : 1;
162
163 /* True when the expression was renamed. */
164 BOOL_BITFIELD was_renamed : 1;
165
166 /* True when expression can't be moved. */
167 BOOL_BITFIELD cant_move : 1;
168};
169
170typedef struct _expr expr_def;
171typedef expr_def *expr_t;
172
173#define EXPR_VINSN(EXPR) ((EXPR)->vinsn)
174#define EXPR_INSN_RTX(EXPR) (VINSN_INSN_RTX (EXPR_VINSN (EXPR)))
175#define EXPR_PATTERN(EXPR) (VINSN_PATTERN (EXPR_VINSN (EXPR)))
176#define EXPR_LHS(EXPR) (VINSN_LHS (EXPR_VINSN (EXPR)))
177#define EXPR_RHS(EXPR) (VINSN_RHS (EXPR_VINSN (EXPR)))
178#define EXPR_TYPE(EXPR) (VINSN_TYPE (EXPR_VINSN (EXPR)))
179#define EXPR_SEPARABLE_P(EXPR) (VINSN_SEPARABLE_P (EXPR_VINSN (EXPR)))
180
181#define EXPR_SPEC(EXPR) ((EXPR)->spec)
182#define EXPR_USEFULNESS(EXPR) ((EXPR)->usefulness)
183#define EXPR_PRIORITY(EXPR) ((EXPR)->priority)
184#define EXPR_PRIORITY_ADJ(EXPR) ((EXPR)->priority_adj)
185#define EXPR_SCHED_TIMES(EXPR) ((EXPR)->sched_times)
186#define EXPR_ORIG_BB_INDEX(EXPR) ((EXPR)->orig_bb_index)
187#define EXPR_ORIG_SCHED_CYCLE(EXPR) ((EXPR)->orig_sched_cycle)
188#define EXPR_SPEC_DONE_DS(EXPR) ((EXPR)->spec_done_ds)
189#define EXPR_SPEC_TO_CHECK_DS(EXPR) ((EXPR)->spec_to_check_ds)
190#define EXPR_HISTORY_OF_CHANGES(EXPR) ((EXPR)->history_of_changes)
191#define EXPR_TARGET_AVAILABLE(EXPR) ((EXPR)->target_available)
192#define EXPR_NEEDS_SPEC_CHECK_P(EXPR) ((EXPR)->needs_spec_check_p)
193#define EXPR_WAS_SUBSTITUTED(EXPR) ((EXPR)->was_substituted)
194#define EXPR_WAS_RENAMED(EXPR) ((EXPR)->was_renamed)
195#define EXPR_CANT_MOVE(EXPR) ((EXPR)->cant_move)
196
197#define EXPR_WAS_CHANGED(EXPR) (VEC_length (expr_history_def, \
198 EXPR_HISTORY_OF_CHANGES (EXPR)) > 0)
199
200/* Insn definition for list of original insns in find_used_regs. */
201struct _def
202{
203 insn_t orig_insn;
204
205 /* FIXME: Get rid of CROSSES_CALL in each def, since if we're moving up
206 rhs from two different places, but only one of the code motion paths
207 crosses a call, we can't use any of the call_used_regs, no matter which
208 path or whether all paths crosses a call. Thus we should move CROSSES_CALL
209 to static params. */
210 bool crosses_call;
211};
212typedef struct _def *def_t;
213
214
215/* Availability sets are sets of expressions we're scheduling. */
216typedef _list_t av_set_t;
217#define _AV_SET_EXPR(L) (&(L)->u.expr)
218#define _AV_SET_NEXT(L) (_LIST_NEXT (L))
219
220
221/* Boundary of the current fence group. */
222struct _bnd
223{
224 /* The actual boundary instruction. */
225 insn_t to;
226
227 /* Its path to the fence. */
228 ilist_t ptr;
229
230 /* Availability set at the boundary. */
231 av_set_t av;
232
233 /* This set moved to the fence. */
234 av_set_t av1;
235
236 /* Deps context at this boundary. As long as we have one boundary per fence,
237 this is just a pointer to the same deps context as in the corresponding
238 fence. */
239 deps_t dc;
240};
241typedef struct _bnd *bnd_t;
242#define BND_TO(B) ((B)->to)
243
244/* PTR stands not for pointer as you might think, but as a Path To Root of the
245 current instruction group from boundary B. */
246#define BND_PTR(B) ((B)->ptr)
247#define BND_AV(B) ((B)->av)
248#define BND_AV1(B) ((B)->av1)
249#define BND_DC(B) ((B)->dc)
250
251/* List of boundaries. */
252typedef _list_t blist_t;
253#define BLIST_BND(L) (&(L)->u.bnd)
254#define BLIST_NEXT(L) (_LIST_NEXT (L))
255
256
257/* Fence information. A fence represents current scheduling point and also
258 blocks code motion through it when pipelining. */
259struct _fence
260{
261 /* Insn before which we gather an instruction group.*/
262 insn_t insn;
263
264 /* Modeled state of the processor pipeline. */
265 state_t state;
266
267 /* Current cycle that is being scheduled on this fence. */
268 int cycle;
269
270 /* Number of insns that were scheduled on the current cycle.
271 This information has to be local to a fence. */
272 int cycle_issued_insns;
273
274 /* At the end of fill_insns () this field holds the list of the instructions
275 that are inner boundaries of the scheduled parallel group. */
276 ilist_t bnds;
277
278 /* Deps context at this fence. It is used to model dependencies at the
279 fence so that insn ticks can be properly evaluated. */
280 deps_t dc;
281
282 /* Target context at this fence. Used to save and load any local target
283 scheduling information when changing fences. */
284 tc_t tc;
285
286 /* A vector of insns that are scheduled but not yet completed. */
287 VEC (rtx,gc) *executing_insns;
288
289 /* A vector indexed by UIDs that caches the earliest cycle on which
290 an insn can be scheduled on this fence. */
291 int *ready_ticks;
292
293 /* Its size. */
294 int ready_ticks_size;
295
296 /* Insn, which has been scheduled last on this fence. */
297 rtx last_scheduled_insn;
298
299 /* If non-NULL force the next scheduled insn to be SCHED_NEXT. */
300 rtx sched_next;
301
302 /* True if fill_insns processed this fence. */
303 BOOL_BITFIELD processed_p : 1;
304
305 /* True if fill_insns actually scheduled something on this fence. */
306 BOOL_BITFIELD scheduled_p : 1;
307
308 /* True when the next insn scheduled here would start a cycle. */
309 BOOL_BITFIELD starts_cycle_p : 1;
310
311 /* True when the next insn scheduled here would be scheduled after a stall. */
312 BOOL_BITFIELD after_stall_p : 1;
313};
314typedef struct _fence *fence_t;
315
316#define FENCE_INSN(F) ((F)->insn)
317#define FENCE_STATE(F) ((F)->state)
318#define FENCE_BNDS(F) ((F)->bnds)
319#define FENCE_PROCESSED_P(F) ((F)->processed_p)
320#define FENCE_SCHEDULED_P(F) ((F)->scheduled_p)
321#define FENCE_ISSUED_INSNS(F) ((F)->cycle_issued_insns)
322#define FENCE_CYCLE(F) ((F)->cycle)
323#define FENCE_STARTS_CYCLE_P(F) ((F)->starts_cycle_p)
324#define FENCE_AFTER_STALL_P(F) ((F)->after_stall_p)
325#define FENCE_DC(F) ((F)->dc)
326#define FENCE_TC(F) ((F)->tc)
327#define FENCE_LAST_SCHEDULED_INSN(F) ((F)->last_scheduled_insn)
328#define FENCE_EXECUTING_INSNS(F) ((F)->executing_insns)
329#define FENCE_READY_TICKS(F) ((F)->ready_ticks)
330#define FENCE_READY_TICKS_SIZE(F) ((F)->ready_ticks_size)
331#define FENCE_SCHED_NEXT(F) ((F)->sched_next)
332
333/* List of fences. */
334typedef _list_t flist_t;
335#define FLIST_FENCE(L) (&(L)->u.fence)
336#define FLIST_NEXT(L) (_LIST_NEXT (L))
337
338/* List of fences with pointer to the tail node. */
339struct flist_tail_def
340{
341 flist_t head;
342 flist_t *tailp;
343};
344
345typedef struct flist_tail_def *flist_tail_t;
346#define FLIST_TAIL_HEAD(L) ((L)->head)
347#define FLIST_TAIL_TAILP(L) ((L)->tailp)
348
349/* List node information. A list node can be any of the types above. */
350struct _list_node
351{
352 _list_t next;
353
354 union
355 {
356 rtx x;
357 struct _bnd bnd;
358 expr_def expr;
359 struct _fence fence;
360 struct _def def;
361 void *data;
362 } u;
363};
364\f
365
366/* _list_t functions.
367 All of _*list_* functions are used through accessor macros, thus
368 we can't move them in sel-sched-ir.c. */
369extern alloc_pool sched_lists_pool;
370
371static inline _list_t
372_list_alloc (void)
373{
374 return (_list_t) pool_alloc (sched_lists_pool);
375}
376
377static inline void
378_list_add (_list_t *lp)
379{
380 _list_t l = _list_alloc ();
381
382 _LIST_NEXT (l) = *lp;
383 *lp = l;
384}
385
386static inline void
387_list_remove_nofree (_list_t *lp)
388{
389 _list_t n = *lp;
390
391 *lp = _LIST_NEXT (n);
392}
393
394static inline void
395_list_remove (_list_t *lp)
396{
397 _list_t n = *lp;
398
399 *lp = _LIST_NEXT (n);
400 pool_free (sched_lists_pool, n);
401}
402
403static inline void
404_list_clear (_list_t *l)
405{
406 while (*l)
407 _list_remove (l);
408}
409\f
410
411/* List iterator backend. */
412typedef struct
413{
414 /* The list we're iterating. */
415 _list_t *lp;
416
417 /* True when this iterator supprts removing. */
418 bool can_remove_p;
419
420 /* True when we've actually removed something. */
421 bool removed_p;
422} _list_iterator;
423
424static inline void
425_list_iter_start (_list_iterator *ip, _list_t *lp, bool can_remove_p)
426{
427 ip->lp = lp;
428 ip->can_remove_p = can_remove_p;
429 ip->removed_p = false;
430}
431
432static inline void
433_list_iter_next (_list_iterator *ip)
434{
435 if (!ip->removed_p)
436 ip->lp = &_LIST_NEXT (*ip->lp);
437 else
438 ip->removed_p = false;
439}
440
441static inline void
442_list_iter_remove (_list_iterator *ip)
443{
444 gcc_assert (!ip->removed_p && ip->can_remove_p);
445 _list_remove (ip->lp);
446 ip->removed_p = true;
447}
448
449static inline void
450_list_iter_remove_nofree (_list_iterator *ip)
451{
452 gcc_assert (!ip->removed_p && ip->can_remove_p);
453 _list_remove_nofree (ip->lp);
454 ip->removed_p = true;
455}
456
457/* General macros to traverse a list. FOR_EACH_* interfaces are
458 implemented using these. */
459#define _FOR_EACH(TYPE, ELEM, I, L) \
460 for (_list_iter_start (&(I), &(L), false); \
461 _list_iter_cond_##TYPE (*(I).lp, &(ELEM)); \
462 _list_iter_next (&(I)))
463
464#define _FOR_EACH_1(TYPE, ELEM, I, LP) \
465 for (_list_iter_start (&(I), (LP), true); \
466 _list_iter_cond_##TYPE (*(I).lp, &(ELEM)); \
467 _list_iter_next (&(I)))
468\f
469
470/* _xlist_t functions. */
471
472static inline void
473_xlist_add (_xlist_t *lp, rtx x)
474{
475 _list_add (lp);
476 _XLIST_X (*lp) = x;
477}
478
479#define _xlist_remove(LP) (_list_remove (LP))
480#define _xlist_clear(LP) (_list_clear (LP))
481
482static inline bool
483_xlist_is_in_p (_xlist_t l, rtx x)
484{
485 while (l)
486 {
487 if (_XLIST_X (l) == x)
488 return true;
489 l = _XLIST_NEXT (l);
490 }
491
492 return false;
493}
494
495/* Used through _FOR_EACH. */
496static inline bool
497_list_iter_cond_x (_xlist_t l, rtx *xp)
498{
499 if (l)
500 {
501 *xp = _XLIST_X (l);
502 return true;
503 }
504
505 return false;
506}
507
508#define _xlist_iter_remove(IP) (_list_iter_remove (IP))
509
510typedef _list_iterator _xlist_iterator;
511#define _FOR_EACH_X(X, I, L) _FOR_EACH (x, (X), (I), (L))
512#define _FOR_EACH_X_1(X, I, LP) _FOR_EACH_1 (x, (X), (I), (LP))
513\f
514
515/* ilist_t functions. Instruction lists are simply RTX lists. */
516
517#define ilist_add(LP, INSN) (_xlist_add ((LP), (INSN)))
518#define ilist_remove(LP) (_xlist_remove (LP))
519#define ilist_clear(LP) (_xlist_clear (LP))
520#define ilist_is_in_p(L, INSN) (_xlist_is_in_p ((L), (INSN)))
521#define ilist_iter_remove(IP) (_xlist_iter_remove (IP))
522
523typedef _xlist_iterator ilist_iterator;
524#define FOR_EACH_INSN(INSN, I, L) _FOR_EACH_X (INSN, I, L)
525#define FOR_EACH_INSN_1(INSN, I, LP) _FOR_EACH_X_1 (INSN, I, LP)
526\f
527
528/* Av set iterators. */
529typedef _list_iterator av_set_iterator;
530#define FOR_EACH_EXPR(EXPR, I, AV) _FOR_EACH (expr, (EXPR), (I), (AV))
531#define FOR_EACH_EXPR_1(EXPR, I, AV) _FOR_EACH_1 (expr, (EXPR), (I), (AV))
532
533static bool
534_list_iter_cond_expr (av_set_t av, expr_t *exprp)
535{
536 if (av)
537 {
538 *exprp = _AV_SET_EXPR (av);
539 return true;
540 }
541
542 return false;
543}
544\f
545
546/* Def list iterators. */
547typedef _list_t def_list_t;
548typedef _list_iterator def_list_iterator;
549
550#define DEF_LIST_NEXT(L) (_LIST_NEXT (L))
551#define DEF_LIST_DEF(L) (&(L)->u.def)
552
553#define FOR_EACH_DEF(DEF, I, DEF_LIST) _FOR_EACH (def, (DEF), (I), (DEF_LIST))
554
555static inline bool
556_list_iter_cond_def (def_list_t def_list, def_t *def)
557{
558 if (def_list)
559 {
560 *def = DEF_LIST_DEF (def_list);
561 return true;
562 }
563
564 return false;
565}
566\f
567
568/* InstructionData. Contains information about insn pattern. */
569struct idata_def
570{
571 /* Type of the insn.
572 o CALL_INSN - Call insn
573 o JUMP_INSN - Jump insn
574 o INSN - INSN that cannot be cloned
575 o USE - INSN that can be cloned
576 o SET - INSN that can be cloned and separable into lhs and rhs
577 o PC - simplejump. Insns that simply redirect control flow should not
578 have any dependencies. Sched-deps.c, though, might consider them as
579 producers or consumers of certain registers. To avoid that we handle
580 dependency for simple jumps ourselves. */
581 int type;
582
583 /* If insn is a SET, this is its left hand side. */
584 rtx lhs;
585
586 /* If insn is a SET, this is its right hand side. */
587 rtx rhs;
588
589 /* Registers that are set/used by this insn. This info is now gathered
590 via sched-deps.c. The downside of this is that we also use live info
591 from flow that is accumulated in the basic blocks. These two infos
592 can be slightly inconsistent, hence in the beginning we make a pass
593 through CFG and calculating the conservative solution for the info in
594 basic blocks. When this scheduler will be switched to use dataflow,
595 this can be unified as df gives us both per basic block and per
596 instruction info. Actually, we don't do that pass and just hope
597 for the best. */
598 regset reg_sets;
599
600 regset reg_clobbers;
601
602 regset reg_uses;
603};
604
605#define IDATA_TYPE(ID) ((ID)->type)
606#define IDATA_LHS(ID) ((ID)->lhs)
607#define IDATA_RHS(ID) ((ID)->rhs)
608#define IDATA_REG_SETS(ID) ((ID)->reg_sets)
609#define IDATA_REG_USES(ID) ((ID)->reg_uses)
610#define IDATA_REG_CLOBBERS(ID) ((ID)->reg_clobbers)
611
612/* Type to represent all needed info to emit an insn.
613 This is a virtual equivalent of the insn.
614 Every insn in the stream has an associated vinsn. This is used
615 to reduce memory consumption basing on the fact that many insns
616 don't change through the scheduler.
617
618 vinsn can be either normal or unique.
619 * Normal vinsn is the one, that can be cloned multiple times and typically
620 corresponds to normal instruction.
621
622 * Unique vinsn derivates from CALL, ASM, JUMP (for a while) and other
623 unusual stuff. Such a vinsn is described by its INSN field, which is a
624 reference to the original instruction. */
625struct vinsn_def
626{
627 /* Associated insn. */
628 rtx insn_rtx;
629
630 /* Its description. */
631 struct idata_def id;
632
633 /* Hash of vinsn. It is computed either from pattern or from rhs using
634 hash_rtx. It is not placed in ID for faster compares. */
635 unsigned hash;
636
637 /* Hash of the insn_rtx pattern. */
638 unsigned hash_rtx;
639
640 /* Smart pointer counter. */
641 int count;
642
643 /* Cached cost of the vinsn. To access it please use vinsn_cost (). */
644 int cost;
645
646 /* Mark insns that may trap so we don't move them through jumps. */
647 bool may_trap_p;
648};
649
650#define VINSN_INSN_RTX(VI) ((VI)->insn_rtx)
651#define VINSN_PATTERN(VI) (PATTERN (VINSN_INSN_RTX (VI)))
652
653#define VINSN_ID(VI) (&((VI)->id))
654#define VINSN_HASH(VI) ((VI)->hash)
655#define VINSN_HASH_RTX(VI) ((VI)->hash_rtx)
656#define VINSN_TYPE(VI) (IDATA_TYPE (VINSN_ID (VI)))
657#define VINSN_SEPARABLE_P(VI) (VINSN_TYPE (VI) == SET)
658#define VINSN_CLONABLE_P(VI) (VINSN_SEPARABLE_P (VI) || VINSN_TYPE (VI) == USE)
659#define VINSN_UNIQUE_P(VI) (!VINSN_CLONABLE_P (VI))
660#define VINSN_LHS(VI) (IDATA_LHS (VINSN_ID (VI)))
661#define VINSN_RHS(VI) (IDATA_RHS (VINSN_ID (VI)))
662#define VINSN_REG_SETS(VI) (IDATA_REG_SETS (VINSN_ID (VI)))
663#define VINSN_REG_USES(VI) (IDATA_REG_USES (VINSN_ID (VI)))
664#define VINSN_REG_CLOBBERS(VI) (IDATA_REG_CLOBBERS (VINSN_ID (VI)))
665#define VINSN_COUNT(VI) ((VI)->count)
666#define VINSN_MAY_TRAP_P(VI) ((VI)->may_trap_p)
667\f
668
669/* An entry of the hashtable describing transformations happened when
670 moving up through an insn. */
671struct transformed_insns
672{
673 /* Previous vinsn. Used to find the proper element. */
674 vinsn_t vinsn_old;
675
676 /* A new vinsn. */
677 vinsn_t vinsn_new;
678
679 /* Speculative status. */
680 ds_t ds;
681
682 /* Type of transformation happened. */
683 enum local_trans_type type;
684
685 /* Whether a conflict on the target register happened. */
686 BOOL_BITFIELD was_target_conflict : 1;
687
688 /* Whether a check was needed. */
689 BOOL_BITFIELD needs_check : 1;
690};
691
692/* Indexed by INSN_LUID, the collection of all data associated with
693 a single instruction that is in the stream. */
694struct _sel_insn_data
695{
696 /* The expression that contains vinsn for this insn and some
697 flow-sensitive data like priority. */
698 expr_def expr;
699
700 /* If (WS_LEVEL == GLOBAL_LEVEL) then AV is empty. */
701 int ws_level;
702
703 /* A number that helps in defining a traversing order for a region. */
704 int seqno;
705
706 /* A liveness data computed above this insn. */
707 regset live;
708
709 /* An INSN_UID bit is set when deps analysis result is already known. */
710 bitmap analyzed_deps;
711
712 /* An INSN_UID bit is set when a hard dep was found, not set when
713 no dependence is found. This is meaningful only when the analyzed_deps
714 bitmap has its bit set. */
715 bitmap found_deps;
716
717 /* An INSN_UID bit is set when this is a bookkeeping insn generated from
718 a parent with this uid. */
719 bitmap originators;
720
721 /* A hashtable caching the result of insn transformations through this one. */
722 htab_t transformed_insns;
723
724 /* A context incapsulating this insn. */
725 struct deps deps_context;
726
727 /* This field is initialized at the beginning of scheduling and is used
728 to handle sched group instructions. If it is non-null, then it points
729 to the instruction, which should be forced to schedule next. Such
730 instructions are unique. */
731 insn_t sched_next;
732
733 /* Cycle at which insn was scheduled. It is greater than zero if insn was
734 scheduled. This is used for bundling. */
735 int sched_cycle;
736
737 /* Cycle at which insn's data will be fully ready. */
738 int ready_cycle;
739
740 /* Speculations that are being checked by this insn. */
741 ds_t spec_checked_ds;
742
743 /* Whether the live set valid or not. */
744 BOOL_BITFIELD live_valid_p : 1;
745 /* Insn is an ASM. */
746 BOOL_BITFIELD asm_p : 1;
747
748 /* True when an insn is scheduled after we've determined that a stall is
749 required.
750 This is used when emulating the Haifa scheduler for bundling. */
751 BOOL_BITFIELD after_stall_p : 1;
752};
753
754typedef struct _sel_insn_data sel_insn_data_def;
755typedef sel_insn_data_def *sel_insn_data_t;
756
757DEF_VEC_O (sel_insn_data_def);
758DEF_VEC_ALLOC_O (sel_insn_data_def, heap);
759extern VEC (sel_insn_data_def, heap) *s_i_d;
760
761/* Accessor macros for s_i_d. */
762#define SID(INSN) (VEC_index (sel_insn_data_def, s_i_d, INSN_LUID (INSN)))
763#define SID_BY_UID(UID) (VEC_index (sel_insn_data_def, s_i_d, LUID_BY_UID (UID)))
764
765extern sel_insn_data_def insn_sid (insn_t);
766
767#define INSN_ASM_P(INSN) (SID (INSN)->asm_p)
768#define INSN_SCHED_NEXT(INSN) (SID (INSN)->sched_next)
769#define INSN_ANALYZED_DEPS(INSN) (SID (INSN)->analyzed_deps)
770#define INSN_FOUND_DEPS(INSN) (SID (INSN)->found_deps)
771#define INSN_DEPS_CONTEXT(INSN) (SID (INSN)->deps_context)
772#define INSN_ORIGINATORS(INSN) (SID (INSN)->originators)
773#define INSN_ORIGINATORS_BY_UID(UID) (SID_BY_UID (UID)->originators)
774#define INSN_TRANSFORMED_INSNS(INSN) (SID (INSN)->transformed_insns)
775
776#define INSN_EXPR(INSN) (&SID (INSN)->expr)
777#define INSN_LIVE(INSN) (SID (INSN)->live)
778#define INSN_LIVE_VALID_P(INSN) (SID (INSN)->live_valid_p)
779#define INSN_VINSN(INSN) (EXPR_VINSN (INSN_EXPR (INSN)))
780#define INSN_TYPE(INSN) (VINSN_TYPE (INSN_VINSN (INSN)))
781#define INSN_SIMPLEJUMP_P(INSN) (INSN_TYPE (INSN) == PC)
782#define INSN_LHS(INSN) (VINSN_LHS (INSN_VINSN (INSN)))
783#define INSN_RHS(INSN) (VINSN_RHS (INSN_VINSN (INSN)))
784#define INSN_REG_SETS(INSN) (VINSN_REG_SETS (INSN_VINSN (INSN)))
785#define INSN_REG_CLOBBERS(INSN) (VINSN_REG_CLOBBERS (INSN_VINSN (INSN)))
786#define INSN_REG_USES(INSN) (VINSN_REG_USES (INSN_VINSN (INSN)))
787#define INSN_SCHED_TIMES(INSN) (EXPR_SCHED_TIMES (INSN_EXPR (INSN)))
788#define INSN_SEQNO(INSN) (SID (INSN)->seqno)
789#define INSN_AFTER_STALL_P(INSN) (SID (INSN)->after_stall_p)
790#define INSN_SCHED_CYCLE(INSN) (SID (INSN)->sched_cycle)
791#define INSN_READY_CYCLE(INSN) (SID (INSN)->ready_cycle)
792#define INSN_SPEC_CHECKED_DS(INSN) (SID (INSN)->spec_checked_ds)
793
794/* A global level shows whether an insn is valid or not. */
795extern int global_level;
796
797#define INSN_WS_LEVEL(INSN) (SID (INSN)->ws_level)
798
799extern av_set_t get_av_set (insn_t);
800extern int get_av_level (insn_t);
801
802#define AV_SET(INSN) (get_av_set (INSN))
803#define AV_LEVEL(INSN) (get_av_level (INSN))
804#define AV_SET_VALID_P(INSN) (AV_LEVEL (INSN) == global_level)
805
806/* A list of fences currently in the works. */
807extern flist_t fences;
808
809/* A NOP pattern used as a placeholder for real insns. */
810extern rtx nop_pattern;
811
812/* An insn that 'contained' in EXIT block. */
813extern rtx exit_insn;
814
815/* Provide a separate luid for the insn. */
816#define INSN_INIT_TODO_LUID (1)
817
818/* Initialize s_s_i_d. */
819#define INSN_INIT_TODO_SSID (2)
820
821/* Initialize data for simplejump. */
822#define INSN_INIT_TODO_SIMPLEJUMP (4)
823
824/* Return true if INSN is a local NOP. The nop is local in the sense that
825 it was emitted by the scheduler as a temporary insn and will soon be
826 deleted. These nops are identified by their pattern. */
827#define INSN_NOP_P(INSN) (PATTERN (INSN) == nop_pattern)
828
829/* Return true if INSN is linked into instruction stream.
830 NB: It is impossible for INSN to have one field null and the other not
831 null: gcc_assert ((PREV_INSN (INSN) == NULL_RTX)
832 == (NEXT_INSN (INSN) == NULL_RTX)) is valid. */
833#define INSN_IN_STREAM_P(INSN) (PREV_INSN (INSN) && NEXT_INSN (INSN))
834
835/* Return true if INSN is in current fence. */
836#define IN_CURRENT_FENCE_P(INSN) (flist_lookup (fences, INSN) != NULL)
837
838/* Marks loop as being considered for pipelining. */
839#define MARK_LOOP_FOR_PIPELINING(LOOP) ((LOOP)->aux = (void *)(size_t)(1))
840#define LOOP_MARKED_FOR_PIPELINING_P(LOOP) ((size_t)((LOOP)->aux))
841
842/* Saved loop preheader to transfer when scheduling the loop. */
843#define LOOP_PREHEADER_BLOCKS(LOOP) ((size_t)((LOOP)->aux) == 1 \
844 ? NULL \
845 : ((VEC(basic_block, heap) *) (LOOP)->aux))
846#define SET_LOOP_PREHEADER_BLOCKS(LOOP,BLOCKS) ((LOOP)->aux \
847 = (BLOCKS != NULL \
848 ? BLOCKS \
849 : (LOOP)->aux))
850
851extern bitmap blocks_to_reschedule;
852\f
853
854/* A variable to track which part of rtx we are scanning in
855 sched-deps.c: sched_analyze_insn (). */
856enum deps_where_def
857 {
858 DEPS_IN_INSN,
859 DEPS_IN_LHS,
860 DEPS_IN_RHS,
861 DEPS_IN_NOWHERE
862 };
863typedef enum deps_where_def deps_where_t;
864\f
865
866/* Per basic block data for the whole CFG. */
867typedef struct
868{
869 /* For each bb header this field contains a set of live registers.
870 For all other insns this field has a NULL.
871 We also need to know LV sets for the instructions, that are immediatly
872 after the border of the region. */
873 regset lv_set;
874
875 /* Status of LV_SET.
876 true - block has usable LV_SET.
877 false - block's LV_SET should be recomputed. */
878 bool lv_set_valid_p;
879} sel_global_bb_info_def;
880
881typedef sel_global_bb_info_def *sel_global_bb_info_t;
882
883DEF_VEC_O (sel_global_bb_info_def);
884DEF_VEC_ALLOC_O (sel_global_bb_info_def, heap);
885
886/* Per basic block data. This array is indexed by basic block index. */
887extern VEC (sel_global_bb_info_def, heap) *sel_global_bb_info;
888
889extern void sel_extend_global_bb_info (void);
890extern void sel_finish_global_bb_info (void);
891
892/* Get data for BB. */
893#define SEL_GLOBAL_BB_INFO(BB) \
894 (VEC_index (sel_global_bb_info_def, sel_global_bb_info, (BB)->index))
895
896/* Access macros. */
897#define BB_LV_SET(BB) (SEL_GLOBAL_BB_INFO (BB)->lv_set)
898#define BB_LV_SET_VALID_P(BB) (SEL_GLOBAL_BB_INFO (BB)->lv_set_valid_p)
899
900/* Per basic block data for the region. */
901typedef struct
902{
903 /* This insn stream is constructed in such a way that it should be
904 traversed by PREV_INSN field - (*not* NEXT_INSN). */
905 rtx note_list;
906
907 /* Cached availability set at the beginning of a block.
908 See also AV_LEVEL () for conditions when this av_set can be used. */
909 av_set_t av_set;
910
911 /* If (AV_LEVEL == GLOBAL_LEVEL) then AV is valid. */
912 int av_level;
913} sel_region_bb_info_def;
914
915typedef sel_region_bb_info_def *sel_region_bb_info_t;
916
917DEF_VEC_O (sel_region_bb_info_def);
918DEF_VEC_ALLOC_O (sel_region_bb_info_def, heap);
919
920/* Per basic block data. This array is indexed by basic block index. */
921extern VEC (sel_region_bb_info_def, heap) *sel_region_bb_info;
922
923/* Get data for BB. */
924#define SEL_REGION_BB_INFO(BB) (VEC_index (sel_region_bb_info_def, \
925 sel_region_bb_info, (BB)->index))
926
927/* Get BB's note_list.
928 A note_list is a list of various notes that was scattered across BB
929 before scheduling, and will be appended at the beginning of BB after
930 scheduling is finished. */
931#define BB_NOTE_LIST(BB) (SEL_REGION_BB_INFO (BB)->note_list)
932
933#define BB_AV_SET(BB) (SEL_REGION_BB_INFO (BB)->av_set)
934#define BB_AV_LEVEL(BB) (SEL_REGION_BB_INFO (BB)->av_level)
935#define BB_AV_SET_VALID_P(BB) (BB_AV_LEVEL (BB) == global_level)
936
937/* Used in bb_in_ebb_p. */
938extern bitmap_head *forced_ebb_heads;
939
940/* The loop nest being pipelined. */
941extern struct loop *current_loop_nest;
942
943/* Saves pipelined blocks. Bitmap is indexed by bb->index. */
944extern sbitmap bbs_pipelined;
945
946/* Various flags. */
947extern bool enable_moveup_set_path_p;
948extern bool pipelining_p;
949extern bool bookkeeping_p;
950extern int max_insns_to_rename;
951extern bool preheader_removed;
952
953/* Software lookahead window size.
954 According to the results in Nakatani and Ebcioglu [1993], window size of 16
955 is enough to extract most ILP in integer code. */
956#define MAX_WS (PARAM_VALUE (PARAM_SELSCHED_MAX_LOOKAHEAD))
957
958extern regset sel_all_regs;
959\f
960
961/* Successor iterator backend. */
962typedef struct
963{
964 /* True if we're at BB end. */
965 bool bb_end;
966
967 /* An edge on which we're iterating. */
968 edge e1;
969
970 /* The previous edge saved after skipping empty blocks. */
971 edge e2;
972
973 /* Edge iterator used when there are successors in other basic blocks. */
974 edge_iterator ei;
975
976 /* Successor block we're traversing. */
977 basic_block bb;
978
979 /* Flags that are passed to the iterator. We return only successors
980 that comply to these flags. */
981 short flags;
982
983 /* When flags include SUCCS_ALL, this will be set to the exact type
984 of the sucessor we're traversing now. */
985 short current_flags;
986
987 /* If skip to loop exits, save here information about loop exits. */
988 int current_exit;
989 VEC (edge, heap) *loop_exits;
990} succ_iterator;
991
992/* A structure returning all successor's information. */
993struct succs_info
994{
995 /* Flags that these succcessors were computed with. */
996 short flags;
997
998 /* Successors that correspond to the flags. */
999 insn_vec_t succs_ok;
1000
1001 /* Their probabilities. As of now, we don't need this for other
1002 successors. */
1003 VEC(int,heap) *probs_ok;
1004
1005 /* Other successors. */
1006 insn_vec_t succs_other;
1007
1008 /* Probability of all successors. */
1009 int all_prob;
1010
1011 /* The number of all successors. */
1012 int all_succs_n;
1013
1014 /* The number of good successors. */
1015 int succs_ok_n;
1016};
1017
1018/* Some needed definitions. */
1019extern basic_block after_recovery;
1020
1021extern insn_t sel_bb_head (basic_block);
1022extern bool sel_bb_empty_p (basic_block);
1023extern bool in_current_region_p (basic_block);
1024
1025/* True when BB is a header of the inner loop. */
1026static inline bool
1027inner_loop_header_p (basic_block bb)
1028{
1029 struct loop *inner_loop;
1030
1031 if (!current_loop_nest)
1032 return false;
1033
1034 if (bb == EXIT_BLOCK_PTR)
1035 return false;
1036
1037 inner_loop = bb->loop_father;
1038 if (inner_loop == current_loop_nest)
1039 return false;
1040
1041 /* If successor belongs to another loop. */
1042 if (bb == inner_loop->header
1043 && flow_bb_inside_loop_p (current_loop_nest, bb))
1044 {
1045 /* Could be '=' here because of wrong loop depths. */
1046 gcc_assert (loop_depth (inner_loop) >= loop_depth (current_loop_nest));
1047 return true;
1048 }
1049
1050 return false;
1051}
1052
1053/* Return exit edges of LOOP, filtering out edges with the same dest bb. */
1054static inline VEC (edge, heap) *
1055get_loop_exit_edges_unique_dests (const struct loop *loop)
1056{
1057 VEC (edge, heap) *edges = NULL;
1058 struct loop_exit *exit;
1059
1060 gcc_assert (loop->latch != EXIT_BLOCK_PTR
1061 && current_loops->state & LOOPS_HAVE_RECORDED_EXITS);
1062
1063 for (exit = loop->exits->next; exit->e; exit = exit->next)
1064 {
1065 int i;
1066 edge e;
1067 bool was_dest = false;
1068
1069 for (i = 0; VEC_iterate (edge, edges, i, e); i++)
1070 if (e->dest == exit->e->dest)
1071 {
1072 was_dest = true;
1073 break;
1074 }
1075
1076 if (!was_dest)
1077 VEC_safe_push (edge, heap, edges, exit->e);
1078 }
1079 return edges;
1080}
1081
1082/* Collect all loop exits recursively, skipping empty BBs between them.
1083 E.g. if BB is a loop header which has several loop exits,
1084 traverse all of them and if any of them turns out to be another loop header
1085 (after skipping empty BBs), add its loop exits to the resulting vector
1086 as well. */
1087static inline VEC(edge, heap) *
1088get_all_loop_exits (basic_block bb)
1089{
1090 VEC(edge, heap) *exits = NULL;
1091
1092 /* If bb is empty, and we're skipping to loop exits, then
1093 consider bb as a possible gate to the inner loop now. */
1094 while (sel_bb_empty_p (bb)
1095 && in_current_region_p (bb))
1096 {
1097 bb = single_succ (bb);
1098
1099 /* This empty block could only lead outside the region. */
1100 gcc_assert (! in_current_region_p (bb));
1101 }
1102
1103 /* And now check whether we should skip over inner loop. */
1104 if (inner_loop_header_p (bb))
1105 {
1106 struct loop *this_loop;
1107 struct loop *pred_loop = NULL;
1108 int i;
1109 edge e;
1110
1111 for (this_loop = bb->loop_father;
1112 this_loop && this_loop != current_loop_nest;
1113 this_loop = loop_outer (this_loop))
1114 pred_loop = this_loop;
1115
1116 this_loop = pred_loop;
1117 gcc_assert (this_loop != NULL);
1118
1119 exits = get_loop_exit_edges_unique_dests (this_loop);
1120
1121 /* Traverse all loop headers. */
1122 for (i = 0; VEC_iterate (edge, exits, i, e); i++)
1123 if (in_current_region_p (e->dest))
1124 {
1125 VEC(edge, heap) *next_exits = get_all_loop_exits (e->dest);
1126
1127 if (next_exits)
1128 {
1129 int j;
1130 edge ne;
1131
1132 /* Add all loop exits for the current edge into the
1133 resulting vector. */
1134 for (j = 0; VEC_iterate (edge, next_exits, j, ne); j++)
1135 VEC_safe_push (edge, heap, exits, ne);
1136
1137 /* Remove the original edge. */
1138 VEC_ordered_remove (edge, exits, i);
1139
1140 /* Decrease the loop counter so we won't skip anything. */
1141 i--;
1142 continue;
1143 }
1144 }
1145 }
1146
1147 return exits;
1148}
1149
1150/* Flags to pass to compute_succs_info and FOR_EACH_SUCC.
1151 Any successor will fall into exactly one category. */
1152
1153/* Include normal successors. */
1154#define SUCCS_NORMAL (1)
1155
1156/* Include back-edge successors. */
1157#define SUCCS_BACK (2)
1158
1159/* Include successors that are outside of the current region. */
1160#define SUCCS_OUT (4)
1161
1162/* When pipelining of the outer loops is enabled, skip innermost loops
1163 to their exits. */
1164#define SUCCS_SKIP_TO_LOOP_EXITS (8)
1165
1166/* Include all successors. */
1167#define SUCCS_ALL (SUCCS_NORMAL | SUCCS_BACK | SUCCS_OUT)
1168
1169/* We need to return a succ_iterator to avoid 'unitialized' warning
1170 during bootstrap. */
1171static inline succ_iterator
1172_succ_iter_start (insn_t *succp, insn_t insn, int flags)
1173{
1174 succ_iterator i;
1175
1176 basic_block bb = BLOCK_FOR_INSN (insn);
1177
1178 gcc_assert (INSN_P (insn) || NOTE_INSN_BASIC_BLOCK_P (insn));
1179
1180 i.flags = flags;
1181
1182 /* Avoid 'uninitialized' warning. */
1183 *succp = NULL;
1184 i.e1 = NULL;
1185 i.e2 = NULL;
1186 i.bb = bb;
1187 i.current_flags = 0;
1188 i.current_exit = -1;
1189 i.loop_exits = NULL;
1190
1191 if (bb != EXIT_BLOCK_PTR && BB_END (bb) != insn)
1192 {
1193 i.bb_end = false;
1194
1195 /* Avoid 'uninitialized' warning. */
1196 i.ei.index = 0;
1197 i.ei.container = NULL;
1198 }
1199 else
1200 {
1201 i.ei = ei_start (bb->succs);
1202 i.bb_end = true;
1203 }
1204
1205 return i;
1206}
1207
1208static inline bool
1209_succ_iter_cond (succ_iterator *ip, rtx *succp, rtx insn,
1210 bool check (edge, succ_iterator *))
1211{
1212 if (!ip->bb_end)
1213 {
1214 /* When we're in a middle of a basic block, return
1215 the next insn immediately, but only when SUCCS_NORMAL is set. */
1216 if (*succp != NULL || (ip->flags & SUCCS_NORMAL) == 0)
1217 return false;
1218
1219 *succp = NEXT_INSN (insn);
1220 ip->current_flags = SUCCS_NORMAL;
1221 return true;
1222 }
1223 else
1224 {
1225 while (1)
1226 {
1227 edge e_tmp = NULL;
1228
1229 /* First, try loop exits, if we have them. */
1230 if (ip->loop_exits)
1231 {
1232 do
1233 {
1234 VEC_iterate (edge, ip->loop_exits,
1235 ip->current_exit, e_tmp);
1236 ip->current_exit++;
1237 }
1238 while (e_tmp && !check (e_tmp, ip));
1239
1240 if (!e_tmp)
1241 VEC_free (edge, heap, ip->loop_exits);
1242 }
1243
1244 /* If we have found a successor, then great. */
1245 if (e_tmp)
1246 {
1247 ip->e1 = e_tmp;
1248 break;
1249 }
1250
1251 /* If not, then try the next edge. */
1252 while (ei_cond (ip->ei, &(ip->e1)))
1253 {
1254 basic_block bb = ip->e1->dest;
1255
1256 /* Consider bb as a possible loop header. */
1257 if ((ip->flags & SUCCS_SKIP_TO_LOOP_EXITS)
1258 && flag_sel_sched_pipelining_outer_loops
1259 && (!in_current_region_p (bb)
1260 || BLOCK_TO_BB (ip->bb->index)
1261 < BLOCK_TO_BB (bb->index)))
1262 {
1263 /* Get all loop exits recursively. */
1264 ip->loop_exits = get_all_loop_exits (bb);
1265
1266 if (ip->loop_exits)
1267 {
1268 ip->current_exit = 0;
1269 /* Move the iterator now, because we won't do
1270 succ_iter_next until loop exits will end. */
1271 ei_next (&(ip->ei));
1272 break;
1273 }
1274 }
1275
1276 /* bb is not a loop header, check as usual. */
1277 if (check (ip->e1, ip))
1278 break;
1279
1280 ei_next (&(ip->ei));
1281 }
1282
1283 /* If loop_exits are non null, we have found an inner loop;
1284 do one more iteration to fetch an edge from these exits. */
1285 if (ip->loop_exits)
1286 continue;
1287
1288 /* Otherwise, we've found an edge in a usual way. Break now. */
1289 break;
1290 }
1291
1292 if (ip->e1)
1293 {
1294 basic_block bb = ip->e2->dest;
1295
1296 if (bb == EXIT_BLOCK_PTR || bb == after_recovery)
1297 *succp = exit_insn;
1298 else
1299 {
1300 *succp = sel_bb_head (bb);
1301
1302 gcc_assert (ip->flags != SUCCS_NORMAL
1303 || *succp == NEXT_INSN (bb_note (bb)));
1304 gcc_assert (BLOCK_FOR_INSN (*succp) == bb);
1305 }
1306
1307 return true;
1308 }
1309 else
1310 return false;
1311 }
1312}
1313
1314static inline void
1315_succ_iter_next (succ_iterator *ip)
1316{
1317 gcc_assert (!ip->e2 || ip->e1);
1318
1319 if (ip->bb_end && ip->e1 && !ip->loop_exits)
1320 ei_next (&(ip->ei));
1321}
1322
1323/* Returns true when E1 is an eligible successor edge, possibly skipping
1324 empty blocks. When E2P is not null, the resulting edge is written there.
1325 FLAGS are used to specify whether back edges and out-of-region edges
1326 should be considered. */
1327static inline bool
1328_eligible_successor_edge_p (edge e1, succ_iterator *ip)
1329{
1330 edge e2 = e1;
1331 basic_block bb;
1332 int flags = ip->flags;
1333 bool src_outside_rgn = !in_current_region_p (e1->src);
1334
1335 gcc_assert (flags != 0);
1336
1337 if (src_outside_rgn)
1338 {
1339 /* Any successor of the block that is outside current region is
1340 ineligible, except when we're skipping to loop exits. */
1341 gcc_assert (flags & (SUCCS_OUT | SUCCS_SKIP_TO_LOOP_EXITS));
1342
1343 if (flags & SUCCS_OUT)
1344 return false;
1345 }
1346
1347 bb = e2->dest;
1348
1349 /* Skip empty blocks, but be careful not to leave the region. */
1350 while (1)
1351 {
1352 if (!sel_bb_empty_p (bb))
1353 break;
1354
1355 if (!in_current_region_p (bb)
1356 && !(flags & SUCCS_OUT))
1357 return false;
1358
1359 e2 = EDGE_SUCC (bb, 0);
1360 bb = e2->dest;
1361
1362 /* This couldn't happen inside a region. */
1363 gcc_assert (! in_current_region_p (bb)
1364 || (flags & SUCCS_OUT));
1365 }
1366
1367 /* Save the second edge for later checks. */
1368 ip->e2 = e2;
1369
1370 if (in_current_region_p (bb))
1371 {
1372 /* BLOCK_TO_BB sets topological order of the region here.
1373 It is important to use real predecessor here, which is ip->bb,
1374 as we may well have e1->src outside current region,
1375 when skipping to loop exits. */
1376 bool succeeds_in_top_order = (BLOCK_TO_BB (ip->bb->index)
1377 < BLOCK_TO_BB (bb->index));
1378
1379 /* This is true for the all cases except the last one. */
1380 ip->current_flags = SUCCS_NORMAL;
1381
1382 /* We are advancing forward in the region, as usual. */
1383 if (succeeds_in_top_order)
1384 {
1385 /* We are skipping to loop exits here. */
1386 gcc_assert (!src_outside_rgn
1387 || flag_sel_sched_pipelining_outer_loops);
1388 return !!(flags & SUCCS_NORMAL);
1389 }
1390
1391 /* This is a back edge. During pipelining we ignore back edges,
1392 but only when it leads to the same loop. It can lead to the header
1393 of the outer loop, which will also be the preheader of
1394 the current loop. */
1395 if (pipelining_p
1396 && e1->src->loop_father == bb->loop_father)
1397 return !!(flags & SUCCS_NORMAL);
1398
1399 /* A back edge should be requested explicitly. */
1400 ip->current_flags = SUCCS_BACK;
1401 return !!(flags & SUCCS_BACK);
1402 }
1403
1404 ip->current_flags = SUCCS_OUT;
1405 return !!(flags & SUCCS_OUT);
1406}
1407
1408#define FOR_EACH_SUCC_1(SUCC, ITER, INSN, FLAGS) \
1409 for ((ITER) = _succ_iter_start (&(SUCC), (INSN), (FLAGS)); \
1410 _succ_iter_cond (&(ITER), &(SUCC), (INSN), _eligible_successor_edge_p); \
1411 _succ_iter_next (&(ITER)))
1412
1413#define FOR_EACH_SUCC(SUCC, ITER, INSN) \
1414 FOR_EACH_SUCC_1 (SUCC, ITER, INSN, SUCCS_NORMAL)
1415
1416/* Return the current edge along which a successor was built. */
1417#define SUCC_ITER_EDGE(ITER) ((ITER)->e1)
1418
1419/* Return the next block of BB not running into inconsistencies. */
1420static inline basic_block
1421bb_next_bb (basic_block bb)
1422{
1423 switch (EDGE_COUNT (bb->succs))
1424 {
1425 case 0:
1426 return bb->next_bb;
1427
1428 case 1:
1429 return single_succ (bb);
1430
1431 case 2:
1432 return FALLTHRU_EDGE (bb)->dest;
1433
1434 default:
1435 return bb->next_bb;
1436 }
1437
1438 gcc_unreachable ();
1439}
1440
1441\f
1442
1443/* Functions that are used in sel-sched.c. */
1444
1445/* List functions. */
1446extern ilist_t ilist_copy (ilist_t);
1447extern ilist_t ilist_invert (ilist_t);
1448extern void blist_add (blist_t *, insn_t, ilist_t, deps_t);
1449extern void blist_remove (blist_t *);
1450extern void flist_tail_init (flist_tail_t);
1451
1452extern fence_t flist_lookup (flist_t, insn_t);
1453extern void flist_clear (flist_t *);
1454extern void def_list_add (def_list_t *, insn_t, bool);
1455
1456/* Target context functions. */
1457extern tc_t create_target_context (bool);
1458extern void set_target_context (tc_t);
1459extern void reset_target_context (tc_t, bool);
1460
1461/* Deps context functions. */
1462extern void advance_deps_context (deps_t, insn_t);
1463
1464/* Fences functions. */
1465extern void init_fences (insn_t);
1466extern void add_clean_fence_to_fences (flist_tail_t, insn_t, fence_t);
1467extern void add_dirty_fence_to_fences (flist_tail_t, insn_t, fence_t);
1468extern void move_fence_to_fences (flist_t, flist_tail_t);
1469
1470/* Pool functions. */
1471extern regset get_regset_from_pool (void);
1472extern regset get_clear_regset_from_pool (void);
1473extern void return_regset_to_pool (regset);
1474extern void free_regset_pool (void);
1475
1476extern insn_t get_nop_from_pool (insn_t);
1477extern void return_nop_to_pool (insn_t);
1478extern void free_nop_pool (void);
1479
1480/* Vinsns functions. */
1481extern bool vinsn_separable_p (vinsn_t);
1482extern bool vinsn_cond_branch_p (vinsn_t);
1483extern void recompute_vinsn_lhs_rhs (vinsn_t);
1484extern int sel_vinsn_cost (vinsn_t);
1485extern insn_t sel_gen_insn_from_rtx_after (rtx, expr_t, int, insn_t);
1486extern insn_t sel_gen_recovery_insn_from_rtx_after (rtx, expr_t, int, insn_t);
1487extern insn_t sel_gen_insn_from_expr_after (expr_t, vinsn_t, int, insn_t);
1488extern insn_t sel_move_insn (expr_t, int, insn_t);
1489extern void vinsn_attach (vinsn_t);
1490extern void vinsn_detach (vinsn_t);
1491extern vinsn_t vinsn_copy (vinsn_t, bool);
1492extern bool vinsn_equal_p (vinsn_t, vinsn_t);
1493
1494/* EXPR functions. */
1495extern void copy_expr (expr_t, expr_t);
1496extern void copy_expr_onside (expr_t, expr_t);
1497extern void merge_expr_data (expr_t, expr_t, insn_t);
1498extern void merge_expr (expr_t, expr_t, insn_t);
1499extern void clear_expr (expr_t);
1500extern unsigned expr_dest_regno (expr_t);
1501extern rtx expr_dest_reg (expr_t);
1502extern int find_in_history_vect (VEC(expr_history_def, heap) *,
1503 rtx, vinsn_t, bool);
1504extern void insert_in_history_vect (VEC(expr_history_def, heap) **,
1505 unsigned, enum local_trans_type,
1506 vinsn_t, vinsn_t, ds_t);
1507extern void mark_unavailable_targets (av_set_t, av_set_t, regset);
1508extern int speculate_expr (expr_t, ds_t);
1509
1510/* Av set functions. */
1511extern void av_set_add (av_set_t *, expr_t);
1512extern void av_set_iter_remove (av_set_iterator *);
1513extern expr_t av_set_lookup (av_set_t, vinsn_t);
1514extern expr_t merge_with_other_exprs (av_set_t *, av_set_iterator *, expr_t);
1515extern bool av_set_is_in_p (av_set_t, vinsn_t);
1516extern av_set_t av_set_copy (av_set_t);
1517extern void av_set_union_and_clear (av_set_t *, av_set_t *, insn_t);
1518extern void av_set_union_and_live (av_set_t *, av_set_t *, regset, regset, insn_t);
1519extern void av_set_clear (av_set_t *);
1520extern void av_set_leave_one_nonspec (av_set_t *);
1521extern expr_t av_set_element (av_set_t, int);
1522extern void av_set_substract_cond_branches (av_set_t *);
1523extern void av_set_split_usefulness (av_set_t, int, int);
1524extern void av_set_intersect (av_set_t *, av_set_t);
1525
1526extern void sel_save_haifa_priorities (void);
1527
1528extern void sel_init_global_and_expr (bb_vec_t);
1529extern void sel_finish_global_and_expr (void);
1530
1531extern regset compute_live (insn_t);
1532
1533/* Dependence analysis functions. */
1534extern void sel_clear_has_dependence (void);
1535extern ds_t has_dependence_p (expr_t, insn_t, ds_t **);
1536
1537extern int tick_check_p (expr_t, deps_t, fence_t);
1538
1539/* Functions to work with insns. */
1540extern bool lhs_of_insn_equals_to_dest_p (insn_t, rtx);
1541extern bool insn_eligible_for_subst_p (insn_t);
1542extern void get_dest_and_mode (rtx, rtx *, enum machine_mode *);
1543
1544extern bool bookkeeping_can_be_created_if_moved_through_p (insn_t);
1545extern bool sel_remove_insn (insn_t, bool, bool);
1546extern bool bb_header_p (insn_t);
1547extern void sel_init_invalid_data_sets (insn_t);
1548extern bool insn_at_boundary_p (insn_t);
1549extern bool jump_leads_only_to_bb_p (insn_t, basic_block);
1550
1551/* Basic block and CFG functions. */
1552
1553extern insn_t sel_bb_head (basic_block);
1554extern bool sel_bb_head_p (insn_t);
1555extern insn_t sel_bb_end (basic_block);
1556extern bool sel_bb_end_p (insn_t);
1557extern bool sel_bb_empty_p (basic_block);
1558
1559extern bool in_current_region_p (basic_block);
1560extern basic_block fallthru_bb_of_jump (rtx);
1561
1562extern void sel_init_bbs (bb_vec_t, basic_block);
1563extern void sel_finish_bbs (void);
1564
1565extern struct succs_info * compute_succs_info (insn_t, short);
1566extern void free_succs_info (struct succs_info *);
1567extern bool sel_insn_has_single_succ_p (insn_t, int);
1568extern bool sel_num_cfg_preds_gt_1 (insn_t);
1569extern int get_seqno_by_preds (rtx);
1570
1571extern bool bb_ends_ebb_p (basic_block);
1572extern bool in_same_ebb_p (insn_t, insn_t);
1573
1574extern bool tidy_control_flow (basic_block, bool);
1575extern void free_bb_note_pool (void);
1576
1577extern void sel_remove_empty_bb (basic_block, bool, bool);
1578extern bool maybe_tidy_empty_bb (basic_block bb);
1579extern basic_block sel_split_edge (edge);
1580extern basic_block sel_create_recovery_block (insn_t);
1581extern void sel_merge_blocks (basic_block, basic_block);
1582extern void sel_redirect_edge_and_branch (edge, basic_block);
1583extern void sel_redirect_edge_and_branch_force (edge, basic_block);
1584extern void sel_init_pipelining (void);
1585extern void sel_finish_pipelining (void);
1586extern void sel_sched_region (int);
1587extern void sel_find_rgns (void);
1588extern loop_p get_loop_nest_for_rgn (unsigned int);
1589extern bool considered_for_pipelining_p (struct loop *);
1590extern void make_region_from_loop_preheader (VEC(basic_block, heap) **);
1591extern void sel_add_loop_preheaders (void);
1592extern bool sel_is_loop_preheader_p (basic_block);
1593extern void clear_outdated_rtx_info (basic_block);
1594extern void free_data_sets (basic_block);
1595extern void exchange_data_sets (basic_block, basic_block);
1596extern void copy_data_sets (basic_block, basic_block);
1597
1598extern void sel_register_cfg_hooks (void);
1599extern void sel_unregister_cfg_hooks (void);
1600
1601/* Expression transformation routines. */
1602extern rtx create_insn_rtx_from_pattern (rtx, rtx);
1603extern vinsn_t create_vinsn_from_insn_rtx (rtx, bool);
1604extern rtx create_copy_of_insn_rtx (rtx);
1605extern void change_vinsn_in_expr (expr_t, vinsn_t);
1606
1607/* Various initialization functions. */
1608extern void init_lv_sets (void);
1609extern void free_lv_sets (void);
1610extern void setup_nop_and_exit_insns (void);
1611extern void free_nop_and_exit_insns (void);
1612extern void setup_nop_vinsn (void);
1613extern void free_nop_vinsn (void);
1614extern void sel_set_sched_flags (void);
1615extern void sel_setup_sched_infos (void);
1616extern void alloc_sched_pools (void);
1617extern void free_sched_pools (void);
1618
1619#endif /* GCC_SEL_SCHED_IR_H */
1620
1621
1622
1623
1624
1625
1626
1627