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