Line data Source code
1 : /* Instruction scheduling pass. This file contains definitions used
2 : internally in the scheduler.
3 : Copyright (C) 2006-2026 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 214395 : _list_alloc (void)
364 : {
365 428790 : return sched_lists_pool.allocate ();
366 : }
367 :
368 : inline void
369 214395 : _list_add (_list_t *lp)
370 : {
371 247945 : _list_t l = _list_alloc ();
372 :
373 214395 : _LIST_NEXT (l) = *lp;
374 187817 : *lp = l;
375 : }
376 :
377 : inline void
378 1917 : _list_remove_nofree (_list_t *lp)
379 : {
380 1917 : _list_t n = *lp;
381 :
382 1917 : *lp = _LIST_NEXT (n);
383 : }
384 :
385 : inline void
386 211839 : _list_remove (_list_t *lp)
387 : {
388 211839 : _list_t n = *lp;
389 :
390 211839 : *lp = _LIST_NEXT (n);
391 46088 : sched_lists_pool.remove (n);
392 32941 : }
393 :
394 : inline void
395 11699 : _list_clear (_list_t *l)
396 : {
397 39702 : while (*l)
398 28003 : _list_remove (l);
399 11699 : }
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 647553 : _list_iter_start (_list_iterator *ip, _list_t *lp, bool can_remove_p)
417 : {
418 703048 : ip->lp = lp;
419 413815 : ip->can_remove_p = can_remove_p;
420 466840 : ip->removed_p = false;
421 647553 : }
422 :
423 : inline void
424 916752 : _list_iter_next (_list_iterator *ip)
425 : {
426 502269 : if (!ip->removed_p)
427 364549 : ip->lp = &_LIST_NEXT (*ip->lp);
428 : else
429 137720 : ip->removed_p = false;
430 338137 : }
431 :
432 : inline void
433 137748 : _list_iter_remove (_list_iterator *ip)
434 : {
435 137748 : gcc_assert (!ip->removed_p && ip->can_remove_p);
436 137748 : _list_remove (ip->lp);
437 137748 : ip->removed_p = true;
438 137748 : }
439 :
440 : inline void
441 1917 : _list_iter_remove_nofree (_list_iterator *ip)
442 : {
443 1917 : gcc_assert (!ip->removed_p && ip->can_remove_p);
444 1917 : _list_remove_nofree (ip->lp);
445 1917 : ip->removed_p = true;
446 1917 : }
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 62832 : ilist_add (ilist_t *lp, insn_t insn)
510 : {
511 62832 : _list_add (lp);
512 62832 : ILIST_INSN (*lp) = insn;
513 958 : }
514 : #define ilist_remove(LP) (_list_remove (LP))
515 : #define ilist_clear(LP) (_list_clear (LP))
516 :
517 : inline bool
518 1033 : ilist_is_in_p (ilist_t l, insn_t insn)
519 : {
520 23067 : while (l)
521 : {
522 18978 : if (ILIST_INSN (l) == insn)
523 : return true;
524 18903 : l = ILIST_NEXT (l);
525 : }
526 :
527 : return false;
528 : }
529 :
530 : /* Used through _FOR_EACH. */
531 : inline bool
532 8553 : _list_iter_cond_insn (ilist_t l, insn_t *ip)
533 : {
534 8553 : if (l)
535 : {
536 5859 : *ip = ILIST_INSN (l);
537 5859 : 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 1561401 : _list_iter_cond_expr (av_set_t av, expr_t *exprp)
557 : {
558 1561401 : if (av)
559 : {
560 993260 : *exprp = _AV_SET_EXPR (av);
561 934523 : 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 12442 : _list_iter_cond_def (def_list_t def_list, def_t *def)
579 : {
580 12442 : if (def_list)
581 : {
582 7029 : *def = DEF_LIST_DEF (def_list);
583 7029 : 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 8776 : 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 420 : inner_loop_header_p (basic_block bb)
1045 : {
1046 420 : class loop *inner_loop;
1047 :
1048 420 : if (!current_loop_nest)
1049 : return false;
1050 :
1051 268 : if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1052 : return false;
1053 :
1054 268 : inner_loop = bb->loop_father;
1055 268 : 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 29344 : sel_bb_empty_or_nop_p (basic_block bb)
1101 : {
1102 29344 : insn_t first = sel_bb_head (bb), last;
1103 :
1104 29344 : if (first == NULL_RTX)
1105 : return true;
1106 :
1107 29337 : if (!INSN_NOP_P (first))
1108 : return false;
1109 :
1110 1157 : if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1111 : return false;
1112 :
1113 72 : last = sel_bb_end (bb);
1114 72 : 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 402 : get_all_loop_exits (basic_block bb)
1127 : {
1128 402 : 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 402 : while (sel_bb_empty_or_nop_p (bb)
1133 7 : && in_current_region_p (bb)
1134 402 : && 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 402 : 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 402 : 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 28831 : _succ_iter_start (insn_t *succp, insn_t insn, int flags)
1217 : {
1218 28831 : succ_iterator i;
1219 :
1220 28831 : basic_block bb = BLOCK_FOR_INSN (insn);
1221 :
1222 28831 : gcc_assert (INSN_P (insn) || NOTE_INSN_BASIC_BLOCK_P (insn));
1223 :
1224 28831 : i.flags = flags;
1225 :
1226 : /* Avoid 'uninitialized' warning. */
1227 28831 : *succp = NULL;
1228 28831 : i.e1 = NULL;
1229 28831 : i.e2 = NULL;
1230 28831 : i.bb = bb;
1231 28831 : i.current_flags = 0;
1232 28831 : i.current_exit = -1;
1233 28831 : i.loop_exits.create (0);
1234 :
1235 28831 : if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun) && BB_END (bb) != insn)
1236 : {
1237 11250 : i.bb_end = false;
1238 :
1239 : /* Avoid 'uninitialized' warning. */
1240 11250 : i.ei.index = 0;
1241 11250 : i.ei.container = 0;
1242 : }
1243 : else
1244 : {
1245 17581 : i.ei = ei_start (bb->succs);
1246 17581 : i.bb_end = true;
1247 : }
1248 :
1249 28831 : return i;
1250 : }
1251 :
1252 : inline bool
1253 66264 : _succ_iter_cond (succ_iterator *ip, insn_t *succp, insn_t insn,
1254 : bool check (edge, succ_iterator *))
1255 : {
1256 66264 : 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 22500 : if (*succp != NULL || (ip->flags & SUCCS_NORMAL) == 0)
1261 : return false;
1262 :
1263 11250 : *succp = NEXT_INSN (insn);
1264 11250 : ip->current_flags = SUCCS_NORMAL;
1265 11250 : return true;
1266 : }
1267 : else
1268 : {
1269 43824 : while (1)
1270 : {
1271 43794 : edge e_tmp = NULL;
1272 :
1273 : /* First, try loop exits, if we have them. */
1274 43794 : 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 43794 : if (e_tmp)
1289 : {
1290 30 : ip->e1 = e_tmp;
1291 30 : break;
1292 : }
1293 :
1294 : /* If not, then try the next edge. */
1295 46438 : while (ei_cond (ip->ei, &(ip->e1)))
1296 : {
1297 28910 : basic_block bb = ip->e1->dest;
1298 :
1299 : /* Consider bb as a possible loop header. */
1300 28910 : if ((ip->flags & SUCCS_SKIP_TO_LOOP_EXITS)
1301 3780 : && flag_sel_sched_pipelining_outer_loops
1302 29359 : && (!in_current_region_p (bb)
1303 202 : || BLOCK_TO_BB (ip->bb->index)
1304 202 : < BLOCK_TO_BB (bb->index)))
1305 : {
1306 : /* Get all loop exits recursively. */
1307 402 : ip->loop_exits = get_all_loop_exits (bb);
1308 :
1309 402 : 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 28880 : if (check (ip->e1, ip))
1321 : break;
1322 :
1323 2674 : 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 43764 : 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 43764 : if (ip->e1)
1336 : {
1337 26236 : basic_block bb = ip->e2->dest;
1338 :
1339 26236 : if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun) || bb == after_recovery)
1340 769 : *succp = exit_insn;
1341 : else
1342 : {
1343 25467 : *succp = sel_bb_head (bb);
1344 :
1345 25467 : gcc_assert (ip->flags != SUCCS_NORMAL
1346 : || *succp == NEXT_INSN (bb_note (bb)));
1347 25467 : gcc_assert (BLOCK_FOR_INSN (*succp) == bb);
1348 : }
1349 :
1350 26236 : return true;
1351 : }
1352 : else
1353 : return false;
1354 : }
1355 : }
1356 :
1357 : inline void
1358 37433 : _succ_iter_next (succ_iterator *ip)
1359 : {
1360 37433 : gcc_assert (!ip->e2 || ip->e1);
1361 :
1362 37433 : if (ip->bb_end && ip->e1 && !ip->loop_exits.exists ())
1363 26153 : ei_next (&(ip->ei));
1364 37433 : }
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 28928 : _eligible_successor_edge_p (edge e1, succ_iterator *ip)
1372 : {
1373 28928 : edge e2 = e1;
1374 28928 : basic_block bb;
1375 28928 : int flags = ip->flags;
1376 28928 : bool src_outside_rgn = !in_current_region_p (e1->src);
1377 :
1378 28928 : gcc_assert (flags != 0);
1379 :
1380 28928 : 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 28928 : bb = e2->dest;
1391 :
1392 : /* Skip empty blocks, but be careful not to leave the region. */
1393 29122 : while (1)
1394 : {
1395 29122 : if (!sel_bb_empty_p (bb))
1396 : {
1397 28942 : edge ne;
1398 28942 : basic_block nbb;
1399 :
1400 28942 : if (!sel_bb_empty_or_nop_p (bb))
1401 : break;
1402 :
1403 70 : ne = EDGE_SUCC (bb, 0);
1404 70 : nbb = ne->dest;
1405 :
1406 70 : if (!in_current_region_p (nbb)
1407 70 : && !(flags & SUCCS_OUT))
1408 : break;
1409 :
1410 70 : e2 = ne;
1411 70 : bb = nbb;
1412 70 : continue;
1413 70 : }
1414 :
1415 180 : if (!in_current_region_p (bb)
1416 180 : && !(flags & SUCCS_OUT))
1417 : return false;
1418 :
1419 180 : if (EDGE_COUNT (bb->succs) == 0)
1420 : return false;
1421 :
1422 124 : e2 = EDGE_SUCC (bb, 0);
1423 124 : bb = e2->dest;
1424 : }
1425 :
1426 : /* Save the second edge for later checks. */
1427 28872 : ip->e2 = e2;
1428 :
1429 28872 : 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 17205 : bool succeeds_in_top_order = (BLOCK_TO_BB (ip->bb->index)
1436 17205 : < BLOCK_TO_BB (bb->index));
1437 :
1438 : /* This is true for the all cases except the last one. */
1439 17205 : ip->current_flags = SUCCS_NORMAL;
1440 :
1441 : /* We are advancing forward in the region, as usual. */
1442 17205 : if (succeeds_in_top_order)
1443 : {
1444 : /* We are skipping to loop exits here. */
1445 14839 : gcc_assert (!src_outside_rgn
1446 : || flag_sel_sched_pipelining_outer_loops);
1447 14839 : 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 2366 : if (pipelining_p
1455 1811 : && e1->src->loop_father == bb->loop_father)
1456 1811 : return !!(flags & SUCCS_NORMAL);
1457 :
1458 : /* A back edge should be requested explicitly. */
1459 555 : ip->current_flags = SUCCS_BACK;
1460 555 : return !!(flags & SUCCS_BACK);
1461 : }
1462 :
1463 11667 : ip->current_flags = SUCCS_OUT;
1464 11667 : 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 1562 : bb_next_bb (basic_block bb)
1481 : {
1482 1562 : switch (EDGE_COUNT (bb->succs))
1483 : {
1484 16 : case 0:
1485 16 : return bb->next_bb;
1486 :
1487 487 : case 1:
1488 487 : return single_succ (bb);
1489 :
1490 1051 : case 2:
1491 1051 : return FALLTHRU_EDGE (bb)->dest;
1492 :
1493 8 : default:
1494 8 : 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 */
|
