Branch data Line data Source code
1 : : /* Instruction scheduling pass. This file contains definitions used
2 : : internally in the scheduler.
3 : : Copyright (C) 2006-2025 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 : 198687 : _list_alloc (void)
364 : : {
365 : 397374 : return sched_lists_pool.allocate ();
366 : : }
367 : :
368 : : inline void
369 : 198687 : _list_add (_list_t *lp)
370 : : {
371 : 230123 : _list_t l = _list_alloc ();
372 : :
373 : 198687 : _LIST_NEXT (l) = *lp;
374 : 173433 : *lp = l;
375 : : }
376 : :
377 : : inline void
378 : 1391 : _list_remove_nofree (_list_t *lp)
379 : : {
380 : 1391 : _list_t n = *lp;
381 : :
382 : 1391 : *lp = _LIST_NEXT (n);
383 : : }
384 : :
385 : : inline void
386 : 196672 : _list_remove (_list_t *lp)
387 : : {
388 : 196672 : _list_t n = *lp;
389 : :
390 : 196672 : *lp = _LIST_NEXT (n);
391 : 43408 : sched_lists_pool.remove (n);
392 : 31572 : }
393 : :
394 : : inline void
395 : 11730 : _list_clear (_list_t *l)
396 : : {
397 : 38907 : while (*l)
398 : 27177 : _list_remove (l);
399 : 11730 : }
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 : 573453 : _list_iter_start (_list_iterator *ip, _list_t *lp, bool can_remove_p)
417 : : {
418 : 627402 : ip->lp = lp;
419 : 369454 : ip->can_remove_p = can_remove_p;
420 : 420708 : ip->removed_p = false;
421 : 573453 : }
422 : :
423 : : inline void
424 : 803519 : _list_iter_next (_list_iterator *ip)
425 : : {
426 : 440962 : if (!ip->removed_p)
427 : 314902 : ip->lp = &_LIST_NEXT (*ip->lp);
428 : : else
429 : 126060 : ip->removed_p = false;
430 : 292958 : }
431 : :
432 : : inline void
433 : 126087 : _list_iter_remove (_list_iterator *ip)
434 : : {
435 : 126087 : gcc_assert (!ip->removed_p && ip->can_remove_p);
436 : 126087 : _list_remove (ip->lp);
437 : 126087 : ip->removed_p = true;
438 : 126087 : }
439 : :
440 : : inline void
441 : 1391 : _list_iter_remove_nofree (_list_iterator *ip)
442 : : {
443 : 1391 : gcc_assert (!ip->removed_p && ip->can_remove_p);
444 : 1391 : _list_remove_nofree (ip->lp);
445 : 1391 : ip->removed_p = true;
446 : 1391 : }
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 : 59490 : ilist_add (ilist_t *lp, insn_t insn)
510 : : {
511 : 59490 : _list_add (lp);
512 : 59490 : ILIST_INSN (*lp) = insn;
513 : 954 : }
514 : : #define ilist_remove(LP) (_list_remove (LP))
515 : : #define ilist_clear(LP) (_list_clear (LP))
516 : :
517 : : inline bool
518 : 1037 : ilist_is_in_p (ilist_t l, insn_t insn)
519 : : {
520 : 20252 : while (l)
521 : : {
522 : 16898 : if (ILIST_INSN (l) == insn)
523 : : return true;
524 : 16815 : l = ILIST_NEXT (l);
525 : : }
526 : :
527 : : return false;
528 : : }
529 : :
530 : : /* Used through _FOR_EACH. */
531 : : inline bool
532 : 8523 : _list_iter_cond_insn (ilist_t l, insn_t *ip)
533 : : {
534 : 8523 : if (l)
535 : : {
536 : 5821 : *ip = ILIST_INSN (l);
537 : 5821 : 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 : 1373770 : _list_iter_cond_expr (av_set_t av, expr_t *exprp)
557 : : {
558 : 1373770 : if (av)
559 : : {
560 : 869981 : *exprp = _AV_SET_EXPR (av);
561 : 816179 : 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 : 12649 : _list_iter_cond_def (def_list_t def_list, def_t *def)
579 : : {
580 : 12649 : if (def_list)
581 : : {
582 : 7090 : *def = DEF_LIST_DEF (def_list);
583 : 7090 : 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 : 8547 : 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_PREHEADER_BLOCKS(LOOP) ((size_t)((LOOP)->aux) == 1 \
866 : : ? NULL \
867 : : : ((vec<basic_block> *) (LOOP)->aux))
868 : : #define SET_LOOP_PREHEADER_BLOCKS(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 preheader_removed;
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 : 413 : inner_loop_header_p (basic_block bb)
1045 : : {
1046 : 413 : class loop *inner_loop;
1047 : :
1048 : 413 : if (!current_loop_nest)
1049 : : return false;
1050 : :
1051 : 263 : if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1052 : : return false;
1053 : :
1054 : 263 : inner_loop = bb->loop_father;
1055 : 263 : if (inner_loop == current_loop_nest)
1056 : : return false;
1057 : :
1058 : : /* If successor belongs to another loop. */
1059 : 119 : if (bb == inner_loop->header
1060 : 119 : && flow_bb_inside_loop_p (current_loop_nest, bb))
1061 : : {
1062 : : /* Could be '=' here because of wrong loop depths. */
1063 : 60 : 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 : 30 : get_loop_exit_edges_unique_dests (const class loop *loop)
1073 : : {
1074 : 30 : vec<edge> edges = vNULL;
1075 : 30 : struct loop_exit *exit;
1076 : :
1077 : 30 : gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun)
1078 : : && current_loops->state & LOOPS_HAVE_RECORDED_EXITS);
1079 : :
1080 : 78 : for (exit = loop->exits->next; exit->e; exit = exit->next)
1081 : : {
1082 : : int i;
1083 : : edge e;
1084 : 75 : bool was_dest = false;
1085 : :
1086 : 75 : for (i = 0; edges.iterate (i, &e); i++)
1087 : 27 : if (e->dest == exit->e->dest)
1088 : : {
1089 : : was_dest = true;
1090 : : break;
1091 : : }
1092 : :
1093 : 48 : if (!was_dest)
1094 : 48 : edges.safe_push (exit->e);
1095 : : }
1096 : 30 : return edges;
1097 : : }
1098 : :
1099 : : inline bool
1100 : 27556 : sel_bb_empty_or_nop_p (basic_block bb)
1101 : : {
1102 : 27556 : insn_t first = sel_bb_head (bb), last;
1103 : :
1104 : 27556 : if (first == NULL_RTX)
1105 : : return true;
1106 : :
1107 : 27549 : if (!INSN_NOP_P (first))
1108 : : return false;
1109 : :
1110 : 1121 : if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1111 : : return false;
1112 : :
1113 : 55 : last = sel_bb_end (bb);
1114 : 55 : 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 : 395 : get_all_loop_exits (basic_block bb)
1127 : : {
1128 : 395 : 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 : 395 : while (sel_bb_empty_or_nop_p (bb)
1133 : 7 : && in_current_region_p (bb)
1134 : 395 : && EDGE_COUNT (bb->succs) > 0)
1135 : : {
1136 : 0 : bb = single_succ (bb);
1137 : :
1138 : : /* This empty block could only lead outside the region. */
1139 : 0 : gcc_assert (! in_current_region_p (bb));
1140 : : }
1141 : :
1142 : : /* And now check whether we should skip over inner loop. */
1143 : 395 : if (inner_loop_header_p (bb))
1144 : : {
1145 : 30 : class loop *this_loop;
1146 : 30 : class loop *pred_loop = NULL;
1147 : 30 : int i;
1148 : 30 : unsigned this_depth;
1149 : 30 : edge e;
1150 : :
1151 : 30 : for (this_loop = bb->loop_father;
1152 : 60 : this_loop && this_loop != current_loop_nest;
1153 : 30 : this_loop = loop_outer (this_loop))
1154 : 30 : pred_loop = this_loop;
1155 : :
1156 : 30 : this_loop = pred_loop;
1157 : 30 : gcc_assert (this_loop != NULL);
1158 : :
1159 : 30 : exits = get_loop_exit_edges_unique_dests (this_loop);
1160 : 30 : this_depth = loop_depth (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 : 78 : for (i = 0; exits.iterate (i, &e); i++)
1165 : 48 : if ((in_current_region_p (e->dest)
1166 : 18 : || (inner_loop_header_p (e->dest)))
1167 : 78 : && loop_depth (e->dest->loop_father) >= this_depth)
1168 : : {
1169 : 0 : auto_vec<edge> next_exits = get_all_loop_exits (e->dest);
1170 : :
1171 : 0 : 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 : 0 : for (j = 0; next_exits.iterate (j, &ne); j++)
1179 : 0 : exits.safe_push (ne);
1180 : :
1181 : : /* Remove the original edge. */
1182 : 0 : exits.ordered_remove (i);
1183 : :
1184 : : /* Decrease the loop counter so we won't skip anything. */
1185 : 0 : i--;
1186 : 0 : continue;
1187 : 0 : }
1188 : 0 : }
1189 : : }
1190 : :
1191 : 395 : 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 : 27612 : _succ_iter_start (insn_t *succp, insn_t insn, int flags)
1217 : : {
1218 : 27612 : succ_iterator i;
1219 : :
1220 : 27612 : basic_block bb = BLOCK_FOR_INSN (insn);
1221 : :
1222 : 27612 : gcc_assert (INSN_P (insn) || NOTE_INSN_BASIC_BLOCK_P (insn));
1223 : :
1224 : 27612 : i.flags = flags;
1225 : :
1226 : : /* Avoid 'uninitialized' warning. */
1227 : 27612 : *succp = NULL;
1228 : 27612 : i.e1 = NULL;
1229 : 27612 : i.e2 = NULL;
1230 : 27612 : i.bb = bb;
1231 : 27612 : i.current_flags = 0;
1232 : 27612 : i.current_exit = -1;
1233 : 27612 : i.loop_exits.create (0);
1234 : :
1235 : 27612 : if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun) && BB_END (bb) != insn)
1236 : : {
1237 : 11244 : i.bb_end = false;
1238 : :
1239 : : /* Avoid 'uninitialized' warning. */
1240 : 11244 : i.ei.index = 0;
1241 : 11244 : i.ei.container = 0;
1242 : : }
1243 : : else
1244 : : {
1245 : 16368 : i.ei = ei_start (bb->succs);
1246 : 16368 : i.bb_end = true;
1247 : : }
1248 : :
1249 : 27612 : return i;
1250 : : }
1251 : :
1252 : : inline bool
1253 : 63314 : _succ_iter_cond (succ_iterator *ip, insn_t *succp, insn_t insn,
1254 : : bool check (edge, succ_iterator *))
1255 : : {
1256 : 63314 : 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 : 22488 : if (*succp != NULL || (ip->flags & SUCCS_NORMAL) == 0)
1261 : : return false;
1262 : :
1263 : 11244 : *succp = NEXT_INSN (insn);
1264 : 11244 : ip->current_flags = SUCCS_NORMAL;
1265 : 11244 : return true;
1266 : : }
1267 : : else
1268 : : {
1269 : 40886 : while (1)
1270 : : {
1271 : 40856 : edge e_tmp = NULL;
1272 : :
1273 : : /* First, try loop exits, if we have them. */
1274 : 40856 : if (ip->loop_exits.exists ())
1275 : : {
1276 : 78 : do
1277 : : {
1278 : 78 : ip->loop_exits.iterate (ip->current_exit, &e_tmp);
1279 : 78 : ip->current_exit++;
1280 : : }
1281 : 138 : while (e_tmp && !check (e_tmp, ip));
1282 : :
1283 : 60 : if (!e_tmp)
1284 : 30 : ip->loop_exits.release ();
1285 : : }
1286 : :
1287 : : /* If we have found a successor, then great. */
1288 : 40856 : if (e_tmp)
1289 : : {
1290 : 30 : ip->e1 = e_tmp;
1291 : 30 : break;
1292 : : }
1293 : :
1294 : : /* If not, then try the next edge. */
1295 : 43474 : while (ei_cond (ip->ei, &(ip->e1)))
1296 : : {
1297 : 27143 : basic_block bb = ip->e1->dest;
1298 : :
1299 : : /* Consider bb as a possible loop header. */
1300 : 27143 : if ((ip->flags & SUCCS_SKIP_TO_LOOP_EXITS)
1301 : 3847 : && flag_sel_sched_pipelining_outer_loops
1302 : 27585 : && (!in_current_region_p (bb)
1303 : 197 : || BLOCK_TO_BB (ip->bb->index)
1304 : 197 : < BLOCK_TO_BB (bb->index)))
1305 : : {
1306 : : /* Get all loop exits recursively. */
1307 : 395 : ip->loop_exits = get_all_loop_exits (bb);
1308 : :
1309 : 395 : if (ip->loop_exits.exists ())
1310 : : {
1311 : 30 : ip->current_exit = 0;
1312 : : /* Move the iterator now, because we won't do
1313 : : succ_iter_next until loop exits will end. */
1314 : 30 : ei_next (&(ip->ei));
1315 : 30 : break;
1316 : : }
1317 : : }
1318 : :
1319 : : /* bb is not a loop header, check as usual. */
1320 : 27113 : if (check (ip->e1, ip))
1321 : : break;
1322 : :
1323 : 2648 : ei_next (&(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 : 40826 : if (ip->loop_exits.exists ())
1329 : 30 : continue;
1330 : :
1331 : : /* Otherwise, we've found an edge in a usual way. Break now. */
1332 : : break;
1333 : : }
1334 : :
1335 : 40826 : if (ip->e1)
1336 : : {
1337 : 24495 : basic_block bb = ip->e2->dest;
1338 : :
1339 : 24495 : if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun) || bb == after_recovery)
1340 : 752 : *succp = exit_insn;
1341 : : else
1342 : : {
1343 : 23743 : *succp = sel_bb_head (bb);
1344 : :
1345 : 23743 : gcc_assert (ip->flags != SUCCS_NORMAL
1346 : : || *succp == NEXT_INSN (bb_note (bb)));
1347 : 23743 : gcc_assert (BLOCK_FOR_INSN (*succp) == bb);
1348 : : }
1349 : :
1350 : 24495 : return true;
1351 : : }
1352 : : else
1353 : : return false;
1354 : : }
1355 : : }
1356 : :
1357 : : inline void
1358 : 35702 : _succ_iter_next (succ_iterator *ip)
1359 : : {
1360 : 35702 : gcc_assert (!ip->e2 || ip->e1);
1361 : :
1362 : 35702 : if (ip->bb_end && ip->e1 && !ip->loop_exits.exists ())
1363 : 24428 : ei_next (&(ip->ei));
1364 : 35702 : }
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 : 27161 : _eligible_successor_edge_p (edge e1, succ_iterator *ip)
1372 : : {
1373 : 27161 : edge e2 = e1;
1374 : 27161 : basic_block bb;
1375 : 27161 : int flags = ip->flags;
1376 : 27161 : bool src_outside_rgn = !in_current_region_p (e1->src);
1377 : :
1378 : 27161 : gcc_assert (flags != 0);
1379 : :
1380 : 27161 : 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 : 48 : gcc_assert (flags & (SUCCS_OUT | SUCCS_SKIP_TO_LOOP_EXITS));
1385 : :
1386 : 48 : if (flags & SUCCS_OUT)
1387 : : return false;
1388 : : }
1389 : :
1390 : 27161 : bb = e2->dest;
1391 : :
1392 : : /* Skip empty blocks, but be careful not to leave the region. */
1393 : 27314 : while (1)
1394 : : {
1395 : 27314 : if (!sel_bb_empty_p (bb))
1396 : : {
1397 : 27161 : edge ne;
1398 : 27161 : basic_block nbb;
1399 : :
1400 : 27161 : if (!sel_bb_empty_or_nop_p (bb))
1401 : : break;
1402 : :
1403 : 48 : ne = EDGE_SUCC (bb, 0);
1404 : 48 : nbb = ne->dest;
1405 : :
1406 : 48 : if (!in_current_region_p (nbb)
1407 : 48 : && !(flags & SUCCS_OUT))
1408 : : break;
1409 : :
1410 : 48 : e2 = ne;
1411 : 48 : bb = nbb;
1412 : 48 : continue;
1413 : 48 : }
1414 : :
1415 : 153 : if (!in_current_region_p (bb)
1416 : 153 : && !(flags & SUCCS_OUT))
1417 : : return false;
1418 : :
1419 : 153 : if (EDGE_COUNT (bb->succs) == 0)
1420 : : return false;
1421 : :
1422 : 105 : e2 = EDGE_SUCC (bb, 0);
1423 : 105 : bb = e2->dest;
1424 : : }
1425 : :
1426 : : /* Save the second edge for later checks. */
1427 : 27113 : ip->e2 = e2;
1428 : :
1429 : 27113 : 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 : 15497 : bool succeeds_in_top_order = (BLOCK_TO_BB (ip->bb->index)
1436 : 15497 : < BLOCK_TO_BB (bb->index));
1437 : :
1438 : : /* This is true for the all cases except the last one. */
1439 : 15497 : ip->current_flags = SUCCS_NORMAL;
1440 : :
1441 : : /* We are advancing forward in the region, as usual. */
1442 : 15497 : if (succeeds_in_top_order)
1443 : : {
1444 : : /* We are skipping to loop exits here. */
1445 : 13309 : gcc_assert (!src_outside_rgn
1446 : : || flag_sel_sched_pipelining_outer_loops);
1447 : 13309 : 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 : 2188 : if (pipelining_p
1455 : 1640 : && e1->src->loop_father == bb->loop_father)
1456 : 1640 : return !!(flags & SUCCS_NORMAL);
1457 : :
1458 : : /* A back edge should be requested explicitly. */
1459 : 548 : ip->current_flags = SUCCS_BACK;
1460 : 548 : return !!(flags & SUCCS_BACK);
1461 : : }
1462 : :
1463 : 11616 : ip->current_flags = SUCCS_OUT;
1464 : 11616 : 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 : 1618 : bb_next_bb (basic_block bb)
1481 : : {
1482 : 1618 : switch (EDGE_COUNT (bb->succs))
1483 : : {
1484 : 10 : case 0:
1485 : 10 : return bb->next_bb;
1486 : :
1487 : 493 : case 1:
1488 : 493 : return single_succ (bb);
1489 : :
1490 : 1114 : case 2:
1491 : 1114 : return FALLTHRU_EDGE (bb)->dest;
1492 : :
1493 : 1 : default:
1494 : 1 : 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 bb_header_p (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 make_region_from_loop_preheader (vec<basic_block> *&);
1645 : : extern void sel_add_loop_preheaders (bb_vec_t *);
1646 : : extern bool sel_is_loop_preheader_p (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 */
|
