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