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