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