OpenCores
URL https://opencores.org/ocsvn/openrisc_me/openrisc_me/trunk

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.5.1/] [gcc/] [sel-sched-ir.h] - Blame information for rev 280

Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.