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