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