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