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

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.5.1/] [gcc/] [sched-int.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) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,
4
   2001, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
5
   Free Software Foundation, Inc.
6
 
7
This file is part of GCC.
8
 
9
GCC is free software; you can redistribute it and/or modify it under
10
the terms of the GNU General Public License as published by the Free
11
Software Foundation; either version 3, or (at your option) any later
12
version.
13
 
14
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15
WARRANTY; without even the implied warranty of MERCHANTABILITY or
16
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
17
for more details.
18
 
19
You should have received a copy of the GNU General Public License
20
along with GCC; see the file COPYING3.  If not see
21
<http://www.gnu.org/licenses/>.  */
22
 
23
#ifndef GCC_SCHED_INT_H
24
#define GCC_SCHED_INT_H
25
 
26
#ifdef INSN_SCHEDULING
27
 
28
/* For state_t.  */
29
#include "insn-attr.h"
30
#include "df.h"
31
#include "basic-block.h"
32
 
33
/* For VEC (int, heap).  */
34
#include "vecprim.h"
35
 
36
/* Identificator of a scheduler pass.  */
37
enum sched_pass_id_t { SCHED_PASS_UNKNOWN, SCHED_RGN_PASS, SCHED_EBB_PASS,
38
                       SCHED_SMS_PASS, SCHED_SEL_PASS };
39
 
40
typedef VEC (basic_block, heap) *bb_vec_t;
41
typedef VEC (rtx, heap) *insn_vec_t;
42
typedef VEC(rtx, heap) *rtx_vec_t;
43
 
44
struct sched_scan_info_def
45
{
46
  /* This hook notifies scheduler frontend to extend its internal per basic
47
     block data structures.  This hook should be called once before a series of
48
     calls to bb_init ().  */
49
  void (*extend_bb) (void);
50
 
51
  /* This hook makes scheduler frontend to initialize its internal data
52
     structures for the passed basic block.  */
53
  void (*init_bb) (basic_block);
54
 
55
  /* This hook notifies scheduler frontend to extend its internal per insn data
56
     structures.  This hook should be called once before a series of calls to
57
     insn_init ().  */
58
  void (*extend_insn) (void);
59
 
60
  /* This hook makes scheduler frontend to initialize its internal data
61
     structures for the passed insn.  */
62
  void (*init_insn) (rtx);
63
};
64
 
65
extern const struct sched_scan_info_def *sched_scan_info;
66
 
67
extern void sched_scan (const struct sched_scan_info_def *,
68
                        bb_vec_t, basic_block, insn_vec_t, rtx);
69
 
70
extern void sched_init_bbs (void);
71
 
72
extern void sched_init_luids (bb_vec_t, basic_block, insn_vec_t, rtx);
73
extern void sched_finish_luids (void);
74
 
75
extern void sched_extend_target (void);
76
 
77
extern void haifa_init_h_i_d (bb_vec_t, basic_block, insn_vec_t, rtx);
78
extern void haifa_finish_h_i_d (void);
79
 
80
/* Hooks that are common to all the schedulers.  */
81
struct common_sched_info_def
82
{
83
  /* Called after blocks were rearranged due to movement of jump instruction.
84
     The first parameter - index of basic block, in which jump currently is.
85
     The second parameter - index of basic block, in which jump used
86
     to be.
87
     The third parameter - index of basic block, that follows the second
88
     parameter.  */
89
  void (*fix_recovery_cfg) (int, int, int);
90
 
91
  /* Called to notify frontend, that new basic block is being added.
92
     The first parameter - new basic block.
93
     The second parameter - block, after which new basic block is being added,
94
     or EXIT_BLOCK_PTR, if recovery block is being added,
95
     or NULL, if standalone block is being added.  */
96
  void (*add_block) (basic_block, basic_block);
97
 
98
  /* Estimate number of insns in the basic block.  */
99
  int (*estimate_number_of_insns) (basic_block);
100
 
101
  /* Given a non-insn (!INSN_P (x)) return
102
     -1 - if this rtx don't need a luid.
103
 
104
     1 - if it needs a separate luid.  */
105
  int (*luid_for_non_insn) (rtx);
106
 
107
  /* Scheduler pass identifier.  It is preferably used in assertions.  */
108
  enum sched_pass_id_t sched_pass_id;
109
};
110
 
111
extern struct common_sched_info_def *common_sched_info;
112
 
113
extern const struct common_sched_info_def haifa_common_sched_info;
114
 
115
/* Return true if selective scheduling pass is working.  */
116
static inline bool
117
sel_sched_p (void)
118
{
119
  return common_sched_info->sched_pass_id == SCHED_SEL_PASS;
120
}
121
 
122
/* Returns maximum priority that an insn was assigned to.  */
123
extern int get_rgn_sched_max_insns_priority (void);
124
 
125
/* Increases effective priority for INSN by AMOUNT.  */
126
extern void sel_add_to_insn_priority (rtx, int);
127
 
128
/* True if during selective scheduling we need to emulate some of haifa
129
   scheduler behaviour.  */
130
extern int sched_emulate_haifa_p;
131
 
132
/* Mapping from INSN_UID to INSN_LUID.  In the end all other per insn data
133
   structures should be indexed by luid.  */
134
extern VEC (int, heap) *sched_luids;
135
#define INSN_LUID(INSN) (VEC_index (int, sched_luids, INSN_UID (INSN)))
136
#define LUID_BY_UID(UID) (VEC_index (int, sched_luids, UID))
137
 
138
#define SET_INSN_LUID(INSN, LUID) \
139
(VEC_replace (int, sched_luids, INSN_UID (INSN), (LUID)))
140
 
141
/* The highest INSN_LUID.  */
142
extern int sched_max_luid;
143
 
144
extern int insn_luid (rtx);
145
 
146
/* This list holds ripped off notes from the current block.  These notes will
147
   be attached to the beginning of the block when its scheduling is
148
   finished.  */
149
extern rtx note_list;
150
 
151
extern void remove_notes (rtx, rtx);
152
extern rtx restore_other_notes (rtx, basic_block);
153
extern void sched_insns_init (rtx);
154
extern void sched_insns_finish (void);
155
 
156
extern void *xrecalloc (void *, size_t, size_t, size_t);
157
extern rtx bb_note (basic_block);
158
 
159
extern void reemit_notes (rtx);
160
 
161
/* Functions in haifa-sched.c.  */
162
extern int haifa_classify_insn (const_rtx);
163
 
164
/* Functions in sel-sched-ir.c.  */
165
extern void sel_find_rgns (void);
166
extern void sel_mark_hard_insn (rtx);
167
 
168
extern size_t dfa_state_size;
169
 
170
extern void advance_state (state_t);
171
 
172
extern void setup_sched_dump (void);
173
extern void sched_init (void);
174
extern void sched_finish (void);
175
 
176
extern bool sel_insn_is_speculation_check (rtx);
177
 
178
/* Describe the ready list of the scheduler.
179
   VEC holds space enough for all insns in the current region.  VECLEN
180
   says how many exactly.
181
   FIRST is the index of the element with the highest priority; i.e. the
182
   last one in the ready list, since elements are ordered by ascending
183
   priority.
184
   N_READY determines how many insns are on the ready list.
185
   N_DEBUG determines how many debug insns are on the ready list.  */
186
struct ready_list
187
{
188
  rtx *vec;
189
  int veclen;
190
  int first;
191
  int n_ready;
192
  int n_debug;
193
};
194
 
195
extern char *ready_try;
196
extern struct ready_list ready;
197
 
198
extern int max_issue (struct ready_list *, int, state_t, int *);
199
 
200
extern void ebb_compute_jump_reg_dependencies (rtx, regset, regset, regset);
201
 
202
extern edge find_fallthru_edge (basic_block);
203
 
204
extern void (* sched_init_only_bb) (basic_block, basic_block);
205
extern basic_block (* sched_split_block) (basic_block, rtx);
206
extern basic_block sched_split_block_1 (basic_block, rtx);
207
extern basic_block (* sched_create_empty_bb) (basic_block);
208
extern basic_block sched_create_empty_bb_1 (basic_block);
209
 
210
extern basic_block sched_create_recovery_block (basic_block *);
211
extern void sched_create_recovery_edges (basic_block, basic_block,
212
                                         basic_block);
213
 
214
/* Pointer to data describing the current DFA state.  */
215
extern state_t curr_state;
216
 
217
/* Type to represent status of a dependence.  */
218
typedef int ds_t;
219
 
220
/* Type to represent weakness of speculative dependence.  */
221
typedef int dw_t;
222
 
223
extern enum reg_note ds_to_dk (ds_t);
224
extern ds_t dk_to_ds (enum reg_note);
225
 
226
/* Information about the dependency.  */
227
struct _dep
228
{
229
  /* Producer.  */
230
  rtx pro;
231
 
232
  /* Consumer.  */
233
  rtx con;
234
 
235
  /* Dependency major type.  This field is superseded by STATUS below.
236
     Though, it is still in place because some targets use it.  */
237
  enum reg_note type;
238
 
239
  /* Dependency status.  This field holds all dependency types and additional
240
     information for speculative dependencies.  */
241
  ds_t status;
242
};
243
 
244
typedef struct _dep dep_def;
245
typedef dep_def *dep_t;
246
 
247
#define DEP_PRO(D) ((D)->pro)
248
#define DEP_CON(D) ((D)->con)
249
#define DEP_TYPE(D) ((D)->type)
250
#define DEP_STATUS(D) ((D)->status)
251
 
252
/* Functions to work with dep.  */
253
 
254
extern void init_dep_1 (dep_t, rtx, rtx, enum reg_note, ds_t);
255
extern void init_dep (dep_t, rtx, rtx, enum reg_note);
256
 
257
extern void sd_debug_dep (dep_t);
258
 
259
/* Definition of this struct resides below.  */
260
struct _dep_node;
261
typedef struct _dep_node *dep_node_t;
262
 
263
/* A link in the dependency list.  This is essentially an equivalent of a
264
   single {INSN, DEPS}_LIST rtx.  */
265
struct _dep_link
266
{
267
  /* Dep node with all the data.  */
268
  dep_node_t node;
269
 
270
  /* Next link in the list. For the last one it is NULL.  */
271
  struct _dep_link *next;
272
 
273
  /* Pointer to the next field of the previous link in the list.
274
     For the first link this points to the deps_list->first.
275
 
276
     With help of this field it is easy to remove and insert links to the
277
     list.  */
278
  struct _dep_link **prev_nextp;
279
};
280
typedef struct _dep_link *dep_link_t;
281
 
282
#define DEP_LINK_NODE(N) ((N)->node)
283
#define DEP_LINK_NEXT(N) ((N)->next)
284
#define DEP_LINK_PREV_NEXTP(N) ((N)->prev_nextp)
285
 
286
/* Macros to work dep_link.  For most usecases only part of the dependency
287
   information is need.  These macros conveniently provide that piece of
288
   information.  */
289
 
290
#define DEP_LINK_DEP(N) (DEP_NODE_DEP (DEP_LINK_NODE (N)))
291
#define DEP_LINK_PRO(N) (DEP_PRO (DEP_LINK_DEP (N)))
292
#define DEP_LINK_CON(N) (DEP_CON (DEP_LINK_DEP (N)))
293
#define DEP_LINK_TYPE(N) (DEP_TYPE (DEP_LINK_DEP (N)))
294
#define DEP_LINK_STATUS(N) (DEP_STATUS (DEP_LINK_DEP (N)))
295
 
296
/* A list of dep_links.  */
297
struct _deps_list
298
{
299
  /* First element.  */
300
  dep_link_t first;
301
 
302
  /* Total number of elements in the list.  */
303
  int n_links;
304
};
305
typedef struct _deps_list *deps_list_t;
306
 
307
#define DEPS_LIST_FIRST(L) ((L)->first)
308
#define DEPS_LIST_N_LINKS(L) ((L)->n_links)
309
 
310
/* Suppose we have a dependence Y between insn pro1 and con1, where pro1 has
311
   additional dependents con0 and con2, and con1 is dependent on additional
312
   insns pro0 and pro1:
313
 
314
   .con0      pro0
315
   . ^         |
316
   . |         |
317
   . |         |
318
   . X         A
319
   . |         |
320
   . |         |
321
   . |         V
322
   .pro1--Y-->con1
323
   . |         ^
324
   . |         |
325
   . |         |
326
   . Z         B
327
   . |         |
328
   . |         |
329
   . V         |
330
   .con2      pro2
331
 
332
   This is represented using a "dep_node" for each dependence arc, which are
333
   connected as follows (diagram is centered around Y which is fully shown;
334
   other dep_nodes shown partially):
335
 
336
   .          +------------+    +--------------+    +------------+
337
   .          : dep_node X :    |  dep_node Y  |    : dep_node Z :
338
   .          :            :    |              |    :            :
339
   .          :            :    |              |    :            :
340
   .          : forw       :    |  forw        |    : forw       :
341
   .          : +--------+ :    |  +--------+  |    : +--------+ :
342
   forw_deps  : |dep_link| :    |  |dep_link|  |    : |dep_link| :
343
   +-----+    : | +----+ | :    |  | +----+ |  |    : | +----+ | :
344
   |first|----->| |next|-+------+->| |next|-+--+----->| |next|-+--->NULL
345
   +-----+    : | +----+ | :    |  | +----+ |  |    : | +----+ | :
346
   . ^  ^     : |     ^  | :    |  |     ^  |  |    : |        | :
347
   . |  |     : |     |  | :    |  |     |  |  |    : |        | :
348
   . |  +--<----+--+  +--+---<--+--+--+  +--+--+--<---+--+     | :
349
   . |        : |  |     | :    |  |  |     |  |    : |  |     | :
350
   . |        : | +----+ | :    |  | +----+ |  |    : | +----+ | :
351
   . |        : | |prev| | :    |  | |prev| |  |    : | |prev| | :
352
   . |        : | |next| | :    |  | |next| |  |    : | |next| | :
353
   . |        : | +----+ | :    |  | +----+ |  |    : | +----+ | :
354
   . |        : |        | :<-+ |  |        |  |<-+ : |        | :<-+
355
   . |        : | +----+ | :  | |  | +----+ |  |  | : | +----+ | :  |
356
   . |        : | |node|-+----+ |  | |node|-+--+--+ : | |node|-+----+
357
   . |        : | +----+ | :    |  | +----+ |  |    : | +----+ | :
358
   . |        : |        | :    |  |        |  |    : |        | :
359
   . |        : +--------+ :    |  +--------+  |    : +--------+ :
360
   . |        :            :    |              |    :            :
361
   . |        :  SAME pro1 :    |  +--------+  |    :  SAME pro1 :
362
   . |        :  DIFF con0 :    |  |dep     |  |    :  DIFF con2 :
363
   . |        :            :    |  |        |  |    :            :
364
   . |                          |  | +----+ |  |
365
   .RTX<------------------------+--+-|pro1| |  |
366
   .pro1                        |  | +----+ |  |
367
   .                            |  |        |  |
368
   .                            |  | +----+ |  |
369
   .RTX<------------------------+--+-|con1| |  |
370
   .con1                        |  | +----+ |  |
371
   . |                          |  |        |  |
372
   . |                          |  | +----+ |  |
373
   . |                          |  | |kind| |  |
374
   . |                          |  | +----+ |  |
375
   . |        :            :    |  | |stat| |  |    :            :
376
   . |        :  DIFF pro0 :    |  | +----+ |  |    :  DIFF pro2 :
377
   . |        :  SAME con1 :    |  |        |  |    :  SAME con1 :
378
   . |        :            :    |  +--------+  |    :            :
379
   . |        :            :    |              |    :            :
380
   . |        : back       :    |  back        |    : back       :
381
   . v        : +--------+ :    |  +--------+  |    : +--------+ :
382
   back_deps  : |dep_link| :    |  |dep_link|  |    : |dep_link| :
383
   +-----+    : | +----+ | :    |  | +----+ |  |    : | +----+ | :
384
   |first|----->| |next|-+------+->| |next|-+--+----->| |next|-+--->NULL
385
   +-----+    : | +----+ | :    |  | +----+ |  |    : | +----+ | :
386
   .    ^     : |     ^  | :    |  |     ^  |  |    : |        | :
387
   .    |     : |     |  | :    |  |     |  |  |    : |        | :
388
   .    +--<----+--+  +--+---<--+--+--+  +--+--+--<---+--+     | :
389
   .          : |  |     | :    |  |  |     |  |    : |  |     | :
390
   .          : | +----+ | :    |  | +----+ |  |    : | +----+ | :
391
   .          : | |prev| | :    |  | |prev| |  |    : | |prev| | :
392
   .          : | |next| | :    |  | |next| |  |    : | |next| | :
393
   .          : | +----+ | :    |  | +----+ |  |    : | +----+ | :
394
   .          : |        | :<-+ |  |        |  |<-+ : |        | :<-+
395
   .          : | +----+ | :  | |  | +----+ |  |  | : | +----+ | :  |
396
   .          : | |node|-+----+ |  | |node|-+--+--+ : | |node|-+----+
397
   .          : | +----+ | :    |  | +----+ |  |    : | +----+ | :
398
   .          : |        | :    |  |        |  |    : |        | :
399
   .          : +--------+ :    |  +--------+  |    : +--------+ :
400
   .          :            :    |              |    :            :
401
   .          : dep_node A :    |  dep_node Y  |    : dep_node B :
402
   .          +------------+    +--------------+    +------------+
403
*/
404
 
405
struct _dep_node
406
{
407
  /* Backward link.  */
408
  struct _dep_link back;
409
 
410
  /* The dep.  */
411
  struct _dep dep;
412
 
413
  /* Forward link.  */
414
  struct _dep_link forw;
415
};
416
 
417
#define DEP_NODE_BACK(N) (&(N)->back)
418
#define DEP_NODE_DEP(N) (&(N)->dep)
419
#define DEP_NODE_FORW(N) (&(N)->forw)
420
 
421
/* The following enumeration values tell us what dependencies we
422
   should use to implement the barrier.  We use true-dependencies for
423
   TRUE_BARRIER and anti-dependencies for MOVE_BARRIER.  */
424
enum reg_pending_barrier_mode
425
{
426
  NOT_A_BARRIER = 0,
427
  MOVE_BARRIER,
428
  TRUE_BARRIER
429
};
430
 
431
/* Whether a register movement is associated with a call.  */
432
enum post_call_group
433
{
434
  not_post_call,
435
  post_call,
436
  post_call_initial
437
};
438
 
439
/* Insns which affect pseudo-registers.  */
440
struct deps_reg
441
{
442
  rtx uses;
443
  rtx sets;
444
  rtx implicit_sets;
445
  rtx clobbers;
446
  int uses_length;
447
  int clobbers_length;
448
};
449
 
450
/* Describe state of dependencies used during sched_analyze phase.  */
451
struct deps_desc
452
{
453
  /* The *_insns and *_mems are paired lists.  Each pending memory operation
454
     will have a pointer to the MEM rtx on one list and a pointer to the
455
     containing insn on the other list in the same place in the list.  */
456
 
457
  /* We can't use add_dependence like the old code did, because a single insn
458
     may have multiple memory accesses, and hence needs to be on the list
459
     once for each memory access.  Add_dependence won't let you add an insn
460
     to a list more than once.  */
461
 
462
  /* An INSN_LIST containing all insns with pending read operations.  */
463
  rtx pending_read_insns;
464
 
465
  /* An EXPR_LIST containing all MEM rtx's which are pending reads.  */
466
  rtx pending_read_mems;
467
 
468
  /* An INSN_LIST containing all insns with pending write operations.  */
469
  rtx pending_write_insns;
470
 
471
  /* An EXPR_LIST containing all MEM rtx's which are pending writes.  */
472
  rtx pending_write_mems;
473
 
474
  /* We must prevent the above lists from ever growing too large since
475
     the number of dependencies produced is at least O(N*N),
476
     and execution time is at least O(4*N*N), as a function of the
477
     length of these pending lists.  */
478
 
479
  /* Indicates the length of the pending_read list.  */
480
  int pending_read_list_length;
481
 
482
  /* Indicates the length of the pending_write list.  */
483
  int pending_write_list_length;
484
 
485
  /* Length of the pending memory flush list. Large functions with no
486
     calls may build up extremely large lists.  */
487
  int pending_flush_length;
488
 
489
  /* The last insn upon which all memory references must depend.
490
     This is an insn which flushed the pending lists, creating a dependency
491
     between it and all previously pending memory references.  This creates
492
     a barrier (or a checkpoint) which no memory reference is allowed to cross.
493
 
494
     This includes all non constant CALL_INSNs.  When we do interprocedural
495
     alias analysis, this restriction can be relaxed.
496
     This may also be an INSN that writes memory if the pending lists grow
497
     too large.  */
498
  rtx last_pending_memory_flush;
499
 
500
  /* A list of the last function calls we have seen.  We use a list to
501
     represent last function calls from multiple predecessor blocks.
502
     Used to prevent register lifetimes from expanding unnecessarily.  */
503
  rtx last_function_call;
504
 
505
  /* A list of the last function calls that may not return normally
506
     we have seen.  We use a list to represent last function calls from
507
     multiple predecessor blocks.  Used to prevent moving trapping insns
508
     across such calls.  */
509
  rtx last_function_call_may_noreturn;
510
 
511
  /* A list of insns which use a pseudo register that does not already
512
     cross a call.  We create dependencies between each of those insn
513
     and the next call insn, to ensure that they won't cross a call after
514
     scheduling is done.  */
515
  rtx sched_before_next_call;
516
 
517
  /* Used to keep post-call pseudo/hard reg movements together with
518
     the call.  */
519
  enum post_call_group in_post_call_group_p;
520
 
521
  /* The last debug insn we've seen.  */
522
  rtx last_debug_insn;
523
 
524
  /* The maximum register number for the following arrays.  Before reload
525
     this is max_reg_num; after reload it is FIRST_PSEUDO_REGISTER.  */
526
  int max_reg;
527
 
528
  /* Element N is the next insn that sets (hard or pseudo) register
529
     N within the current basic block; or zero, if there is no
530
     such insn.  Needed for new registers which may be introduced
531
     by splitting insns.  */
532
  struct deps_reg *reg_last;
533
 
534
  /* Element N is set for each register that has any nonzero element
535
     in reg_last[N].{uses,sets,clobbers}.  */
536
  regset_head reg_last_in_use;
537
 
538
  /* Element N is set for each register that is conditionally set.  */
539
  regset_head reg_conditional_sets;
540
 
541
  /* Shows the last value of reg_pending_barrier associated with the insn.  */
542
  enum reg_pending_barrier_mode last_reg_pending_barrier;
543
 
544
  /* True when this context should be treated as a readonly by
545
     the analysis.  */
546
  BOOL_BITFIELD readonly : 1;
547
};
548
 
549
typedef struct deps_desc *deps_t;
550
 
551
/* This structure holds some state of the current scheduling pass, and
552
   contains some function pointers that abstract out some of the non-generic
553
   functionality from functions such as schedule_block or schedule_insn.
554
   There is one global variable, current_sched_info, which points to the
555
   sched_info structure currently in use.  */
556
struct haifa_sched_info
557
{
558
  /* Add all insns that are initially ready to the ready list.  Called once
559
     before scheduling a set of insns.  */
560
  void (*init_ready_list) (void);
561
  /* Called after taking an insn from the ready list.  Returns nonzero if
562
     this insn can be scheduled, nonzero if we should silently discard it.  */
563
  int (*can_schedule_ready_p) (rtx);
564
  /* Return nonzero if there are more insns that should be scheduled.  */
565
  int (*schedule_more_p) (void);
566
  /* Called after an insn has all its hard dependencies resolved.
567
     Adjusts status of instruction (which is passed through second parameter)
568
     to indicate if instruction should be moved to the ready list or the
569
     queue, or if it should silently discard it (until next resolved
570
     dependence).  */
571
  ds_t (*new_ready) (rtx, ds_t);
572
  /* Compare priority of two insns.  Return a positive number if the second
573
     insn is to be preferred for scheduling, and a negative one if the first
574
     is to be preferred.  Zero if they are equally good.  */
575
  int (*rank) (rtx, rtx);
576
  /* Return a string that contains the insn uid and optionally anything else
577
     necessary to identify this insn in an output.  It's valid to use a
578
     static buffer for this.  The ALIGNED parameter should cause the string
579
     to be formatted so that multiple output lines will line up nicely.  */
580
  const char *(*print_insn) (const_rtx, int);
581
  /* Return nonzero if an insn should be included in priority
582
     calculations.  */
583
  int (*contributes_to_priority) (rtx, rtx);
584
 
585
  /* Return true if scheduling insn (passed as the parameter) will trigger
586
     finish of scheduling current block.  */
587
  bool (*insn_finishes_block_p) (rtx);
588
 
589
  /* The boundaries of the set of insns to be scheduled.  */
590
  rtx prev_head, next_tail;
591
 
592
  /* Filled in after the schedule is finished; the first and last scheduled
593
     insns.  */
594
  rtx head, tail;
595
 
596
  /* If nonzero, enables an additional sanity check in schedule_block.  */
597
  unsigned int queue_must_finish_empty:1;
598
 
599
  /* Maximum priority that has been assigned to an insn.  */
600
  int sched_max_insns_priority;
601
 
602
  /* Hooks to support speculative scheduling.  */
603
 
604
  /* Called to notify frontend that instruction is being added (second
605
     parameter == 0) or removed (second parameter == 1).  */
606
  void (*add_remove_insn) (rtx, int);
607
 
608
  /* Called to notify frontend that instruction is being scheduled.
609
     The first parameter - instruction to scheduled, the second parameter -
610
     last scheduled instruction.  */
611
  void (*begin_schedule_ready) (rtx, rtx);
612
 
613
  /* If the second parameter is not NULL, return nonnull value, if the
614
     basic block should be advanced.
615
     If the second parameter is NULL, return the next basic block in EBB.
616
     The first parameter is the current basic block in EBB.  */
617
  basic_block (*advance_target_bb) (basic_block, rtx);
618
 
619
  /* ??? FIXME: should use straight bitfields inside sched_info instead of
620
     this flag field.  */
621
  unsigned int flags;
622
};
623
 
624
/* This structure holds description of the properties for speculative
625
   scheduling.  */
626
struct spec_info_def
627
{
628
  /* Holds types of allowed speculations: BEGIN_{DATA|CONTROL},
629
     BE_IN_{DATA_CONTROL}.  */
630
  int mask;
631
 
632
  /* A dump file for additional information on speculative scheduling.  */
633
  FILE *dump;
634
 
635
  /* Minimal cumulative weakness of speculative instruction's
636
     dependencies, so that insn will be scheduled.  */
637
  dw_t data_weakness_cutoff;
638
 
639
  /* Minimal usefulness of speculative instruction to be considered for
640
     scheduling.  */
641
  int control_weakness_cutoff;
642
 
643
  /* Flags from the enum SPEC_SCHED_FLAGS.  */
644
  int flags;
645
};
646
typedef struct spec_info_def *spec_info_t;
647
 
648
extern spec_info_t spec_info;
649
 
650
extern struct haifa_sched_info *current_sched_info;
651
 
652
/* Do register pressure sensitive insn scheduling if the flag is set
653
   up.  */
654
extern bool sched_pressure_p;
655
 
656
/* Map regno -> its cover class.  The map defined only when
657
   SCHED_PRESSURE_P is true.  */
658
extern enum reg_class *sched_regno_cover_class;
659
 
660
/* Indexed by INSN_UID, the collection of all data associated with
661
   a single instruction.  */
662
 
663
struct _haifa_deps_insn_data
664
{
665
  /* The number of incoming edges in the forward dependency graph.
666
     As scheduling proceeds, counts are decreased.  An insn moves to
667
     the ready queue when its counter reaches zero.  */
668
  int dep_count;
669
 
670
  /* Nonzero if instruction has internal dependence
671
     (e.g. add_dependence was invoked with (insn == elem)).  */
672
  unsigned int has_internal_dep;
673
 
674
  /* NB: We can't place 'struct _deps_list' here instead of deps_list_t into
675
     h_i_d because when h_i_d extends, addresses of the deps_list->first
676
     change without updating deps_list->first->next->prev_nextp.  Thus
677
     BACK_DEPS and RESOLVED_BACK_DEPS are allocated on the heap and FORW_DEPS
678
     list is allocated on the obstack.  */
679
 
680
  /* A list of hard backward dependencies.  The insn is a consumer of all the
681
     deps mentioned here.  */
682
  deps_list_t hard_back_deps;
683
 
684
  /* A list of speculative (weak) dependencies.  The insn is a consumer of all
685
     the deps mentioned here.  */
686
  deps_list_t spec_back_deps;
687
 
688
  /* A list of insns which depend on the instruction.  Unlike 'back_deps',
689
     it represents forward dependencies.  */
690
  deps_list_t forw_deps;
691
 
692
  /* A list of scheduled producers of the instruction.  Links are being moved
693
     from 'back_deps' to 'resolved_back_deps' while scheduling.  */
694
  deps_list_t resolved_back_deps;
695
 
696
  /* A list of scheduled consumers of the instruction.  Links are being moved
697
     from 'forw_deps' to 'resolved_forw_deps' while scheduling to fasten the
698
     search in 'forw_deps'.  */
699
  deps_list_t resolved_forw_deps;
700
 
701
  /* Some insns (e.g. call) are not allowed to move across blocks.  */
702
  unsigned int cant_move : 1;
703
};
704
 
705
/* Bits used for storing values of the fields in the following
706
   structure.  */
707
#define INCREASE_BITS 8
708
 
709
/* The structure describes how the corresponding insn increases the
710
   register pressure for each cover class.  */
711
struct reg_pressure_data
712
{
713
  /* Pressure increase for given class because of clobber.  */
714
  unsigned int clobber_increase : INCREASE_BITS;
715
  /* Increase in register pressure for given class because of register
716
     sets. */
717
  unsigned int set_increase : INCREASE_BITS;
718
  /* Pressure increase for given class because of unused register
719
     set.  */
720
  unsigned int unused_set_increase : INCREASE_BITS;
721
  /* Pressure change: #sets - #deaths.  */
722
  int change : INCREASE_BITS;
723
};
724
 
725
/* The following structure describes usage of registers by insns.  */
726
struct reg_use_data
727
{
728
  /* Regno used in the insn.  */
729
  int regno;
730
  /* Insn using the regno.  */
731
  rtx insn;
732
  /* Cyclic list of elements with the same regno.  */
733
  struct reg_use_data *next_regno_use;
734
  /* List of elements with the same insn.  */
735
  struct reg_use_data *next_insn_use;
736
};
737
 
738
/* The following structure describes used sets of registers by insns.
739
   Registers are pseudos whose cover class is not NO_REGS or hard
740
   registers available for allocations.  */
741
struct reg_set_data
742
{
743
  /* Regno used in the insn.  */
744
  int regno;
745
  /* Insn setting the regno.  */
746
  rtx insn;
747
  /* List of elements with the same insn.  */
748
  struct reg_set_data *next_insn_set;
749
};
750
 
751
struct _haifa_insn_data
752
{
753
  /* We can't place 'struct _deps_list' into h_i_d instead of deps_list_t
754
     because when h_i_d extends, addresses of the deps_list->first
755
     change without updating deps_list->first->next->prev_nextp.  */
756
 
757
  /* Logical uid gives the original ordering of the insns.  */
758
  int luid;
759
 
760
  /* A priority for each insn.  */
761
  int priority;
762
 
763
  /* The minimum clock tick at which the insn becomes ready.  This is
764
     used to note timing constraints for the insns in the pending list.  */
765
  int tick;
766
 
767
  /* INTER_TICK is used to adjust INSN_TICKs of instructions from the
768
     subsequent blocks in a region.  */
769
  int inter_tick;
770
 
771
  /* See comment on QUEUE_INDEX macro in haifa-sched.c.  */
772
  int queue_index;
773
 
774
  short cost;
775
 
776
  /* Set if there's DEF-USE dependence between some speculatively
777
     moved load insn and this one.  */
778
  unsigned int fed_by_spec_load : 1;
779
  unsigned int is_load_insn : 1;
780
 
781
  /* '> 0' if priority is valid,
782
     '== 0' if priority was not yet computed,
783
     '< 0' if priority in invalid and should be recomputed.  */
784
  signed char priority_status;
785
 
786
  /* What speculations are necessary to apply to schedule the instruction.  */
787
  ds_t todo_spec;
788
 
789
  /* What speculations were already applied.  */
790
  ds_t done_spec;
791
 
792
  /* What speculations are checked by this instruction.  */
793
  ds_t check_spec;
794
 
795
  /* Recovery block for speculation checks.  */
796
  basic_block recovery_block;
797
 
798
  /* Original pattern of the instruction.  */
799
  rtx orig_pat;
800
 
801
  /* The following array contains info how the insn increases register
802
     pressure.  There is an element for each cover class of pseudos
803
     referenced in insns.  */
804
  struct reg_pressure_data *reg_pressure;
805
  /* The following array contains maximal reg pressure between last
806
     scheduled insn and given insn.  There is an element for each
807
     cover class of pseudos referenced in insns.  This info updated
808
     after scheduling each insn for each insn between the two
809
     mentioned insns.  */
810
  int *max_reg_pressure;
811
  /* The following list contains info about used pseudos and hard
812
     registers available for allocation.  */
813
  struct reg_use_data *reg_use_list;
814
  /* The following list contains info about set pseudos and hard
815
     registers available for allocation.  */
816
  struct reg_set_data *reg_set_list;
817
  /* Info about how scheduling the insn changes cost of register
818
     pressure excess (between source and target).  */
819
  int reg_pressure_excess_cost_change;
820
};
821
 
822
typedef struct _haifa_insn_data haifa_insn_data_def;
823
typedef haifa_insn_data_def *haifa_insn_data_t;
824
 
825
DEF_VEC_O (haifa_insn_data_def);
826
DEF_VEC_ALLOC_O (haifa_insn_data_def, heap);
827
 
828
extern VEC(haifa_insn_data_def, heap) *h_i_d;
829
 
830
#define HID(INSN) (VEC_index (haifa_insn_data_def, h_i_d, INSN_UID (INSN)))
831
 
832
/* Accessor macros for h_i_d.  There are more in haifa-sched.c and
833
   sched-rgn.c.  */
834
#define INSN_PRIORITY(INSN) (HID (INSN)->priority)
835
#define INSN_REG_PRESSURE(INSN) (HID (INSN)->reg_pressure)
836
#define INSN_MAX_REG_PRESSURE(INSN) (HID (INSN)->max_reg_pressure)
837
#define INSN_REG_USE_LIST(INSN) (HID (INSN)->reg_use_list)
838
#define INSN_REG_SET_LIST(INSN) (HID (INSN)->reg_set_list)
839
#define INSN_REG_PRESSURE_EXCESS_COST_CHANGE(INSN) \
840
  (HID (INSN)->reg_pressure_excess_cost_change)
841
#define INSN_PRIORITY_STATUS(INSN) (HID (INSN)->priority_status)
842
 
843
typedef struct _haifa_deps_insn_data haifa_deps_insn_data_def;
844
typedef haifa_deps_insn_data_def *haifa_deps_insn_data_t;
845
 
846
DEF_VEC_O (haifa_deps_insn_data_def);
847
DEF_VEC_ALLOC_O (haifa_deps_insn_data_def, heap);
848
 
849
extern VEC(haifa_deps_insn_data_def, heap) *h_d_i_d;
850
 
851
#define HDID(INSN) (VEC_index (haifa_deps_insn_data_def, h_d_i_d,       \
852
                               INSN_LUID (INSN)))
853
#define INSN_DEP_COUNT(INSN)    (HDID (INSN)->dep_count)
854
#define HAS_INTERNAL_DEP(INSN)  (HDID (INSN)->has_internal_dep)
855
#define INSN_FORW_DEPS(INSN) (HDID (INSN)->forw_deps)
856
#define INSN_RESOLVED_BACK_DEPS(INSN) (HDID (INSN)->resolved_back_deps)
857
#define INSN_RESOLVED_FORW_DEPS(INSN) (HDID (INSN)->resolved_forw_deps)
858
#define INSN_HARD_BACK_DEPS(INSN) (HDID (INSN)->hard_back_deps)
859
#define INSN_SPEC_BACK_DEPS(INSN) (HDID (INSN)->spec_back_deps)
860
#define CANT_MOVE(INSN) (HDID (INSN)->cant_move)
861
#define CANT_MOVE_BY_LUID(LUID) (VEC_index (haifa_deps_insn_data_def, h_d_i_d, \
862
                                            LUID)->cant_move)
863
 
864
 
865
#define INSN_PRIORITY(INSN)     (HID (INSN)->priority)
866
#define INSN_PRIORITY_STATUS(INSN) (HID (INSN)->priority_status)
867
#define INSN_PRIORITY_KNOWN(INSN) (INSN_PRIORITY_STATUS (INSN) > 0)
868
#define TODO_SPEC(INSN) (HID (INSN)->todo_spec)
869
#define DONE_SPEC(INSN) (HID (INSN)->done_spec)
870
#define CHECK_SPEC(INSN) (HID (INSN)->check_spec)
871
#define RECOVERY_BLOCK(INSN) (HID (INSN)->recovery_block)
872
#define ORIG_PAT(INSN) (HID (INSN)->orig_pat)
873
 
874
/* INSN is either a simple or a branchy speculation check.  */
875
#define IS_SPECULATION_CHECK_P(INSN) \
876
  (sel_sched_p () ? sel_insn_is_speculation_check (INSN) : RECOVERY_BLOCK (INSN) != NULL)
877
 
878
/* INSN is a speculation check that will simply reexecute the speculatively
879
   scheduled instruction if the speculation fails.  */
880
#define IS_SPECULATION_SIMPLE_CHECK_P(INSN) \
881
  (RECOVERY_BLOCK (INSN) == EXIT_BLOCK_PTR)
882
 
883
/* INSN is a speculation check that will branch to RECOVERY_BLOCK if the
884
   speculation fails.  Insns in that block will reexecute the speculatively
885
   scheduled code and then will return immediately after INSN thus preserving
886
   semantics of the program.  */
887
#define IS_SPECULATION_BRANCHY_CHECK_P(INSN) \
888
  (RECOVERY_BLOCK (INSN) != NULL && RECOVERY_BLOCK (INSN) != EXIT_BLOCK_PTR)
889
 
890
/* The unchanging bit tracks whether a debug insn is to be handled
891
   like an insn (i.e., schedule it) or like a note (e.g., it is next
892
   to a basic block boundary.  */
893
#define DEBUG_INSN_SCHED_P(insn) \
894
  (RTL_FLAG_CHECK1("DEBUG_INSN_SCHED_P", (insn), DEBUG_INSN)->unchanging)
895
 
896
/* True if INSN is a debug insn that is next to a basic block
897
   boundary, i.e., it is to be handled by the scheduler like a
898
   note.  */
899
#define BOUNDARY_DEBUG_INSN_P(insn) \
900
  (DEBUG_INSN_P (insn) && !DEBUG_INSN_SCHED_P (insn))
901
/* True if INSN is a debug insn that is not next to a basic block
902
   boundary, i.e., it is to be handled by the scheduler like an
903
   insn.  */
904
#define SCHEDULE_DEBUG_INSN_P(insn) \
905
  (DEBUG_INSN_P (insn) && DEBUG_INSN_SCHED_P (insn))
906
 
907
/* Dep status (aka ds_t) of the link encapsulates information, that is needed
908
   for speculative scheduling.  Namely, it is 4 integers in the range
909
   [0, MAX_DEP_WEAK] and 3 bits.
910
   The integers correspond to the probability of the dependence to *not*
911
   exist, it is the probability, that overcoming of this dependence will
912
   not be followed by execution of the recovery code.  Nevertheless,
913
   whatever high the probability of success is, recovery code should still
914
   be generated to preserve semantics of the program.  To find a way to
915
   get/set these integers, please refer to the {get, set}_dep_weak ()
916
   functions in sched-deps.c .
917
   The 3 bits in the DEP_STATUS correspond to 3 dependence types: true-,
918
   output- and anti- dependence.  It is not enough for speculative scheduling
919
   to know just the major type of all the dependence between two instructions,
920
   as only true dependence can be overcome.
921
   There also is the 4-th bit in the DEP_STATUS (HARD_DEP), that is reserved
922
   for using to describe instruction's status.  It is set whenever instruction
923
   has at least one dependence, that cannot be overcame.
924
   See also: check_dep_status () in sched-deps.c .  */
925
 
926
/* We exclude sign bit.  */
927
#define BITS_PER_DEP_STATUS (HOST_BITS_PER_INT - 1)
928
 
929
/* First '4' stands for 3 dep type bits and HARD_DEP bit.
930
   Second '4' stands for BEGIN_{DATA, CONTROL}, BE_IN_{DATA, CONTROL}
931
   dep weakness.  */
932
#define BITS_PER_DEP_WEAK ((BITS_PER_DEP_STATUS - 4) / 4)
933
 
934
/* Mask of speculative weakness in dep_status.  */
935
#define DEP_WEAK_MASK ((1 << BITS_PER_DEP_WEAK) - 1)
936
 
937
/* This constant means that dependence is fake with 99.999...% probability.
938
   This is the maximum value, that can appear in dep_status.
939
   Note, that we don't want MAX_DEP_WEAK to be the same as DEP_WEAK_MASK for
940
   debugging reasons.  Though, it can be set to DEP_WEAK_MASK, and, when
941
   done so, we'll get fast (mul for)/(div by) NO_DEP_WEAK.  */
942
#define MAX_DEP_WEAK (DEP_WEAK_MASK - 1)
943
 
944
/* This constant means that dependence is 99.999...% real and it is a really
945
   bad idea to overcome it (though this can be done, preserving program
946
   semantics).  */
947
#define MIN_DEP_WEAK 1
948
 
949
/* This constant represents 100% probability.
950
   E.g. it is used to represent weakness of dependence, that doesn't exist.  */
951
#define NO_DEP_WEAK (MAX_DEP_WEAK + MIN_DEP_WEAK)
952
 
953
/* Default weakness of speculative dependence.  Used when we can't say
954
   neither bad nor good about the dependence.  */
955
#define UNCERTAIN_DEP_WEAK (MAX_DEP_WEAK - MAX_DEP_WEAK / 4)
956
 
957
/* Offset for speculative weaknesses in dep_status.  */
958
enum SPEC_TYPES_OFFSETS {
959
  BEGIN_DATA_BITS_OFFSET = 0,
960
  BE_IN_DATA_BITS_OFFSET = BEGIN_DATA_BITS_OFFSET + BITS_PER_DEP_WEAK,
961
  BEGIN_CONTROL_BITS_OFFSET = BE_IN_DATA_BITS_OFFSET + BITS_PER_DEP_WEAK,
962
  BE_IN_CONTROL_BITS_OFFSET = BEGIN_CONTROL_BITS_OFFSET + BITS_PER_DEP_WEAK
963
};
964
 
965
/* The following defines provide numerous constants used to distinguish between
966
   different types of speculative dependencies.  */
967
 
968
/* Dependence can be overcome with generation of new data speculative
969
   instruction.  */
970
#define BEGIN_DATA (((ds_t) DEP_WEAK_MASK) << BEGIN_DATA_BITS_OFFSET)
971
 
972
/* This dependence is to the instruction in the recovery block, that was
973
   formed to recover after data-speculation failure.
974
   Thus, this dependence can overcome with generating of the copy of
975
   this instruction in the recovery block.  */
976
#define BE_IN_DATA (((ds_t) DEP_WEAK_MASK) << BE_IN_DATA_BITS_OFFSET)
977
 
978
/* Dependence can be overcome with generation of new control speculative
979
   instruction.  */
980
#define BEGIN_CONTROL (((ds_t) DEP_WEAK_MASK) << BEGIN_CONTROL_BITS_OFFSET)
981
 
982
/* This dependence is to the instruction in the recovery block, that was
983
   formed to recover after control-speculation failure.
984
   Thus, this dependence can be overcome with generating of the copy of
985
   this instruction in the recovery block.  */
986
#define BE_IN_CONTROL (((ds_t) DEP_WEAK_MASK) << BE_IN_CONTROL_BITS_OFFSET)
987
 
988
/* A few convenient combinations.  */
989
#define BEGIN_SPEC (BEGIN_DATA | BEGIN_CONTROL)
990
#define DATA_SPEC (BEGIN_DATA | BE_IN_DATA)
991
#define CONTROL_SPEC (BEGIN_CONTROL | BE_IN_CONTROL)
992
#define SPECULATIVE (DATA_SPEC | CONTROL_SPEC)
993
#define BE_IN_SPEC (BE_IN_DATA | BE_IN_CONTROL)
994
 
995
/* Constants, that are helpful in iterating through dep_status.  */
996
#define FIRST_SPEC_TYPE BEGIN_DATA
997
#define LAST_SPEC_TYPE BE_IN_CONTROL
998
#define SPEC_TYPE_SHIFT BITS_PER_DEP_WEAK
999
 
1000
/* Dependence on instruction can be of multiple types
1001
   (e.g. true and output). This fields enhance REG_NOTE_KIND information
1002
   of the dependence.  */
1003
#define DEP_TRUE (((ds_t) 1) << (BE_IN_CONTROL_BITS_OFFSET + BITS_PER_DEP_WEAK))
1004
#define DEP_OUTPUT (DEP_TRUE << 1)
1005
#define DEP_ANTI (DEP_OUTPUT << 1)
1006
 
1007
#define DEP_TYPES (DEP_TRUE | DEP_OUTPUT | DEP_ANTI)
1008
 
1009
/* Instruction has non-speculative dependence.  This bit represents the
1010
   property of an instruction - not the one of a dependence.
1011
   Therefore, it can appear only in TODO_SPEC field of an instruction.  */
1012
#define HARD_DEP (DEP_ANTI << 1)
1013
 
1014
/* This represents the results of calling sched-deps.c functions,
1015
   which modify dependencies.  */
1016
enum DEPS_ADJUST_RESULT {
1017
  /* No dependence needed (e.g. producer == consumer).  */
1018
  DEP_NODEP,
1019
  /* Dependence is already present and wasn't modified.  */
1020
  DEP_PRESENT,
1021
  /* Existing dependence was modified to include additional information.  */
1022
  DEP_CHANGED,
1023
  /* New dependence has been created.  */
1024
  DEP_CREATED
1025
};
1026
 
1027
/* Represents the bits that can be set in the flags field of the
1028
   sched_info structure.  */
1029
enum SCHED_FLAGS {
1030
  /* If set, generate links between instruction as DEPS_LIST.
1031
     Otherwise, generate usual INSN_LIST links.  */
1032
  USE_DEPS_LIST = 1,
1033
  /* Perform data or control (or both) speculation.
1034
     Results in generation of data and control speculative dependencies.
1035
     Requires USE_DEPS_LIST set.  */
1036
  DO_SPECULATION = USE_DEPS_LIST << 1,
1037
  SCHED_RGN = DO_SPECULATION << 1,
1038
  SCHED_EBB = SCHED_RGN << 1,
1039
  /* Scheduler can possibly create new basic blocks.  Used for assertions.  */
1040
  NEW_BBS = SCHED_EBB << 1,
1041
  SEL_SCHED = NEW_BBS << 1
1042
};
1043
 
1044
enum SPEC_SCHED_FLAGS {
1045
  COUNT_SPEC_IN_CRITICAL_PATH = 1,
1046
  PREFER_NON_DATA_SPEC = COUNT_SPEC_IN_CRITICAL_PATH << 1,
1047
  PREFER_NON_CONTROL_SPEC = PREFER_NON_DATA_SPEC << 1,
1048
  SEL_SCHED_SPEC_DONT_CHECK_CONTROL = PREFER_NON_CONTROL_SPEC << 1
1049
};
1050
 
1051
#define NOTE_NOT_BB_P(NOTE) (NOTE_P (NOTE) && (NOTE_KIND (NOTE) \
1052
                                               != NOTE_INSN_BASIC_BLOCK))
1053
 
1054
extern FILE *sched_dump;
1055
extern int sched_verbose;
1056
 
1057
extern spec_info_t spec_info;
1058
extern bool haifa_recovery_bb_ever_added_p;
1059
 
1060
/* Exception Free Loads:
1061
 
1062
   We define five classes of speculative loads: IFREE, IRISKY,
1063
   PFREE, PRISKY, and MFREE.
1064
 
1065
   IFREE loads are loads that are proved to be exception-free, just
1066
   by examining the load insn.  Examples for such loads are loads
1067
   from TOC and loads of global data.
1068
 
1069
   IRISKY loads are loads that are proved to be exception-risky,
1070
   just by examining the load insn.  Examples for such loads are
1071
   volatile loads and loads from shared memory.
1072
 
1073
   PFREE loads are loads for which we can prove, by examining other
1074
   insns, that they are exception-free.  Currently, this class consists
1075
   of loads for which we are able to find a "similar load", either in
1076
   the target block, or, if only one split-block exists, in that split
1077
   block.  Load2 is similar to load1 if both have same single base
1078
   register.  We identify only part of the similar loads, by finding
1079
   an insn upon which both load1 and load2 have a DEF-USE dependence.
1080
 
1081
   PRISKY loads are loads for which we can prove, by examining other
1082
   insns, that they are exception-risky.  Currently we have two proofs for
1083
   such loads.  The first proof detects loads that are probably guarded by a
1084
   test on the memory address.  This proof is based on the
1085
   backward and forward data dependence information for the region.
1086
   Let load-insn be the examined load.
1087
   Load-insn is PRISKY iff ALL the following hold:
1088
 
1089
   - insn1 is not in the same block as load-insn
1090
   - there is a DEF-USE dependence chain (insn1, ..., load-insn)
1091
   - test-insn is either a compare or a branch, not in the same block
1092
     as load-insn
1093
   - load-insn is reachable from test-insn
1094
   - there is a DEF-USE dependence chain (insn1, ..., test-insn)
1095
 
1096
   This proof might fail when the compare and the load are fed
1097
   by an insn not in the region.  To solve this, we will add to this
1098
   group all loads that have no input DEF-USE dependence.
1099
 
1100
   The second proof detects loads that are directly or indirectly
1101
   fed by a speculative load.  This proof is affected by the
1102
   scheduling process.  We will use the flag  fed_by_spec_load.
1103
   Initially, all insns have this flag reset.  After a speculative
1104
   motion of an insn, if insn is either a load, or marked as
1105
   fed_by_spec_load, we will also mark as fed_by_spec_load every
1106
   insn1 for which a DEF-USE dependence (insn, insn1) exists.  A
1107
   load which is fed_by_spec_load is also PRISKY.
1108
 
1109
   MFREE (maybe-free) loads are all the remaining loads. They may be
1110
   exception-free, but we cannot prove it.
1111
 
1112
   Now, all loads in IFREE and PFREE classes are considered
1113
   exception-free, while all loads in IRISKY and PRISKY classes are
1114
   considered exception-risky.  As for loads in the MFREE class,
1115
   these are considered either exception-free or exception-risky,
1116
   depending on whether we are pessimistic or optimistic.  We have
1117
   to take the pessimistic approach to assure the safety of
1118
   speculative scheduling, but we can take the optimistic approach
1119
   by invoking the -fsched_spec_load_dangerous option.  */
1120
 
1121
enum INSN_TRAP_CLASS
1122
{
1123
  TRAP_FREE = 0, IFREE = 1, PFREE_CANDIDATE = 2,
1124
  PRISKY_CANDIDATE = 3, IRISKY = 4, TRAP_RISKY = 5
1125
};
1126
 
1127
#define WORST_CLASS(class1, class2) \
1128
((class1 > class2) ? class1 : class2)
1129
 
1130
#ifndef __GNUC__
1131
#define __inline
1132
#endif
1133
 
1134
#ifndef HAIFA_INLINE
1135
#define HAIFA_INLINE __inline
1136
#endif
1137
 
1138
struct sched_deps_info_def
1139
{
1140
  /* Called when computing dependencies for a JUMP_INSN.  This function
1141
     should store the set of registers that must be considered as set by
1142
     the jump in the regset.  */
1143
  void (*compute_jump_reg_dependencies) (rtx, regset, regset, regset);
1144
 
1145
  /* Start analyzing insn.  */
1146
  void (*start_insn) (rtx);
1147
 
1148
  /* Finish analyzing insn.  */
1149
  void (*finish_insn) (void);
1150
 
1151
  /* Start analyzing insn LHS (Left Hand Side).  */
1152
  void (*start_lhs) (rtx);
1153
 
1154
  /* Finish analyzing insn LHS.  */
1155
  void (*finish_lhs) (void);
1156
 
1157
  /* Start analyzing insn RHS (Right Hand Side).  */
1158
  void (*start_rhs) (rtx);
1159
 
1160
  /* Finish analyzing insn RHS.  */
1161
  void (*finish_rhs) (void);
1162
 
1163
  /* Note set of the register.  */
1164
  void (*note_reg_set) (int);
1165
 
1166
  /* Note clobber of the register.  */
1167
  void (*note_reg_clobber) (int);
1168
 
1169
  /* Note use of the register.  */
1170
  void (*note_reg_use) (int);
1171
 
1172
  /* Note memory dependence of type DS between MEM1 and MEM2 (which is
1173
     in the INSN2).  */
1174
  void (*note_mem_dep) (rtx mem1, rtx mem2, rtx insn2, ds_t ds);
1175
 
1176
  /* Note a dependence of type DS from the INSN.  */
1177
  void (*note_dep) (rtx insn, ds_t ds);
1178
 
1179
  /* Nonzero if we should use cselib for better alias analysis.  This
1180
     must be 0 if the dependency information is used after sched_analyze
1181
     has completed, e.g. if we're using it to initialize state for successor
1182
     blocks in region scheduling.  */
1183
  unsigned int use_cselib : 1;
1184
 
1185
  /* If set, generate links between instruction as DEPS_LIST.
1186
     Otherwise, generate usual INSN_LIST links.  */
1187
  unsigned int use_deps_list : 1;
1188
 
1189
  /* Generate data and control speculative dependencies.
1190
     Requires USE_DEPS_LIST set.  */
1191
  unsigned int generate_spec_deps : 1;
1192
};
1193
 
1194
extern struct sched_deps_info_def *sched_deps_info;
1195
 
1196
 
1197
/* Functions in sched-deps.c.  */
1198
extern bool sched_insns_conditions_mutex_p (const_rtx, const_rtx);
1199
extern bool sched_insn_is_legitimate_for_speculation_p (const_rtx, ds_t);
1200
extern void add_dependence (rtx, rtx, enum reg_note);
1201
extern void sched_analyze (struct deps_desc *, rtx, rtx);
1202
extern void init_deps (struct deps_desc *, bool);
1203
extern void init_deps_reg_last (struct deps_desc *);
1204
extern void free_deps (struct deps_desc *);
1205
extern void init_deps_global (void);
1206
extern void finish_deps_global (void);
1207
extern void deps_analyze_insn (struct deps_desc *, rtx);
1208
extern void remove_from_deps (struct deps_desc *, rtx);
1209
 
1210
extern dw_t get_dep_weak_1 (ds_t, ds_t);
1211
extern dw_t get_dep_weak (ds_t, ds_t);
1212
extern ds_t set_dep_weak (ds_t, ds_t, dw_t);
1213
extern dw_t estimate_dep_weak (rtx, rtx);
1214
extern ds_t ds_merge (ds_t, ds_t);
1215
extern ds_t ds_full_merge (ds_t, ds_t, rtx, rtx);
1216
extern ds_t ds_max_merge (ds_t, ds_t);
1217
extern dw_t ds_weak (ds_t);
1218
extern ds_t ds_get_speculation_types (ds_t);
1219
extern ds_t ds_get_max_dep_weak (ds_t);
1220
 
1221
extern void sched_deps_init (bool);
1222
extern void sched_deps_finish (void);
1223
 
1224
extern void haifa_note_reg_set (int);
1225
extern void haifa_note_reg_clobber (int);
1226
extern void haifa_note_reg_use (int);
1227
 
1228
extern void maybe_extend_reg_info_p (void);
1229
 
1230
extern void deps_start_bb (struct deps_desc *, rtx);
1231
extern enum reg_note ds_to_dt (ds_t);
1232
 
1233
extern bool deps_pools_are_empty_p (void);
1234
extern void sched_free_deps (rtx, rtx, bool);
1235
extern void extend_dependency_caches (int, bool);
1236
 
1237
extern void debug_ds (ds_t);
1238
 
1239
 
1240
/* Functions in haifa-sched.c.  */
1241
extern void sched_init_region_reg_pressure_info (void);
1242
extern int haifa_classify_insn (const_rtx);
1243
extern void get_ebb_head_tail (basic_block, basic_block, rtx *, rtx *);
1244
extern int no_real_insns_p (const_rtx, const_rtx);
1245
 
1246
extern int insn_cost (rtx);
1247
extern int dep_cost_1 (dep_t, dw_t);
1248
extern int dep_cost (dep_t);
1249
extern int set_priorities (rtx, rtx);
1250
 
1251
extern void sched_setup_bb_reg_pressure_info (basic_block, rtx);
1252
extern void schedule_block (basic_block *);
1253
 
1254
extern int cycle_issued_insns;
1255
extern int issue_rate;
1256
extern int dfa_lookahead;
1257
 
1258
extern void ready_sort (struct ready_list *);
1259
extern rtx ready_element (struct ready_list *, int);
1260
extern rtx *ready_lastpos (struct ready_list *);
1261
 
1262
extern int try_ready (rtx);
1263
extern void sched_extend_ready_list (int);
1264
extern void sched_finish_ready_list (void);
1265
extern void sched_change_pattern (rtx, rtx);
1266
extern int sched_speculate_insn (rtx, ds_t, rtx *);
1267
extern void unlink_bb_notes (basic_block, basic_block);
1268
extern void add_block (basic_block, basic_block);
1269
extern rtx bb_note (basic_block);
1270
extern void concat_note_lists (rtx, rtx *);
1271
extern rtx sched_emit_insn (rtx);
1272
 
1273
 
1274
/* Types and functions in sched-rgn.c.  */
1275
 
1276
/* A region is the main entity for interblock scheduling: insns
1277
   are allowed to move between blocks in the same region, along
1278
   control flow graph edges, in the 'up' direction.  */
1279
typedef struct
1280
{
1281
  /* Number of extended basic blocks in region.  */
1282
  int rgn_nr_blocks;
1283
  /* cblocks in the region (actually index in rgn_bb_table).  */
1284
  int rgn_blocks;
1285
  /* Dependencies for this region are already computed.  Basically, indicates,
1286
     that this is a recovery block.  */
1287
  unsigned int dont_calc_deps : 1;
1288
  /* This region has at least one non-trivial ebb.  */
1289
  unsigned int has_real_ebb : 1;
1290
}
1291
region;
1292
 
1293
extern int nr_regions;
1294
extern region *rgn_table;
1295
extern int *rgn_bb_table;
1296
extern int *block_to_bb;
1297
extern int *containing_rgn;
1298
 
1299
/* Often used short-hand in the scheduler.  The rest of the compiler uses
1300
   BLOCK_FOR_INSN(INSN) and an indirect reference to get the basic block
1301
   number ("index").  For historical reasons, the scheduler does not.  */
1302
#define BLOCK_NUM(INSN)       (BLOCK_FOR_INSN (INSN)->index + 0)
1303
 
1304
#define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
1305
#define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
1306
#define RGN_DONT_CALC_DEPS(rgn) (rgn_table[rgn].dont_calc_deps)
1307
#define RGN_HAS_REAL_EBB(rgn) (rgn_table[rgn].has_real_ebb)
1308
#define BLOCK_TO_BB(block) (block_to_bb[block])
1309
#define CONTAINING_RGN(block) (containing_rgn[block])
1310
 
1311
/* The mapping from ebb to block.  */
1312
extern int *ebb_head;
1313
#define BB_TO_BLOCK(ebb) (rgn_bb_table[ebb_head[ebb]])
1314
#define EBB_FIRST_BB(ebb) BASIC_BLOCK (BB_TO_BLOCK (ebb))
1315
#define EBB_LAST_BB(ebb) BASIC_BLOCK (rgn_bb_table[ebb_head[ebb + 1] - 1])
1316
#define INSN_BB(INSN) (BLOCK_TO_BB (BLOCK_NUM (INSN)))
1317
 
1318
extern int current_nr_blocks;
1319
extern int current_blocks;
1320
extern int target_bb;
1321
 
1322
extern bool sched_is_disabled_for_current_region_p (void);
1323
extern void sched_rgn_init (bool);
1324
extern void sched_rgn_finish (void);
1325
extern void rgn_setup_region (int);
1326
extern void sched_rgn_compute_dependencies (int);
1327
extern void sched_rgn_local_init (int);
1328
extern void sched_rgn_local_finish (void);
1329
extern void sched_rgn_local_free (void);
1330
extern void extend_regions (void);
1331
extern void rgn_make_new_region_out_of_new_block (basic_block);
1332
 
1333
extern void compute_priorities (void);
1334
extern void increase_insn_priority (rtx, int);
1335
extern void debug_rgn_dependencies (int);
1336
extern void debug_dependencies (rtx, rtx);
1337
extern void free_rgn_deps (void);
1338
extern int contributes_to_priority (rtx, rtx);
1339
extern void extend_rgns (int *, int *, sbitmap, int *);
1340
extern void deps_join (struct deps_desc *, struct deps_desc *);
1341
 
1342
extern void rgn_setup_common_sched_info (void);
1343
extern void rgn_setup_sched_infos (void);
1344
 
1345
extern void debug_regions (void);
1346
extern void debug_region (int);
1347
extern void dump_region_dot (FILE *, int);
1348
extern void dump_region_dot_file (const char *, int);
1349
 
1350
extern void haifa_sched_init (void);
1351
extern void haifa_sched_finish (void);
1352
 
1353
/* sched-deps.c interface to walk, add, search, update, resolve, delete
1354
   and debug instruction dependencies.  */
1355
 
1356
/* Constants defining dependences lists.  */
1357
 
1358
/* No list.  */
1359
#define SD_LIST_NONE (0)
1360
 
1361
/* hard_back_deps.  */
1362
#define SD_LIST_HARD_BACK (1)
1363
 
1364
/* spec_back_deps.  */
1365
#define SD_LIST_SPEC_BACK (2)
1366
 
1367
/* forw_deps.  */
1368
#define SD_LIST_FORW (4)
1369
 
1370
/* resolved_back_deps.  */
1371
#define SD_LIST_RES_BACK (8)
1372
 
1373
/* resolved_forw_deps.  */
1374
#define SD_LIST_RES_FORW (16)
1375
 
1376
#define SD_LIST_BACK (SD_LIST_HARD_BACK | SD_LIST_SPEC_BACK)
1377
 
1378
/* A type to hold above flags.  */
1379
typedef int sd_list_types_def;
1380
 
1381
extern void sd_next_list (const_rtx, sd_list_types_def *, deps_list_t *, bool *);
1382
 
1383
/* Iterator to walk through, resolve and delete dependencies.  */
1384
struct _sd_iterator
1385
{
1386
  /* What lists to walk.  Can be any combination of SD_LIST_* flags.  */
1387
  sd_list_types_def types;
1388
 
1389
  /* Instruction dependencies lists of which will be walked.  */
1390
  rtx insn;
1391
 
1392
  /* Pointer to the next field of the previous element.  This is not
1393
     simply a pointer to the next element to allow easy deletion from the
1394
     list.  When a dep is being removed from the list the iterator
1395
     will automatically advance because the value in *linkp will start
1396
     referring to the next element.  */
1397
  dep_link_t *linkp;
1398
 
1399
  /* True if the current list is a resolved one.  */
1400
  bool resolved_p;
1401
};
1402
 
1403
typedef struct _sd_iterator sd_iterator_def;
1404
 
1405
/* ??? We can move some definitions that are used in below inline functions
1406
   out of sched-int.h to sched-deps.c provided that the below functions will
1407
   become global externals.
1408
   These definitions include:
1409
   * struct _deps_list: opaque pointer is needed at global scope.
1410
   * struct _dep_link: opaque pointer is needed at scope of sd_iterator_def.
1411
   * struct _dep_node: opaque pointer is needed at scope of
1412
   struct _deps_link.  */
1413
 
1414
/* Return initialized iterator.  */
1415
static inline sd_iterator_def
1416
sd_iterator_start (rtx insn, sd_list_types_def types)
1417
{
1418
  /* Some dep_link a pointer to which will return NULL.  */
1419
  static dep_link_t null_link = NULL;
1420
 
1421
  sd_iterator_def i;
1422
 
1423
  i.types = types;
1424
  i.insn = insn;
1425
  i.linkp = &null_link;
1426
 
1427
  /* Avoid 'uninitialized warning'.  */
1428
  i.resolved_p = false;
1429
 
1430
  return i;
1431
}
1432
 
1433
/* Return the current element.  */
1434
static inline bool
1435
sd_iterator_cond (sd_iterator_def *it_ptr, dep_t *dep_ptr)
1436
{
1437
  dep_link_t link = *it_ptr->linkp;
1438
 
1439
  if (link != NULL)
1440
    {
1441
      *dep_ptr = DEP_LINK_DEP (link);
1442
      return true;
1443
    }
1444
  else
1445
    {
1446
      sd_list_types_def types = it_ptr->types;
1447
 
1448
      if (types != SD_LIST_NONE)
1449
        /* Switch to next list.  */
1450
        {
1451
          deps_list_t list;
1452
 
1453
          sd_next_list (it_ptr->insn,
1454
                        &it_ptr->types, &list, &it_ptr->resolved_p);
1455
 
1456
          it_ptr->linkp = &DEPS_LIST_FIRST (list);
1457
 
1458
          if (list)
1459
            return sd_iterator_cond (it_ptr, dep_ptr);
1460
        }
1461
 
1462
      *dep_ptr = NULL;
1463
      return false;
1464
    }
1465
}
1466
 
1467
/* Advance iterator.  */
1468
static inline void
1469
sd_iterator_next (sd_iterator_def *it_ptr)
1470
{
1471
  it_ptr->linkp = &DEP_LINK_NEXT (*it_ptr->linkp);
1472
}
1473
 
1474
/* A cycle wrapper.  */
1475
#define FOR_EACH_DEP(INSN, LIST_TYPES, ITER, DEP)               \
1476
  for ((ITER) = sd_iterator_start ((INSN), (LIST_TYPES));       \
1477
       sd_iterator_cond (&(ITER), &(DEP));                      \
1478
       sd_iterator_next (&(ITER)))
1479
 
1480
extern int sd_lists_size (const_rtx, sd_list_types_def);
1481
extern bool sd_lists_empty_p (const_rtx, sd_list_types_def);
1482
extern void sd_init_insn (rtx);
1483
extern void sd_finish_insn (rtx);
1484
extern dep_t sd_find_dep_between (rtx, rtx, bool);
1485
extern void sd_add_dep (dep_t, bool);
1486
extern enum DEPS_ADJUST_RESULT sd_add_or_update_dep (dep_t, bool);
1487
extern void sd_resolve_dep (sd_iterator_def);
1488
extern void sd_copy_back_deps (rtx, rtx, bool);
1489
extern void sd_delete_dep (sd_iterator_def);
1490
extern void sd_debug_lists (rtx, sd_list_types_def);
1491
 
1492
#endif /* INSN_SCHEDULING */
1493
 
1494
/* Functions in sched-vis.c.  These must be outside INSN_SCHEDULING as
1495
   sched-vis.c is compiled always.  */
1496
extern void print_insn (char *, const_rtx, int);
1497
extern void print_pattern (char *, const_rtx, int);
1498
extern void print_value (char *, const_rtx, int);
1499
 
1500
#endif /* GCC_SCHED_INT_H */

powered by: WebSVN 2.1.0

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