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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-stable/] [gcc-4.5.1/] [gcc/] [basic-block.h] - Blame information for rev 859

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 280 jeremybenn
/* Define control and data flow tables, and regsets.
2
   Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004,
3
   2005, 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_BASIC_BLOCK_H
22
#define GCC_BASIC_BLOCK_H
23
 
24
#include "bitmap.h"
25
#include "sbitmap.h"
26
#include "varray.h"
27
#include "partition.h"
28
#include "hard-reg-set.h"
29
#include "predict.h"
30
#include "vec.h"
31
#include "function.h"
32
 
33
/* Head of register set linked list.  */
34
typedef bitmap_head regset_head;
35
 
36
/* A pointer to a regset_head.  */
37
typedef bitmap regset;
38
 
39
/* Allocate a register set with oballoc.  */
40
#define ALLOC_REG_SET(OBSTACK) BITMAP_ALLOC (OBSTACK)
41
 
42
/* Do any cleanup needed on a regset when it is no longer used.  */
43
#define FREE_REG_SET(REGSET) BITMAP_FREE (REGSET)
44
 
45
/* Initialize a new regset.  */
46
#define INIT_REG_SET(HEAD) bitmap_initialize (HEAD, &reg_obstack)
47
 
48
/* Clear a register set by freeing up the linked list.  */
49
#define CLEAR_REG_SET(HEAD) bitmap_clear (HEAD)
50
 
51
/* Copy a register set to another register set.  */
52
#define COPY_REG_SET(TO, FROM) bitmap_copy (TO, FROM)
53
 
54
/* Compare two register sets.  */
55
#define REG_SET_EQUAL_P(A, B) bitmap_equal_p (A, B)
56
 
57
/* `and' a register set with a second register set.  */
58
#define AND_REG_SET(TO, FROM) bitmap_and_into (TO, FROM)
59
 
60
/* `and' the complement of a register set with a register set.  */
61
#define AND_COMPL_REG_SET(TO, FROM) bitmap_and_compl_into (TO, FROM)
62
 
63
/* Inclusive or a register set with a second register set.  */
64
#define IOR_REG_SET(TO, FROM) bitmap_ior_into (TO, FROM)
65
 
66
/* Exclusive or a register set with a second register set.  */
67
#define XOR_REG_SET(TO, FROM) bitmap_xor_into (TO, FROM)
68
 
69
/* Or into TO the register set FROM1 `and'ed with the complement of FROM2.  */
70
#define IOR_AND_COMPL_REG_SET(TO, FROM1, FROM2) \
71
  bitmap_ior_and_compl_into (TO, FROM1, FROM2)
72
 
73
/* Clear a single register in a register set.  */
74
#define CLEAR_REGNO_REG_SET(HEAD, REG) bitmap_clear_bit (HEAD, REG)
75
 
76
/* Set a single register in a register set.  */
77
#define SET_REGNO_REG_SET(HEAD, REG) bitmap_set_bit (HEAD, REG)
78
 
79
/* Return true if a register is set in a register set.  */
80
#define REGNO_REG_SET_P(TO, REG) bitmap_bit_p (TO, REG)
81
 
82
/* Copy the hard registers in a register set to the hard register set.  */
83
extern void reg_set_to_hard_reg_set (HARD_REG_SET *, const_bitmap);
84
#define REG_SET_TO_HARD_REG_SET(TO, FROM)                               \
85
do {                                                                    \
86
  CLEAR_HARD_REG_SET (TO);                                              \
87
  reg_set_to_hard_reg_set (&TO, FROM);                                  \
88
} while (0)
89
 
90
typedef bitmap_iterator reg_set_iterator;
91
 
92
/* Loop over all registers in REGSET, starting with MIN, setting REGNUM to the
93
   register number and executing CODE for all registers that are set.  */
94
#define EXECUTE_IF_SET_IN_REG_SET(REGSET, MIN, REGNUM, RSI)     \
95
  EXECUTE_IF_SET_IN_BITMAP (REGSET, MIN, REGNUM, RSI)
96
 
97
/* Loop over all registers in REGSET1 and REGSET2, starting with MIN, setting
98
   REGNUM to the register number and executing CODE for all registers that are
99
   set in the first regset and not set in the second.  */
100
#define EXECUTE_IF_AND_COMPL_IN_REG_SET(REGSET1, REGSET2, MIN, REGNUM, RSI) \
101
  EXECUTE_IF_AND_COMPL_IN_BITMAP (REGSET1, REGSET2, MIN, REGNUM, RSI)
102
 
103
/* Loop over all registers in REGSET1 and REGSET2, starting with MIN, setting
104
   REGNUM to the register number and executing CODE for all registers that are
105
   set in both regsets.  */
106
#define EXECUTE_IF_AND_IN_REG_SET(REGSET1, REGSET2, MIN, REGNUM, RSI) \
107
  EXECUTE_IF_AND_IN_BITMAP (REGSET1, REGSET2, MIN, REGNUM, RSI) \
108
 
109
/* Same information as REGS_INVALIDATED_BY_CALL but in regset form to be used
110
   in dataflow more conveniently.  */
111
 
112
extern regset regs_invalidated_by_call_regset;
113
 
114
/* Type we use to hold basic block counters.  Should be at least
115
   64bit.  Although a counter cannot be negative, we use a signed
116
   type, because erroneous negative counts can be generated when the
117
   flow graph is manipulated by various optimizations.  A signed type
118
   makes those easy to detect.  */
119
typedef HOST_WIDEST_INT gcov_type;
120
 
121
/* Control flow edge information.  */
122
struct GTY(()) edge_def {
123
  /* The two blocks at the ends of the edge.  */
124
  struct basic_block_def *src;
125
  struct basic_block_def *dest;
126
 
127
  /* Instructions queued on the edge.  */
128
  union edge_def_insns {
129
    gimple_seq GTY ((tag ("true"))) g;
130
    rtx GTY ((tag ("false"))) r;
131
  } GTY ((desc ("current_ir_type () == IR_GIMPLE"))) insns;
132
 
133
  /* Auxiliary info specific to a pass.  */
134
  PTR GTY ((skip (""))) aux;
135
 
136
  /* Location of any goto implicit in the edge and associated BLOCK.  */
137
  tree goto_block;
138
  location_t goto_locus;
139
 
140
  /* The index number corresponding to this edge in the edge vector
141
     dest->preds.  */
142
  unsigned int dest_idx;
143
 
144
  int flags;                    /* see EDGE_* below  */
145
  int probability;              /* biased by REG_BR_PROB_BASE */
146
  gcov_type count;              /* Expected number of executions calculated
147
                                   in profile.c  */
148
};
149
 
150
DEF_VEC_P(edge);
151
DEF_VEC_ALLOC_P(edge,gc);
152
DEF_VEC_ALLOC_P(edge,heap);
153
 
154
#define EDGE_FALLTHRU           1       /* 'Straight line' flow */
155
#define EDGE_ABNORMAL           2       /* Strange flow, like computed
156
                                           label, or eh */
157
#define EDGE_ABNORMAL_CALL      4       /* Call with abnormal exit
158
                                           like an exception, or sibcall */
159
#define EDGE_EH                 8       /* Exception throw */
160
#define EDGE_FAKE               16      /* Not a real edge (profile.c) */
161
#define EDGE_DFS_BACK           32      /* A backwards edge */
162
#define EDGE_CAN_FALLTHRU       64      /* Candidate for straight line
163
                                           flow.  */
164
#define EDGE_IRREDUCIBLE_LOOP   128     /* Part of irreducible loop.  */
165
#define EDGE_SIBCALL            256     /* Edge from sibcall to exit.  */
166
#define EDGE_LOOP_EXIT          512     /* Exit of a loop.  */
167
#define EDGE_TRUE_VALUE         1024    /* Edge taken when controlling
168
                                           predicate is nonzero.  */
169
#define EDGE_FALSE_VALUE        2048    /* Edge taken when controlling
170
                                           predicate is zero.  */
171
#define EDGE_EXECUTABLE         4096    /* Edge is executable.  Only
172
                                           valid during SSA-CCP.  */
173
#define EDGE_CROSSING           8192    /* Edge crosses between hot
174
                                           and cold sections, when we
175
                                           do partitioning.  */
176
#define EDGE_ALL_FLAGS         16383
177
 
178
#define EDGE_COMPLEX    (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_EH)
179
 
180
/* Counter summary from the last set of coverage counts read by
181
   profile.c.  */
182
extern const struct gcov_ctr_summary *profile_info;
183
 
184
/* Declared in cfgloop.h.  */
185
struct loop;
186
 
187
/* Declared in tree-flow.h.  */
188
struct edge_prediction;
189
struct rtl_bb_info;
190
 
191
/* A basic block is a sequence of instructions with only entry and
192
   only one exit.  If any one of the instructions are executed, they
193
   will all be executed, and in sequence from first to last.
194
 
195
   There may be COND_EXEC instructions in the basic block.  The
196
   COND_EXEC *instructions* will be executed -- but if the condition
197
   is false the conditionally executed *expressions* will of course
198
   not be executed.  We don't consider the conditionally executed
199
   expression (which might have side-effects) to be in a separate
200
   basic block because the program counter will always be at the same
201
   location after the COND_EXEC instruction, regardless of whether the
202
   condition is true or not.
203
 
204
   Basic blocks need not start with a label nor end with a jump insn.
205
   For example, a previous basic block may just "conditionally fall"
206
   into the succeeding basic block, and the last basic block need not
207
   end with a jump insn.  Block 0 is a descendant of the entry block.
208
 
209
   A basic block beginning with two labels cannot have notes between
210
   the labels.
211
 
212
   Data for jump tables are stored in jump_insns that occur in no
213
   basic block even though these insns can follow or precede insns in
214
   basic blocks.  */
215
 
216
/* Basic block information indexed by block number.  */
217
struct GTY((chain_next ("%h.next_bb"), chain_prev ("%h.prev_bb"))) basic_block_def {
218
  /* The edges into and out of the block.  */
219
  VEC(edge,gc) *preds;
220
  VEC(edge,gc) *succs;
221
 
222
  /* Auxiliary info specific to a pass.  */
223
  PTR GTY ((skip (""))) aux;
224
 
225
  /* Innermost loop containing the block.  */
226
  struct loop *loop_father;
227
 
228
  /* The dominance and postdominance information node.  */
229
  struct et_node * GTY ((skip (""))) dom[2];
230
 
231
  /* Previous and next blocks in the chain.  */
232
  struct basic_block_def *prev_bb;
233
  struct basic_block_def *next_bb;
234
 
235
  union basic_block_il_dependent {
236
      struct gimple_bb_info * GTY ((tag ("0"))) gimple;
237
      struct rtl_bb_info * GTY ((tag ("1"))) rtl;
238
    } GTY ((desc ("((%1.flags & BB_RTL) != 0)"))) il;
239
 
240
  /* Expected number of executions: calculated in profile.c.  */
241
  gcov_type count;
242
 
243
  /* The index of this block.  */
244
  int index;
245
 
246
  /* The loop depth of this block.  */
247
  int loop_depth;
248
 
249
  /* Expected frequency.  Normalized to be in range 0 to BB_FREQ_MAX.  */
250
  int frequency;
251
 
252
  /* The discriminator for this block.  */
253
  int discriminator;
254
 
255
  /* Various flags.  See BB_* below.  */
256
  int flags;
257
};
258
 
259
struct GTY(()) rtl_bb_info {
260
  /* The first and last insns of the block.  */
261
  rtx head_;
262
  rtx end_;
263
 
264
  /* In CFGlayout mode points to insn notes/jumptables to be placed just before
265
     and after the block.   */
266
  rtx header;
267
  rtx footer;
268
 
269
  /* This field is used by the bb-reorder and tracer passes.  */
270
  int visited;
271
};
272
 
273
struct GTY(()) gimple_bb_info {
274
  /* Sequence of statements in this block.  */
275
  gimple_seq seq;
276
 
277
  /* PHI nodes for this block.  */
278
  gimple_seq phi_nodes;
279
};
280
 
281
DEF_VEC_P(basic_block);
282
DEF_VEC_ALLOC_P(basic_block,gc);
283
DEF_VEC_ALLOC_P(basic_block,heap);
284
 
285
#define BB_FREQ_MAX 10000
286
 
287
/* Masks for basic_block.flags.
288
 
289
   BB_HOT_PARTITION and BB_COLD_PARTITION should be preserved throughout
290
   the compilation, so they are never cleared.
291
 
292
   All other flags may be cleared by clear_bb_flags().  It is generally
293
   a bad idea to rely on any flags being up-to-date.  */
294
 
295
enum bb_flags
296
{
297
  /* Only set on blocks that have just been created by create_bb.  */
298
  BB_NEW = 1 << 0,
299
 
300
  /* Set by find_unreachable_blocks.  Do not rely on this being set in any
301
     pass.  */
302
  BB_REACHABLE = 1 << 1,
303
 
304
  /* Set for blocks in an irreducible loop by loop analysis.  */
305
  BB_IRREDUCIBLE_LOOP = 1 << 2,
306
 
307
  /* Set on blocks that may actually not be single-entry single-exit block.  */
308
  BB_SUPERBLOCK = 1 << 3,
309
 
310
  /* Set on basic blocks that the scheduler should not touch.  This is used
311
     by SMS to prevent other schedulers from messing with the loop schedule.  */
312
  BB_DISABLE_SCHEDULE = 1 << 4,
313
 
314
  /* Set on blocks that should be put in a hot section.  */
315
  BB_HOT_PARTITION = 1 << 5,
316
 
317
  /* Set on blocks that should be put in a cold section.  */
318
  BB_COLD_PARTITION = 1 << 6,
319
 
320
  /* Set on block that was duplicated.  */
321
  BB_DUPLICATED = 1 << 7,
322
 
323
  /* Set if the label at the top of this block is the target of a non-local goto.  */
324
  BB_NON_LOCAL_GOTO_TARGET = 1 << 8,
325
 
326
  /* Set on blocks that are in RTL format.  */
327
  BB_RTL = 1 << 9 ,
328
 
329
  /* Set on blocks that are forwarder blocks.
330
     Only used in cfgcleanup.c.  */
331
  BB_FORWARDER_BLOCK = 1 << 10,
332
 
333
  /* Set on blocks that cannot be threaded through.
334
     Only used in cfgcleanup.c.  */
335
  BB_NONTHREADABLE_BLOCK = 1 << 11
336
};
337
 
338
/* Dummy flag for convenience in the hot/cold partitioning code.  */
339
#define BB_UNPARTITIONED        0
340
 
341
/* Partitions, to be used when partitioning hot and cold basic blocks into
342
   separate sections.  */
343
#define BB_PARTITION(bb) ((bb)->flags & (BB_HOT_PARTITION|BB_COLD_PARTITION))
344
#define BB_SET_PARTITION(bb, part) do {                                 \
345
  basic_block bb_ = (bb);                                               \
346
  bb_->flags = ((bb_->flags & ~(BB_HOT_PARTITION|BB_COLD_PARTITION))    \
347
                | (part));                                              \
348
} while (0)
349
 
350
#define BB_COPY_PARTITION(dstbb, srcbb) \
351
  BB_SET_PARTITION (dstbb, BB_PARTITION (srcbb))
352
 
353
/* State of dominance information.  */
354
 
355
enum dom_state
356
{
357
  DOM_NONE,             /* Not computed at all.  */
358
  DOM_NO_FAST_QUERY,    /* The data is OK, but the fast query data are not usable.  */
359
  DOM_OK                /* Everything is ok.  */
360
};
361
 
362
/* What sort of profiling information we have.  */
363
enum profile_status_d
364
{
365
  PROFILE_ABSENT,
366
  PROFILE_GUESSED,
367
  PROFILE_READ
368
};
369
 
370
/* A structure to group all the per-function control flow graph data.
371
   The x_* prefixing is necessary because otherwise references to the
372
   fields of this struct are interpreted as the defines for backward
373
   source compatibility following the definition of this struct.  */
374
struct GTY(()) control_flow_graph {
375
  /* Block pointers for the exit and entry of a function.
376
     These are always the head and tail of the basic block list.  */
377
  basic_block x_entry_block_ptr;
378
  basic_block x_exit_block_ptr;
379
 
380
  /* Index by basic block number, get basic block struct info.  */
381
  VEC(basic_block,gc) *x_basic_block_info;
382
 
383
  /* Number of basic blocks in this flow graph.  */
384
  int x_n_basic_blocks;
385
 
386
  /* Number of edges in this flow graph.  */
387
  int x_n_edges;
388
 
389
  /* The first free basic block number.  */
390
  int x_last_basic_block;
391
 
392
  /* Mapping of labels to their associated blocks.  At present
393
     only used for the gimple CFG.  */
394
  VEC(basic_block,gc) *x_label_to_block_map;
395
 
396
  enum profile_status_d x_profile_status;
397
 
398
  /* Whether the dominators and the postdominators are available.  */
399
  enum dom_state x_dom_computed[2];
400
 
401
  /* Number of basic blocks in the dominance tree.  */
402
  unsigned x_n_bbs_in_dom_tree[2];
403
 
404
  /* Maximal number of entities in the single jumptable.  Used to estimate
405
     final flowgraph size.  */
406
  int max_jumptable_ents;
407
 
408
  /* UIDs for LABEL_DECLs.  */
409
  int last_label_uid;
410
};
411
 
412
/* Defines for accessing the fields of the CFG structure for function FN.  */
413
#define ENTRY_BLOCK_PTR_FOR_FUNCTION(FN)     ((FN)->cfg->x_entry_block_ptr)
414
#define EXIT_BLOCK_PTR_FOR_FUNCTION(FN)      ((FN)->cfg->x_exit_block_ptr)
415
#define basic_block_info_for_function(FN)    ((FN)->cfg->x_basic_block_info)
416
#define n_basic_blocks_for_function(FN)      ((FN)->cfg->x_n_basic_blocks)
417
#define n_edges_for_function(FN)             ((FN)->cfg->x_n_edges)
418
#define last_basic_block_for_function(FN)    ((FN)->cfg->x_last_basic_block)
419
#define label_to_block_map_for_function(FN)  ((FN)->cfg->x_label_to_block_map)
420
#define profile_status_for_function(FN)      ((FN)->cfg->x_profile_status)
421
 
422
#define BASIC_BLOCK_FOR_FUNCTION(FN,N) \
423
  (VEC_index (basic_block, basic_block_info_for_function(FN), (N)))
424
#define SET_BASIC_BLOCK_FOR_FUNCTION(FN,N,BB) \
425
  (VEC_replace (basic_block, basic_block_info_for_function(FN), (N), (BB)))
426
 
427
/* Defines for textual backward source compatibility.  */
428
#define ENTRY_BLOCK_PTR         (cfun->cfg->x_entry_block_ptr)
429
#define EXIT_BLOCK_PTR          (cfun->cfg->x_exit_block_ptr)
430
#define basic_block_info        (cfun->cfg->x_basic_block_info)
431
#define n_basic_blocks          (cfun->cfg->x_n_basic_blocks)
432
#define n_edges                 (cfun->cfg->x_n_edges)
433
#define last_basic_block        (cfun->cfg->x_last_basic_block)
434
#define label_to_block_map      (cfun->cfg->x_label_to_block_map)
435
#define profile_status          (cfun->cfg->x_profile_status)
436
 
437
#define BASIC_BLOCK(N)          (VEC_index (basic_block, basic_block_info, (N)))
438
#define SET_BASIC_BLOCK(N,BB)   (VEC_replace (basic_block, basic_block_info, (N), (BB)))
439
 
440
/* For iterating over basic blocks.  */
441
#define FOR_BB_BETWEEN(BB, FROM, TO, DIR) \
442
  for (BB = FROM; BB != TO; BB = BB->DIR)
443
 
444
#define FOR_EACH_BB_FN(BB, FN) \
445
  FOR_BB_BETWEEN (BB, (FN)->cfg->x_entry_block_ptr->next_bb, (FN)->cfg->x_exit_block_ptr, next_bb)
446
 
447
#define FOR_EACH_BB(BB) FOR_EACH_BB_FN (BB, cfun)
448
 
449
#define FOR_EACH_BB_REVERSE_FN(BB, FN) \
450
  FOR_BB_BETWEEN (BB, (FN)->cfg->x_exit_block_ptr->prev_bb, (FN)->cfg->x_entry_block_ptr, prev_bb)
451
 
452
#define FOR_EACH_BB_REVERSE(BB) FOR_EACH_BB_REVERSE_FN(BB, cfun)
453
 
454
/* For iterating over insns in basic block.  */
455
#define FOR_BB_INSNS(BB, INSN)                  \
456
  for ((INSN) = BB_HEAD (BB);                   \
457
       (INSN) && (INSN) != NEXT_INSN (BB_END (BB));     \
458
       (INSN) = NEXT_INSN (INSN))
459
 
460
/* For iterating over insns in basic block when we might remove the
461
   current insn.  */
462
#define FOR_BB_INSNS_SAFE(BB, INSN, CURR)                       \
463
  for ((INSN) = BB_HEAD (BB), (CURR) = (INSN) ? NEXT_INSN ((INSN)): NULL;       \
464
       (INSN) && (INSN) != NEXT_INSN (BB_END (BB));     \
465
       (INSN) = (CURR), (CURR) = (INSN) ? NEXT_INSN ((INSN)) : NULL)
466
 
467
#define FOR_BB_INSNS_REVERSE(BB, INSN)          \
468
  for ((INSN) = BB_END (BB);                    \
469
       (INSN) && (INSN) != PREV_INSN (BB_HEAD (BB));    \
470
       (INSN) = PREV_INSN (INSN))
471
 
472
#define FOR_BB_INSNS_REVERSE_SAFE(BB, INSN, CURR)       \
473
  for ((INSN) = BB_END (BB),(CURR) = (INSN) ? PREV_INSN ((INSN)) : NULL;        \
474
       (INSN) && (INSN) != PREV_INSN (BB_HEAD (BB));    \
475
       (INSN) = (CURR), (CURR) = (INSN) ? PREV_INSN ((INSN)) : NULL)
476
 
477
/* Cycles through _all_ basic blocks, even the fake ones (entry and
478
   exit block).  */
479
 
480
#define FOR_ALL_BB(BB) \
481
  for (BB = ENTRY_BLOCK_PTR; BB; BB = BB->next_bb)
482
 
483
#define FOR_ALL_BB_FN(BB, FN) \
484
  for (BB = ENTRY_BLOCK_PTR_FOR_FUNCTION (FN); BB; BB = BB->next_bb)
485
 
486
extern bitmap_obstack reg_obstack;
487
 
488
 
489
/* Stuff for recording basic block info.  */
490
 
491
#define BB_HEAD(B)      (B)->il.rtl->head_
492
#define BB_END(B)       (B)->il.rtl->end_
493
 
494
/* Special block numbers [markers] for entry and exit.
495
   Neither of them is supposed to hold actual statements.  */
496
#define ENTRY_BLOCK (0)
497
#define EXIT_BLOCK (1)
498
 
499
/* The two blocks that are always in the cfg.  */
500
#define NUM_FIXED_BLOCKS (2)
501
 
502
#define set_block_for_insn(INSN, BB)  (BLOCK_FOR_INSN (INSN) = BB)
503
 
504
extern void compute_bb_for_insn (void);
505
extern unsigned int free_bb_for_insn (void);
506
extern void update_bb_for_insn (basic_block);
507
 
508
extern void insert_insn_on_edge (rtx, edge);
509
basic_block split_edge_and_insert (edge, rtx);
510
 
511
extern void commit_one_edge_insertion (edge e);
512
extern void commit_edge_insertions (void);
513
 
514
extern void remove_fake_edges (void);
515
extern void remove_fake_exit_edges (void);
516
extern void add_noreturn_fake_exit_edges (void);
517
extern void connect_infinite_loops_to_exit (void);
518
extern edge unchecked_make_edge (basic_block, basic_block, int);
519
extern edge cached_make_edge (sbitmap, basic_block, basic_block, int);
520
extern edge make_edge (basic_block, basic_block, int);
521
extern edge make_single_succ_edge (basic_block, basic_block, int);
522
extern void remove_edge_raw (edge);
523
extern void redirect_edge_succ (edge, basic_block);
524
extern edge redirect_edge_succ_nodup (edge, basic_block);
525
extern void redirect_edge_pred (edge, basic_block);
526
extern basic_block create_basic_block_structure (rtx, rtx, rtx, basic_block);
527
extern void clear_bb_flags (void);
528
extern int post_order_compute (int *, bool, bool);
529
extern int inverted_post_order_compute (int *);
530
extern int pre_and_rev_post_order_compute (int *, int *, bool);
531
extern int dfs_enumerate_from (basic_block, int,
532
                               bool (*)(const_basic_block, const void *),
533
                               basic_block *, int, const void *);
534
extern void compute_dominance_frontiers (bitmap *);
535
extern bitmap compute_idf (bitmap, bitmap *);
536
extern void dump_bb_info (basic_block, bool, bool, int, const char *, FILE *);
537
extern void dump_edge_info (FILE *, edge, int);
538
extern void brief_dump_cfg (FILE *);
539
extern void clear_edges (void);
540
extern void scale_bbs_frequencies_int (basic_block *, int, int, int);
541
extern void scale_bbs_frequencies_gcov_type (basic_block *, int, gcov_type,
542
                                             gcov_type);
543
 
544
/* Structure to group all of the information to process IF-THEN and
545
   IF-THEN-ELSE blocks for the conditional execution support.  This
546
   needs to be in a public file in case the IFCVT macros call
547
   functions passing the ce_if_block data structure.  */
548
 
549
typedef struct ce_if_block
550
{
551
  basic_block test_bb;                  /* First test block.  */
552
  basic_block then_bb;                  /* THEN block.  */
553
  basic_block else_bb;                  /* ELSE block or NULL.  */
554
  basic_block join_bb;                  /* Join THEN/ELSE blocks.  */
555
  basic_block last_test_bb;             /* Last bb to hold && or || tests.  */
556
  int num_multiple_test_blocks;         /* # of && and || basic blocks.  */
557
  int num_and_and_blocks;               /* # of && blocks.  */
558
  int num_or_or_blocks;                 /* # of || blocks.  */
559
  int num_multiple_test_insns;          /* # of insns in && and || blocks.  */
560
  int and_and_p;                        /* Complex test is &&.  */
561
  int num_then_insns;                   /* # of insns in THEN block.  */
562
  int num_else_insns;                   /* # of insns in ELSE block.  */
563
  int pass;                             /* Pass number.  */
564
 
565
#ifdef IFCVT_EXTRA_FIELDS
566
  IFCVT_EXTRA_FIELDS                    /* Any machine dependent fields.  */
567
#endif
568
 
569
} ce_if_block_t;
570
 
571
/* This structure maintains an edge list vector.  */
572
struct edge_list
573
{
574
  int num_blocks;
575
  int num_edges;
576
  edge *index_to_edge;
577
};
578
 
579
/* The base value for branch probability notes and edge probabilities.  */
580
#define REG_BR_PROB_BASE  10000
581
 
582
/* This is the value which indicates no edge is present.  */
583
#define EDGE_INDEX_NO_EDGE      -1
584
 
585
/* EDGE_INDEX returns an integer index for an edge, or EDGE_INDEX_NO_EDGE
586
   if there is no edge between the 2 basic blocks.  */
587
#define EDGE_INDEX(el, pred, succ) (find_edge_index ((el), (pred), (succ)))
588
 
589
/* INDEX_EDGE_PRED_BB and INDEX_EDGE_SUCC_BB return a pointer to the basic
590
   block which is either the pred or succ end of the indexed edge.  */
591
#define INDEX_EDGE_PRED_BB(el, index)   ((el)->index_to_edge[(index)]->src)
592
#define INDEX_EDGE_SUCC_BB(el, index)   ((el)->index_to_edge[(index)]->dest)
593
 
594
/* INDEX_EDGE returns a pointer to the edge.  */
595
#define INDEX_EDGE(el, index)           ((el)->index_to_edge[(index)])
596
 
597
/* Number of edges in the compressed edge list.  */
598
#define NUM_EDGES(el)                   ((el)->num_edges)
599
 
600
/* BB is assumed to contain conditional jump.  Return the fallthru edge.  */
601
#define FALLTHRU_EDGE(bb)               (EDGE_SUCC ((bb), 0)->flags & EDGE_FALLTHRU \
602
                                         ? EDGE_SUCC ((bb), 0) : EDGE_SUCC ((bb), 1))
603
 
604
/* BB is assumed to contain conditional jump.  Return the branch edge.  */
605
#define BRANCH_EDGE(bb)                 (EDGE_SUCC ((bb), 0)->flags & EDGE_FALLTHRU \
606
                                         ? EDGE_SUCC ((bb), 1) : EDGE_SUCC ((bb), 0))
607
 
608
/* Return expected execution frequency of the edge E.  */
609
#define EDGE_FREQUENCY(e)               (((e)->src->frequency \
610
                                          * (e)->probability \
611
                                          + REG_BR_PROB_BASE / 2) \
612
                                         / REG_BR_PROB_BASE)
613
 
614
/* Return nonzero if edge is critical.  */
615
#define EDGE_CRITICAL_P(e)              (EDGE_COUNT ((e)->src->succs) >= 2 \
616
                                         && EDGE_COUNT ((e)->dest->preds) >= 2)
617
 
618
#define EDGE_COUNT(ev)                  VEC_length (edge, (ev))
619
#define EDGE_I(ev,i)                    VEC_index  (edge, (ev), (i))
620
#define EDGE_PRED(bb,i)                 VEC_index  (edge, (bb)->preds, (i))
621
#define EDGE_SUCC(bb,i)                 VEC_index  (edge, (bb)->succs, (i))
622
 
623
/* Returns true if BB has precisely one successor.  */
624
 
625
static inline bool
626
single_succ_p (const_basic_block bb)
627
{
628
  return EDGE_COUNT (bb->succs) == 1;
629
}
630
 
631
/* Returns true if BB has precisely one predecessor.  */
632
 
633
static inline bool
634
single_pred_p (const_basic_block bb)
635
{
636
  return EDGE_COUNT (bb->preds) == 1;
637
}
638
 
639
/* Returns the single successor edge of basic block BB.  Aborts if
640
   BB does not have exactly one successor.  */
641
 
642
static inline edge
643
single_succ_edge (const_basic_block bb)
644
{
645
  gcc_assert (single_succ_p (bb));
646
  return EDGE_SUCC (bb, 0);
647
}
648
 
649
/* Returns the single predecessor edge of basic block BB.  Aborts
650
   if BB does not have exactly one predecessor.  */
651
 
652
static inline edge
653
single_pred_edge (const_basic_block bb)
654
{
655
  gcc_assert (single_pred_p (bb));
656
  return EDGE_PRED (bb, 0);
657
}
658
 
659
/* Returns the single successor block of basic block BB.  Aborts
660
   if BB does not have exactly one successor.  */
661
 
662
static inline basic_block
663
single_succ (const_basic_block bb)
664
{
665
  return single_succ_edge (bb)->dest;
666
}
667
 
668
/* Returns the single predecessor block of basic block BB.  Aborts
669
   if BB does not have exactly one predecessor.*/
670
 
671
static inline basic_block
672
single_pred (const_basic_block bb)
673
{
674
  return single_pred_edge (bb)->src;
675
}
676
 
677
/* Iterator object for edges.  */
678
 
679
typedef struct {
680
  unsigned index;
681
  VEC(edge,gc) **container;
682
} edge_iterator;
683
 
684
static inline VEC(edge,gc) *
685
ei_container (edge_iterator i)
686
{
687
  gcc_assert (i.container);
688
  return *i.container;
689
}
690
 
691
#define ei_start(iter) ei_start_1 (&(iter))
692
#define ei_last(iter) ei_last_1 (&(iter))
693
 
694
/* Return an iterator pointing to the start of an edge vector.  */
695
static inline edge_iterator
696
ei_start_1 (VEC(edge,gc) **ev)
697
{
698
  edge_iterator i;
699
 
700
  i.index = 0;
701
  i.container = ev;
702
 
703
  return i;
704
}
705
 
706
/* Return an iterator pointing to the last element of an edge
707
   vector.  */
708
static inline edge_iterator
709
ei_last_1 (VEC(edge,gc) **ev)
710
{
711
  edge_iterator i;
712
 
713
  i.index = EDGE_COUNT (*ev) - 1;
714
  i.container = ev;
715
 
716
  return i;
717
}
718
 
719
/* Is the iterator `i' at the end of the sequence?  */
720
static inline bool
721
ei_end_p (edge_iterator i)
722
{
723
  return (i.index == EDGE_COUNT (ei_container (i)));
724
}
725
 
726
/* Is the iterator `i' at one position before the end of the
727
   sequence?  */
728
static inline bool
729
ei_one_before_end_p (edge_iterator i)
730
{
731
  return (i.index + 1 == EDGE_COUNT (ei_container (i)));
732
}
733
 
734
/* Advance the iterator to the next element.  */
735
static inline void
736
ei_next (edge_iterator *i)
737
{
738
  gcc_assert (i->index < EDGE_COUNT (ei_container (*i)));
739
  i->index++;
740
}
741
 
742
/* Move the iterator to the previous element.  */
743
static inline void
744
ei_prev (edge_iterator *i)
745
{
746
  gcc_assert (i->index > 0);
747
  i->index--;
748
}
749
 
750
/* Return the edge pointed to by the iterator `i'.  */
751
static inline edge
752
ei_edge (edge_iterator i)
753
{
754
  return EDGE_I (ei_container (i), i.index);
755
}
756
 
757
/* Return an edge pointed to by the iterator.  Do it safely so that
758
   NULL is returned when the iterator is pointing at the end of the
759
   sequence.  */
760
static inline edge
761
ei_safe_edge (edge_iterator i)
762
{
763
  return !ei_end_p (i) ? ei_edge (i) : NULL;
764
}
765
 
766
/* Return 1 if we should continue to iterate.  Return 0 otherwise.
767
   *Edge P is set to the next edge if we are to continue to iterate
768
   and NULL otherwise.  */
769
 
770
static inline bool
771
ei_cond (edge_iterator ei, edge *p)
772
{
773
  if (!ei_end_p (ei))
774
    {
775
      *p = ei_edge (ei);
776
      return 1;
777
    }
778
  else
779
    {
780
      *p = NULL;
781
      return 0;
782
    }
783
}
784
 
785
/* This macro serves as a convenient way to iterate each edge in a
786
   vector of predecessor or successor edges.  It must not be used when
787
   an element might be removed during the traversal, otherwise
788
   elements will be missed.  Instead, use a for-loop like that shown
789
   in the following pseudo-code:
790
 
791
   FOR (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
792
     {
793
        IF (e != taken_edge)
794
          remove_edge (e);
795
        ELSE
796
          ei_next (&ei);
797
     }
798
*/
799
 
800
#define FOR_EACH_EDGE(EDGE,ITER,EDGE_VEC)       \
801
  for ((ITER) = ei_start ((EDGE_VEC));          \
802
       ei_cond ((ITER), &(EDGE));               \
803
       ei_next (&(ITER)))
804
 
805
struct edge_list * create_edge_list (void);
806
void free_edge_list (struct edge_list *);
807
void print_edge_list (FILE *, struct edge_list *);
808
void verify_edge_list (FILE *, struct edge_list *);
809
int find_edge_index (struct edge_list *, basic_block, basic_block);
810
edge find_edge (basic_block, basic_block);
811
 
812
#define CLEANUP_EXPENSIVE       1       /* Do relatively expensive optimizations
813
                                           except for edge forwarding */
814
#define CLEANUP_CROSSJUMP       2       /* Do crossjumping.  */
815
#define CLEANUP_POST_REGSTACK   4       /* We run after reg-stack and need
816
                                           to care REG_DEAD notes.  */
817
#define CLEANUP_THREADING       8       /* Do jump threading.  */
818
#define CLEANUP_NO_INSN_DEL     16      /* Do not try to delete trivially dead
819
                                           insns.  */
820
#define CLEANUP_CFGLAYOUT       32      /* Do cleanup in cfglayout mode.  */
821
 
822
/* In lcm.c */
823
extern struct edge_list *pre_edge_lcm (int, sbitmap *, sbitmap *,
824
                                       sbitmap *, sbitmap *, sbitmap **,
825
                                       sbitmap **);
826
extern struct edge_list *pre_edge_rev_lcm (int, sbitmap *,
827
                                           sbitmap *, sbitmap *,
828
                                           sbitmap *, sbitmap **,
829
                                           sbitmap **);
830
extern void compute_available (sbitmap *, sbitmap *, sbitmap *, sbitmap *);
831
 
832
/* In predict.c */
833
extern bool maybe_hot_bb_p (const_basic_block);
834
extern bool maybe_hot_edge_p (edge);
835
extern bool probably_never_executed_bb_p (const_basic_block);
836
extern bool optimize_bb_for_size_p (const_basic_block);
837
extern bool optimize_bb_for_speed_p (const_basic_block);
838
extern bool optimize_edge_for_size_p (edge);
839
extern bool optimize_edge_for_speed_p (edge);
840
extern bool optimize_function_for_size_p (struct function *);
841
extern bool optimize_function_for_speed_p (struct function *);
842
extern bool optimize_loop_for_size_p (struct loop *);
843
extern bool optimize_loop_for_speed_p (struct loop *);
844
extern bool optimize_loop_nest_for_size_p (struct loop *);
845
extern bool optimize_loop_nest_for_speed_p (struct loop *);
846
extern bool gimple_predicted_by_p (const_basic_block, enum br_predictor);
847
extern bool rtl_predicted_by_p (const_basic_block, enum br_predictor);
848
extern void gimple_predict_edge (edge, enum br_predictor, int);
849
extern void rtl_predict_edge (edge, enum br_predictor, int);
850
extern void predict_edge_def (edge, enum br_predictor, enum prediction);
851
extern void guess_outgoing_edge_probabilities (basic_block);
852
extern void remove_predictions_associated_with_edge (edge);
853
extern bool edge_probability_reliable_p (const_edge);
854
extern bool br_prob_note_reliable_p (const_rtx);
855
extern bool predictable_edge_p (edge);
856
 
857
/* In cfg.c  */
858
extern void init_flow (struct function *);
859
extern void debug_bb (basic_block);
860
extern basic_block debug_bb_n (int);
861
extern void dump_regset (regset, FILE *);
862
extern void debug_regset (regset);
863
extern void expunge_block (basic_block);
864
extern void link_block (basic_block, basic_block);
865
extern void unlink_block (basic_block);
866
extern void compact_blocks (void);
867
extern basic_block alloc_block (void);
868
extern void alloc_aux_for_block (basic_block, int);
869
extern void alloc_aux_for_blocks (int);
870
extern void clear_aux_for_blocks (void);
871
extern void free_aux_for_blocks (void);
872
extern void alloc_aux_for_edge (edge, int);
873
extern void alloc_aux_for_edges (int);
874
extern void clear_aux_for_edges (void);
875
extern void free_aux_for_edges (void);
876
 
877
/* In cfganal.c  */
878
extern void find_unreachable_blocks (void);
879
extern bool forwarder_block_p (const_basic_block);
880
extern bool can_fallthru (basic_block, basic_block);
881
extern bool could_fall_through (basic_block, basic_block);
882
extern void flow_nodes_print (const char *, const_sbitmap, FILE *);
883
extern void flow_edge_list_print (const char *, const edge *, int, FILE *);
884
 
885
/* In cfgrtl.c  */
886
extern basic_block force_nonfallthru (edge);
887
extern rtx block_label (basic_block);
888
extern bool purge_all_dead_edges (void);
889
extern bool purge_dead_edges (basic_block);
890
 
891
/* In cfgbuild.c.  */
892
extern void find_many_sub_basic_blocks (sbitmap);
893
extern void rtl_make_eh_edge (sbitmap, basic_block, rtx);
894
 
895
/* In cfgcleanup.c.  */
896
extern bool cleanup_cfg (int);
897
extern bool delete_unreachable_blocks (void);
898
 
899
extern bool mark_dfs_back_edges (void);
900
extern void set_edge_can_fallthru_flag (void);
901
extern void update_br_prob_note (basic_block);
902
extern void fixup_abnormal_edges (void);
903
extern bool inside_basic_block_p (const_rtx);
904
extern bool control_flow_insn_p (const_rtx);
905
extern rtx get_last_bb_insn (basic_block);
906
 
907
/* In bb-reorder.c */
908
extern void reorder_basic_blocks (void);
909
 
910
/* In dominance.c */
911
 
912
enum cdi_direction
913
{
914
  CDI_DOMINATORS = 1,
915
  CDI_POST_DOMINATORS = 2
916
};
917
 
918
extern enum dom_state dom_info_state (enum cdi_direction);
919
extern void set_dom_info_availability (enum cdi_direction, enum dom_state);
920
extern bool dom_info_available_p (enum cdi_direction);
921
extern void calculate_dominance_info (enum cdi_direction);
922
extern void free_dominance_info (enum cdi_direction);
923
extern basic_block nearest_common_dominator (enum cdi_direction,
924
                                             basic_block, basic_block);
925
extern basic_block nearest_common_dominator_for_set (enum cdi_direction,
926
                                                     bitmap);
927
extern void set_immediate_dominator (enum cdi_direction, basic_block,
928
                                     basic_block);
929
extern basic_block get_immediate_dominator (enum cdi_direction, basic_block);
930
extern bool dominated_by_p (enum cdi_direction, const_basic_block, const_basic_block);
931
extern VEC (basic_block, heap) *get_dominated_by (enum cdi_direction, basic_block);
932
extern VEC (basic_block, heap) *get_dominated_by_region (enum cdi_direction,
933
                                                         basic_block *,
934
                                                         unsigned);
935
extern VEC (basic_block, heap) *get_all_dominated_blocks (enum cdi_direction,
936
                                                          basic_block);
937
extern void add_to_dominance_info (enum cdi_direction, basic_block);
938
extern void delete_from_dominance_info (enum cdi_direction, basic_block);
939
basic_block recompute_dominator (enum cdi_direction, basic_block);
940
extern void redirect_immediate_dominators (enum cdi_direction, basic_block,
941
                                           basic_block);
942
extern void iterate_fix_dominators (enum cdi_direction,
943
                                    VEC (basic_block, heap) *, bool);
944
extern void verify_dominators (enum cdi_direction);
945
extern basic_block first_dom_son (enum cdi_direction, basic_block);
946
extern basic_block next_dom_son (enum cdi_direction, basic_block);
947
unsigned bb_dom_dfs_in (enum cdi_direction, basic_block);
948
unsigned bb_dom_dfs_out (enum cdi_direction, basic_block);
949
 
950
extern edge try_redirect_by_replacing_jump (edge, basic_block, bool);
951
extern void break_superblocks (void);
952
extern void relink_block_chain (bool);
953
extern void check_bb_profile (basic_block, FILE *);
954
extern void update_bb_profile_for_threading (basic_block, int, gcov_type, edge);
955
extern void init_rtl_bb_info (basic_block);
956
 
957
extern void initialize_original_copy_tables (void);
958
extern void free_original_copy_tables (void);
959
extern void set_bb_original (basic_block, basic_block);
960
extern basic_block get_bb_original (basic_block);
961
extern void set_bb_copy (basic_block, basic_block);
962
extern basic_block get_bb_copy (basic_block);
963
void set_loop_copy (struct loop *, struct loop *);
964
struct loop *get_loop_copy (struct loop *);
965
 
966
 
967
extern rtx insert_insn_end_bb_new (rtx, basic_block);
968
 
969
#include "cfghooks.h"
970
 
971
/* Return true when one of the predecessor edges of BB is marked with EDGE_EH.  */
972
static inline bool
973
bb_has_eh_pred (basic_block bb)
974
{
975
  edge e;
976
  edge_iterator ei;
977
 
978
  FOR_EACH_EDGE (e, ei, bb->preds)
979
    {
980
      if (e->flags & EDGE_EH)
981
        return true;
982
    }
983
  return false;
984
}
985
 
986
/* Return true when one of the predecessor edges of BB is marked with EDGE_ABNORMAL.  */
987
static inline bool
988
bb_has_abnormal_pred (basic_block bb)
989
{
990
  edge e;
991
  edge_iterator ei;
992
 
993
  FOR_EACH_EDGE (e, ei, bb->preds)
994
    {
995
      if (e->flags & EDGE_ABNORMAL)
996
        return true;
997
    }
998
  return false;
999
}
1000
 
1001
/* In cfgloopmanip.c.  */
1002
extern edge mfb_kj_edge;
1003
extern bool mfb_keep_just (edge);
1004
 
1005
/* In cfgexpand.c.  */
1006
extern void rtl_profile_for_bb (basic_block);
1007
extern void rtl_profile_for_edge (edge);
1008
extern void default_rtl_profile (void);
1009
 
1010
#endif /* GCC_BASIC_BLOCK_H */

powered by: WebSVN 2.1.0

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