1 /* Define control flow data structures for the CFG.
2 Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004,
3 2005, 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
5 This file is part of GCC.
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
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
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/>. */
21 #ifndef GCC_BASIC_BLOCK_H
22 #define GCC_BASIC_BLOCK_H
28 /* Type we use to hold basic block counters. Should be at least
29 64bit. Although a counter cannot be negative, we use a signed
30 type, because erroneous negative counts can be generated when the
31 flow graph is manipulated by various optimizations. A signed type
32 makes those easy to detect. */
33 typedef HOST_WIDEST_INT gcov_type;
35 /* Control flow edge information. */
36 struct GTY(()) edge_def {
37 /* The two blocks at the ends of the edge. */
38 struct basic_block_def *src;
39 struct basic_block_def *dest;
41 /* Instructions queued on the edge. */
42 union edge_def_insns {
43 gimple_seq GTY ((tag ("true"))) g;
44 rtx GTY ((tag ("false"))) r;
45 } GTY ((desc ("current_ir_type () == IR_GIMPLE"))) insns;
47 /* Auxiliary info specific to a pass. */
48 PTR GTY ((skip (""))) aux;
50 /* Location of any goto implicit in the edge and associated BLOCK. */
52 location_t goto_locus;
54 /* The index number corresponding to this edge in the edge vector
56 unsigned int dest_idx;
58 int flags; /* see EDGE_* below */
59 int probability; /* biased by REG_BR_PROB_BASE */
60 gcov_type count; /* Expected number of executions calculated
65 DEF_VEC_ALLOC_P(edge,gc);
66 DEF_VEC_ALLOC_P(edge,heap);
68 /* Always update the table in cfg.c dump_edge_info. */
69 #define EDGE_FALLTHRU 0x0001 /* 'Straight line' flow */
70 #define EDGE_ABNORMAL 0x0002 /* Strange flow, like computed
72 #define EDGE_ABNORMAL_CALL 0x0004 /* Call with abnormal exit
73 like an exception, or sibcall */
74 #define EDGE_EH 0x0008 /* Exception throw */
75 #define EDGE_FAKE 0x0010 /* Not a real edge (profile.c) */
76 #define EDGE_DFS_BACK 0x0020 /* A backwards edge */
77 #define EDGE_CAN_FALLTHRU 0x0040 /* Candidate for straight line
79 #define EDGE_IRREDUCIBLE_LOOP 0x0080 /* Part of irreducible loop. */
80 #define EDGE_SIBCALL 0x0100 /* Edge from sibcall to exit. */
81 #define EDGE_LOOP_EXIT 0x0200 /* Exit of a loop. */
82 #define EDGE_TRUE_VALUE 0x0400 /* Edge taken when controlling
83 predicate is nonzero. */
84 #define EDGE_FALSE_VALUE 0x0800 /* Edge taken when controlling
86 #define EDGE_EXECUTABLE 0x1000 /* Edge is executable. Only
87 valid during SSA-CCP. */
88 #define EDGE_CROSSING 0x2000 /* Edge crosses between hot
89 and cold sections, when we
91 #define EDGE_PRESERVE 0x4000 /* Never merge blocks via this edge. */
92 #define EDGE_ALL_FLAGS 0x7fff
94 #define EDGE_COMPLEX \
95 (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_EH | EDGE_PRESERVE)
97 /* Counter summary from the last set of coverage counts read by
99 extern const struct gcov_ctr_summary *profile_info;
101 /* Declared in cfgloop.h. */
104 /* Declared in tree-flow.h. */
107 /* A basic block is a sequence of instructions with only entry and
108 only one exit. If any one of the instructions are executed, they
109 will all be executed, and in sequence from first to last.
111 There may be COND_EXEC instructions in the basic block. The
112 COND_EXEC *instructions* will be executed -- but if the condition
113 is false the conditionally executed *expressions* will of course
114 not be executed. We don't consider the conditionally executed
115 expression (which might have side-effects) to be in a separate
116 basic block because the program counter will always be at the same
117 location after the COND_EXEC instruction, regardless of whether the
118 condition is true or not.
120 Basic blocks need not start with a label nor end with a jump insn.
121 For example, a previous basic block may just "conditionally fall"
122 into the succeeding basic block, and the last basic block need not
123 end with a jump insn. Block 0 is a descendant of the entry block.
125 A basic block beginning with two labels cannot have notes between
128 Data for jump tables are stored in jump_insns that occur in no
129 basic block even though these insns can follow or precede insns in
132 /* Basic block information indexed by block number. */
133 struct GTY((chain_next ("%h.next_bb"), chain_prev ("%h.prev_bb"))) basic_block_def {
134 /* The edges into and out of the block. */
138 /* Auxiliary info specific to a pass. */
139 PTR GTY ((skip (""))) aux;
141 /* Innermost loop containing the block. */
142 struct loop *loop_father;
144 /* The dominance and postdominance information node. */
145 struct et_node * GTY ((skip (""))) dom[2];
147 /* Previous and next blocks in the chain. */
148 struct basic_block_def *prev_bb;
149 struct basic_block_def *next_bb;
151 union basic_block_il_dependent {
152 struct gimple_bb_info * GTY ((tag ("0"))) gimple;
153 struct rtl_bb_info * GTY ((tag ("1"))) rtl;
154 } GTY ((desc ("((%1.flags & BB_RTL) != 0)"))) il;
156 /* Expected number of executions: calculated in profile.c. */
159 /* The index of this block. */
162 /* The loop depth of this block. */
165 /* Expected frequency. Normalized to be in range 0 to BB_FREQ_MAX. */
168 /* The discriminator for this block. */
171 /* Various flags. See BB_* below. */
175 struct GTY(()) rtl_bb_info {
176 /* The first and last insns of the block. */
180 /* In CFGlayout mode points to insn notes/jumptables to be placed just before
181 and after the block. */
185 /* This field is used by the bb-reorder and tracer passes. */
189 struct GTY(()) gimple_bb_info {
190 /* Sequence of statements in this block. */
193 /* PHI nodes for this block. */
194 gimple_seq phi_nodes;
197 DEF_VEC_P(basic_block);
198 DEF_VEC_ALLOC_P(basic_block,gc);
199 DEF_VEC_ALLOC_P(basic_block,heap);
201 #define BB_FREQ_MAX 10000
203 /* Masks for basic_block.flags.
205 BB_HOT_PARTITION and BB_COLD_PARTITION should be preserved throughout
206 the compilation, so they are never cleared.
208 All other flags may be cleared by clear_bb_flags(). It is generally
209 a bad idea to rely on any flags being up-to-date.
211 Always update the table in cfg.c dump_bb_info. */
215 /* Only set on blocks that have just been created by create_bb. */
218 /* Set by find_unreachable_blocks. Do not rely on this being set in any
220 BB_REACHABLE = 1 << 1,
222 /* Set for blocks in an irreducible loop by loop analysis. */
223 BB_IRREDUCIBLE_LOOP = 1 << 2,
225 /* Set on blocks that may actually not be single-entry single-exit block. */
226 BB_SUPERBLOCK = 1 << 3,
228 /* Set on basic blocks that the scheduler should not touch. This is used
229 by SMS to prevent other schedulers from messing with the loop schedule. */
230 BB_DISABLE_SCHEDULE = 1 << 4,
232 /* Set on blocks that should be put in a hot section. */
233 BB_HOT_PARTITION = 1 << 5,
235 /* Set on blocks that should be put in a cold section. */
236 BB_COLD_PARTITION = 1 << 6,
238 /* Set on block that was duplicated. */
239 BB_DUPLICATED = 1 << 7,
241 /* Set if the label at the top of this block is the target of a non-local goto. */
242 BB_NON_LOCAL_GOTO_TARGET = 1 << 8,
244 /* Set on blocks that are in RTL format. */
247 /* Set on blocks that are forwarder blocks.
248 Only used in cfgcleanup.c. */
249 BB_FORWARDER_BLOCK = 1 << 10,
251 /* Set on blocks that cannot be threaded through.
252 Only used in cfgcleanup.c. */
253 BB_NONTHREADABLE_BLOCK = 1 << 11,
255 /* Set on blocks that were modified in some way. This bit is set in
256 df_set_bb_dirty, but not cleared by df_analyze, so it can be used
257 to test whether a block has been modified prior to a df_analyze
259 BB_MODIFIED = 1 << 12,
261 /* Set on blocks that are in a transaction. This is calculated on
262 demand, and is available after calling
263 compute_transaction_bits(). */
264 BB_IN_TRANSACTION = 1 << 13
267 /* Dummy flag for convenience in the hot/cold partitioning code. */
268 #define BB_UNPARTITIONED 0
270 /* Partitions, to be used when partitioning hot and cold basic blocks into
271 separate sections. */
272 #define BB_PARTITION(bb) ((bb)->flags & (BB_HOT_PARTITION|BB_COLD_PARTITION))
273 #define BB_SET_PARTITION(bb, part) do { \
274 basic_block bb_ = (bb); \
275 bb_->flags = ((bb_->flags & ~(BB_HOT_PARTITION|BB_COLD_PARTITION)) \
279 #define BB_COPY_PARTITION(dstbb, srcbb) \
280 BB_SET_PARTITION (dstbb, BB_PARTITION (srcbb))
282 /* State of dominance information. */
286 DOM_NONE, /* Not computed at all. */
287 DOM_NO_FAST_QUERY, /* The data is OK, but the fast query data are not usable. */
288 DOM_OK /* Everything is ok. */
291 /* What sort of profiling information we have. */
292 enum profile_status_d
297 PROFILE_LAST /* Last value, used by profile streaming. */
300 /* A structure to group all the per-function control flow graph data.
301 The x_* prefixing is necessary because otherwise references to the
302 fields of this struct are interpreted as the defines for backward
303 source compatibility following the definition of this struct. */
304 struct GTY(()) control_flow_graph {
305 /* Block pointers for the exit and entry of a function.
306 These are always the head and tail of the basic block list. */
307 basic_block x_entry_block_ptr;
308 basic_block x_exit_block_ptr;
310 /* Index by basic block number, get basic block struct info. */
311 VEC(basic_block,gc) *x_basic_block_info;
313 /* Number of basic blocks in this flow graph. */
314 int x_n_basic_blocks;
316 /* Number of edges in this flow graph. */
319 /* The first free basic block number. */
320 int x_last_basic_block;
322 /* UIDs for LABEL_DECLs. */
325 /* Mapping of labels to their associated blocks. At present
326 only used for the gimple CFG. */
327 VEC(basic_block,gc) *x_label_to_block_map;
329 enum profile_status_d x_profile_status;
331 /* Whether the dominators and the postdominators are available. */
332 enum dom_state x_dom_computed[2];
334 /* Number of basic blocks in the dominance tree. */
335 unsigned x_n_bbs_in_dom_tree[2];
337 /* Maximal number of entities in the single jumptable. Used to estimate
338 final flowgraph size. */
339 int max_jumptable_ents;
342 /* Defines for accessing the fields of the CFG structure for function FN. */
343 #define ENTRY_BLOCK_PTR_FOR_FUNCTION(FN) ((FN)->cfg->x_entry_block_ptr)
344 #define EXIT_BLOCK_PTR_FOR_FUNCTION(FN) ((FN)->cfg->x_exit_block_ptr)
345 #define basic_block_info_for_function(FN) ((FN)->cfg->x_basic_block_info)
346 #define n_basic_blocks_for_function(FN) ((FN)->cfg->x_n_basic_blocks)
347 #define n_edges_for_function(FN) ((FN)->cfg->x_n_edges)
348 #define last_basic_block_for_function(FN) ((FN)->cfg->x_last_basic_block)
349 #define label_to_block_map_for_function(FN) ((FN)->cfg->x_label_to_block_map)
350 #define profile_status_for_function(FN) ((FN)->cfg->x_profile_status)
352 #define BASIC_BLOCK_FOR_FUNCTION(FN,N) \
353 (VEC_index (basic_block, basic_block_info_for_function(FN), (N)))
354 #define SET_BASIC_BLOCK_FOR_FUNCTION(FN,N,BB) \
355 (VEC_replace (basic_block, basic_block_info_for_function(FN), (N), (BB)))
357 /* Defines for textual backward source compatibility. */
358 #define ENTRY_BLOCK_PTR (cfun->cfg->x_entry_block_ptr)
359 #define EXIT_BLOCK_PTR (cfun->cfg->x_exit_block_ptr)
360 #define basic_block_info (cfun->cfg->x_basic_block_info)
361 #define n_basic_blocks (cfun->cfg->x_n_basic_blocks)
362 #define n_edges (cfun->cfg->x_n_edges)
363 #define last_basic_block (cfun->cfg->x_last_basic_block)
364 #define label_to_block_map (cfun->cfg->x_label_to_block_map)
365 #define profile_status (cfun->cfg->x_profile_status)
367 #define BASIC_BLOCK(N) (VEC_index (basic_block, basic_block_info, (N)))
368 #define SET_BASIC_BLOCK(N,BB) (VEC_replace (basic_block, basic_block_info, (N), (BB)))
370 /* For iterating over basic blocks. */
371 #define FOR_BB_BETWEEN(BB, FROM, TO, DIR) \
372 for (BB = FROM; BB != TO; BB = BB->DIR)
374 #define FOR_EACH_BB_FN(BB, FN) \
375 FOR_BB_BETWEEN (BB, (FN)->cfg->x_entry_block_ptr->next_bb, (FN)->cfg->x_exit_block_ptr, next_bb)
377 #define FOR_EACH_BB(BB) FOR_EACH_BB_FN (BB, cfun)
379 #define FOR_EACH_BB_REVERSE_FN(BB, FN) \
380 FOR_BB_BETWEEN (BB, (FN)->cfg->x_exit_block_ptr->prev_bb, (FN)->cfg->x_entry_block_ptr, prev_bb)
382 #define FOR_EACH_BB_REVERSE(BB) FOR_EACH_BB_REVERSE_FN(BB, cfun)
384 /* For iterating over insns in basic block. */
385 #define FOR_BB_INSNS(BB, INSN) \
386 for ((INSN) = BB_HEAD (BB); \
387 (INSN) && (INSN) != NEXT_INSN (BB_END (BB)); \
388 (INSN) = NEXT_INSN (INSN))
390 /* For iterating over insns in basic block when we might remove the
392 #define FOR_BB_INSNS_SAFE(BB, INSN, CURR) \
393 for ((INSN) = BB_HEAD (BB), (CURR) = (INSN) ? NEXT_INSN ((INSN)): NULL; \
394 (INSN) && (INSN) != NEXT_INSN (BB_END (BB)); \
395 (INSN) = (CURR), (CURR) = (INSN) ? NEXT_INSN ((INSN)) : NULL)
397 #define FOR_BB_INSNS_REVERSE(BB, INSN) \
398 for ((INSN) = BB_END (BB); \
399 (INSN) && (INSN) != PREV_INSN (BB_HEAD (BB)); \
400 (INSN) = PREV_INSN (INSN))
402 #define FOR_BB_INSNS_REVERSE_SAFE(BB, INSN, CURR) \
403 for ((INSN) = BB_END (BB),(CURR) = (INSN) ? PREV_INSN ((INSN)) : NULL; \
404 (INSN) && (INSN) != PREV_INSN (BB_HEAD (BB)); \
405 (INSN) = (CURR), (CURR) = (INSN) ? PREV_INSN ((INSN)) : NULL)
407 /* Cycles through _all_ basic blocks, even the fake ones (entry and
410 #define FOR_ALL_BB(BB) \
411 for (BB = ENTRY_BLOCK_PTR; BB; BB = BB->next_bb)
413 #define FOR_ALL_BB_FN(BB, FN) \
414 for (BB = ENTRY_BLOCK_PTR_FOR_FUNCTION (FN); BB; BB = BB->next_bb)
417 /* Stuff for recording basic block info. */
419 #define BB_HEAD(B) (B)->il.rtl->head_
420 #define BB_END(B) (B)->il.rtl->end_
422 /* Special block numbers [markers] for entry and exit.
423 Neither of them is supposed to hold actual statements. */
424 #define ENTRY_BLOCK (0)
425 #define EXIT_BLOCK (1)
427 /* The two blocks that are always in the cfg. */
428 #define NUM_FIXED_BLOCKS (2)
430 #define set_block_for_insn(INSN, BB) (BLOCK_FOR_INSN (INSN) = BB)
432 extern void compute_bb_for_insn (void);
433 extern unsigned int free_bb_for_insn (void);
434 extern void update_bb_for_insn (basic_block);
436 extern void insert_insn_on_edge (rtx, edge);
437 basic_block split_edge_and_insert (edge, rtx);
439 extern void commit_one_edge_insertion (edge e);
440 extern void commit_edge_insertions (void);
442 extern void remove_fake_edges (void);
443 extern void remove_fake_exit_edges (void);
444 extern void add_noreturn_fake_exit_edges (void);
445 extern void connect_infinite_loops_to_exit (void);
446 extern edge unchecked_make_edge (basic_block, basic_block, int);
447 extern edge cached_make_edge (sbitmap, basic_block, basic_block, int);
448 extern edge make_edge (basic_block, basic_block, int);
449 extern edge make_single_succ_edge (basic_block, basic_block, int);
450 extern void remove_edge_raw (edge);
451 extern void redirect_edge_succ (edge, basic_block);
452 extern edge redirect_edge_succ_nodup (edge, basic_block);
453 extern void redirect_edge_pred (edge, basic_block);
454 extern basic_block create_basic_block_structure (rtx, rtx, rtx, basic_block);
455 extern void clear_bb_flags (void);
456 extern int post_order_compute (int *, bool, bool);
457 extern int inverted_post_order_compute (int *);
458 extern int pre_and_rev_post_order_compute (int *, int *, bool);
459 extern int dfs_enumerate_from (basic_block, int,
460 bool (*)(const_basic_block, const void *),
461 basic_block *, int, const void *);
462 extern void compute_dominance_frontiers (struct bitmap_head_def *);
463 extern bitmap compute_idf (bitmap, struct bitmap_head_def *);
464 extern void dump_bb_info (basic_block, bool, bool, int, const char *, FILE *);
465 extern void dump_edge_info (FILE *, edge, int);
466 extern void brief_dump_cfg (FILE *);
467 extern void clear_edges (void);
468 extern void scale_bbs_frequencies_int (basic_block *, int, int, int);
469 extern void scale_bbs_frequencies_gcov_type (basic_block *, int, gcov_type,
472 /* Structure to group all of the information to process IF-THEN and
473 IF-THEN-ELSE blocks for the conditional execution support. This
474 needs to be in a public file in case the IFCVT macros call
475 functions passing the ce_if_block data structure. */
477 typedef struct ce_if_block
479 basic_block test_bb; /* First test block. */
480 basic_block then_bb; /* THEN block. */
481 basic_block else_bb; /* ELSE block or NULL. */
482 basic_block join_bb; /* Join THEN/ELSE blocks. */
483 basic_block last_test_bb; /* Last bb to hold && or || tests. */
484 int num_multiple_test_blocks; /* # of && and || basic blocks. */
485 int num_and_and_blocks; /* # of && blocks. */
486 int num_or_or_blocks; /* # of || blocks. */
487 int num_multiple_test_insns; /* # of insns in && and || blocks. */
488 int and_and_p; /* Complex test is &&. */
489 int num_then_insns; /* # of insns in THEN block. */
490 int num_else_insns; /* # of insns in ELSE block. */
491 int pass; /* Pass number. */
493 #ifdef IFCVT_EXTRA_FIELDS
494 IFCVT_EXTRA_FIELDS /* Any machine dependent fields. */
499 /* This structure maintains an edge list vector. */
507 /* The base value for branch probability notes and edge probabilities. */
508 #define REG_BR_PROB_BASE 10000
510 /* This is the value which indicates no edge is present. */
511 #define EDGE_INDEX_NO_EDGE -1
513 /* EDGE_INDEX returns an integer index for an edge, or EDGE_INDEX_NO_EDGE
514 if there is no edge between the 2 basic blocks. */
515 #define EDGE_INDEX(el, pred, succ) (find_edge_index ((el), (pred), (succ)))
517 /* INDEX_EDGE_PRED_BB and INDEX_EDGE_SUCC_BB return a pointer to the basic
518 block which is either the pred or succ end of the indexed edge. */
519 #define INDEX_EDGE_PRED_BB(el, index) ((el)->index_to_edge[(index)]->src)
520 #define INDEX_EDGE_SUCC_BB(el, index) ((el)->index_to_edge[(index)]->dest)
522 /* INDEX_EDGE returns a pointer to the edge. */
523 #define INDEX_EDGE(el, index) ((el)->index_to_edge[(index)])
525 /* Number of edges in the compressed edge list. */
526 #define NUM_EDGES(el) ((el)->num_edges)
528 /* BB is assumed to contain conditional jump. Return the fallthru edge. */
529 #define FALLTHRU_EDGE(bb) (EDGE_SUCC ((bb), 0)->flags & EDGE_FALLTHRU \
530 ? EDGE_SUCC ((bb), 0) : EDGE_SUCC ((bb), 1))
532 /* BB is assumed to contain conditional jump. Return the branch edge. */
533 #define BRANCH_EDGE(bb) (EDGE_SUCC ((bb), 0)->flags & EDGE_FALLTHRU \
534 ? EDGE_SUCC ((bb), 1) : EDGE_SUCC ((bb), 0))
536 /* Return expected execution frequency of the edge E. */
537 #define EDGE_FREQUENCY(e) (((e)->src->frequency \
539 + REG_BR_PROB_BASE / 2) \
542 /* Return nonzero if edge is critical. */
543 #define EDGE_CRITICAL_P(e) (EDGE_COUNT ((e)->src->succs) >= 2 \
544 && EDGE_COUNT ((e)->dest->preds) >= 2)
546 #define EDGE_COUNT(ev) VEC_length (edge, (ev))
547 #define EDGE_I(ev,i) VEC_index (edge, (ev), (i))
548 #define EDGE_PRED(bb,i) VEC_index (edge, (bb)->preds, (i))
549 #define EDGE_SUCC(bb,i) VEC_index (edge, (bb)->succs, (i))
551 /* Returns true if BB has precisely one successor. */
554 single_succ_p (const_basic_block bb)
556 return EDGE_COUNT (bb->succs) == 1;
559 /* Returns true if BB has precisely one predecessor. */
562 single_pred_p (const_basic_block bb)
564 return EDGE_COUNT (bb->preds) == 1;
567 /* Returns the single successor edge of basic block BB. Aborts if
568 BB does not have exactly one successor. */
571 single_succ_edge (const_basic_block bb)
573 gcc_checking_assert (single_succ_p (bb));
574 return EDGE_SUCC (bb, 0);
577 /* Returns the single predecessor edge of basic block BB. Aborts
578 if BB does not have exactly one predecessor. */
581 single_pred_edge (const_basic_block bb)
583 gcc_checking_assert (single_pred_p (bb));
584 return EDGE_PRED (bb, 0);
587 /* Returns the single successor block of basic block BB. Aborts
588 if BB does not have exactly one successor. */
590 static inline basic_block
591 single_succ (const_basic_block bb)
593 return single_succ_edge (bb)->dest;
596 /* Returns the single predecessor block of basic block BB. Aborts
597 if BB does not have exactly one predecessor.*/
599 static inline basic_block
600 single_pred (const_basic_block bb)
602 return single_pred_edge (bb)->src;
605 /* Iterator object for edges. */
609 VEC(edge,gc) **container;
612 static inline VEC(edge,gc) *
613 ei_container (edge_iterator i)
615 gcc_checking_assert (i.container);
619 #define ei_start(iter) ei_start_1 (&(iter))
620 #define ei_last(iter) ei_last_1 (&(iter))
622 /* Return an iterator pointing to the start of an edge vector. */
623 static inline edge_iterator
624 ei_start_1 (VEC(edge,gc) **ev)
634 /* Return an iterator pointing to the last element of an edge
636 static inline edge_iterator
637 ei_last_1 (VEC(edge,gc) **ev)
641 i.index = EDGE_COUNT (*ev) - 1;
647 /* Is the iterator `i' at the end of the sequence? */
649 ei_end_p (edge_iterator i)
651 return (i.index == EDGE_COUNT (ei_container (i)));
654 /* Is the iterator `i' at one position before the end of the
657 ei_one_before_end_p (edge_iterator i)
659 return (i.index + 1 == EDGE_COUNT (ei_container (i)));
662 /* Advance the iterator to the next element. */
664 ei_next (edge_iterator *i)
666 gcc_checking_assert (i->index < EDGE_COUNT (ei_container (*i)));
670 /* Move the iterator to the previous element. */
672 ei_prev (edge_iterator *i)
674 gcc_checking_assert (i->index > 0);
678 /* Return the edge pointed to by the iterator `i'. */
680 ei_edge (edge_iterator i)
682 return EDGE_I (ei_container (i), i.index);
685 /* Return an edge pointed to by the iterator. Do it safely so that
686 NULL is returned when the iterator is pointing at the end of the
689 ei_safe_edge (edge_iterator i)
691 return !ei_end_p (i) ? ei_edge (i) : NULL;
694 /* Return 1 if we should continue to iterate. Return 0 otherwise.
695 *Edge P is set to the next edge if we are to continue to iterate
696 and NULL otherwise. */
699 ei_cond (edge_iterator ei, edge *p)
713 /* This macro serves as a convenient way to iterate each edge in a
714 vector of predecessor or successor edges. It must not be used when
715 an element might be removed during the traversal, otherwise
716 elements will be missed. Instead, use a for-loop like that shown
717 in the following pseudo-code:
719 FOR (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
728 #define FOR_EACH_EDGE(EDGE,ITER,EDGE_VEC) \
729 for ((ITER) = ei_start ((EDGE_VEC)); \
730 ei_cond ((ITER), &(EDGE)); \
733 struct edge_list * create_edge_list (void);
734 void free_edge_list (struct edge_list *);
735 void print_edge_list (FILE *, struct edge_list *);
736 void verify_edge_list (FILE *, struct edge_list *);
737 int find_edge_index (struct edge_list *, basic_block, basic_block);
738 edge find_edge (basic_block, basic_block);
740 #define CLEANUP_EXPENSIVE 1 /* Do relatively expensive optimizations
741 except for edge forwarding */
742 #define CLEANUP_CROSSJUMP 2 /* Do crossjumping. */
743 #define CLEANUP_POST_REGSTACK 4 /* We run after reg-stack and need
744 to care REG_DEAD notes. */
745 #define CLEANUP_THREADING 8 /* Do jump threading. */
746 #define CLEANUP_NO_INSN_DEL 16 /* Do not try to delete trivially dead
748 #define CLEANUP_CFGLAYOUT 32 /* Do cleanup in cfglayout mode. */
751 extern struct edge_list *pre_edge_lcm (int, sbitmap *, sbitmap *,
752 sbitmap *, sbitmap *, sbitmap **,
754 extern struct edge_list *pre_edge_rev_lcm (int, sbitmap *,
755 sbitmap *, sbitmap *,
756 sbitmap *, sbitmap **,
758 extern void compute_available (sbitmap *, sbitmap *, sbitmap *, sbitmap *);
761 extern bool maybe_hot_bb_p (const_basic_block);
762 extern bool maybe_hot_edge_p (edge);
763 extern bool probably_never_executed_bb_p (const_basic_block);
764 extern bool optimize_bb_for_size_p (const_basic_block);
765 extern bool optimize_bb_for_speed_p (const_basic_block);
766 extern bool optimize_edge_for_size_p (edge);
767 extern bool optimize_edge_for_speed_p (edge);
768 extern bool optimize_loop_for_size_p (struct loop *);
769 extern bool optimize_loop_for_speed_p (struct loop *);
770 extern bool optimize_loop_nest_for_size_p (struct loop *);
771 extern bool optimize_loop_nest_for_speed_p (struct loop *);
772 extern bool gimple_predicted_by_p (const_basic_block, enum br_predictor);
773 extern bool rtl_predicted_by_p (const_basic_block, enum br_predictor);
774 extern void gimple_predict_edge (edge, enum br_predictor, int);
775 extern void rtl_predict_edge (edge, enum br_predictor, int);
776 extern void predict_edge_def (edge, enum br_predictor, enum prediction);
777 extern void guess_outgoing_edge_probabilities (basic_block);
778 extern void remove_predictions_associated_with_edge (edge);
779 extern bool edge_probability_reliable_p (const_edge);
780 extern bool br_prob_note_reliable_p (const_rtx);
781 extern bool predictable_edge_p (edge);
784 extern void init_flow (struct function *);
785 extern void debug_bb (basic_block);
786 extern basic_block debug_bb_n (int);
787 extern void expunge_block (basic_block);
788 extern void link_block (basic_block, basic_block);
789 extern void unlink_block (basic_block);
790 extern void compact_blocks (void);
791 extern basic_block alloc_block (void);
792 extern void alloc_aux_for_blocks (int);
793 extern void clear_aux_for_blocks (void);
794 extern void free_aux_for_blocks (void);
795 extern void alloc_aux_for_edge (edge, int);
796 extern void alloc_aux_for_edges (int);
797 extern void clear_aux_for_edges (void);
798 extern void free_aux_for_edges (void);
801 extern void find_unreachable_blocks (void);
802 extern bool forwarder_block_p (const_basic_block);
803 extern bool can_fallthru (basic_block, basic_block);
804 extern bool could_fall_through (basic_block, basic_block);
805 extern void flow_nodes_print (const char *, const_sbitmap, FILE *);
806 extern void flow_edge_list_print (const char *, const edge *, int, FILE *);
809 extern rtx block_label (basic_block);
810 extern rtx bb_note (basic_block);
811 extern bool purge_all_dead_edges (void);
812 extern bool purge_dead_edges (basic_block);
813 extern bool fixup_abnormal_edges (void);
814 extern basic_block force_nonfallthru_and_redirect (edge, basic_block, rtx);
817 extern void find_many_sub_basic_blocks (sbitmap);
818 extern void rtl_make_eh_edge (sbitmap, basic_block, rtx);
820 enum replace_direction { dir_none, dir_forward, dir_backward, dir_both };
822 /* In cfgcleanup.c. */
823 extern bool cleanup_cfg (int);
824 extern int flow_find_cross_jump (basic_block, basic_block, rtx *, rtx *,
825 enum replace_direction*);
826 extern int flow_find_head_matching_sequence (basic_block, basic_block,
829 extern bool delete_unreachable_blocks (void);
831 extern bool mark_dfs_back_edges (void);
832 extern void set_edge_can_fallthru_flag (void);
833 extern void update_br_prob_note (basic_block);
834 extern bool inside_basic_block_p (const_rtx);
835 extern bool control_flow_insn_p (const_rtx);
836 extern rtx get_last_bb_insn (basic_block);
838 /* In bb-reorder.c */
839 extern void reorder_basic_blocks (void);
846 CDI_POST_DOMINATORS = 2
849 extern enum dom_state dom_info_state (enum cdi_direction);
850 extern void set_dom_info_availability (enum cdi_direction, enum dom_state);
851 extern bool dom_info_available_p (enum cdi_direction);
852 extern void calculate_dominance_info (enum cdi_direction);
853 extern void free_dominance_info (enum cdi_direction);
854 extern basic_block nearest_common_dominator (enum cdi_direction,
855 basic_block, basic_block);
856 extern basic_block nearest_common_dominator_for_set (enum cdi_direction,
858 extern void set_immediate_dominator (enum cdi_direction, basic_block,
860 extern basic_block get_immediate_dominator (enum cdi_direction, basic_block);
861 extern bool dominated_by_p (enum cdi_direction, const_basic_block, const_basic_block);
862 extern VEC (basic_block, heap) *get_dominated_by (enum cdi_direction, basic_block);
863 extern VEC (basic_block, heap) *get_dominated_by_region (enum cdi_direction,
866 extern VEC (basic_block, heap) *get_dominated_to_depth (enum cdi_direction,
868 extern VEC (basic_block, heap) *get_all_dominated_blocks (enum cdi_direction,
870 extern void add_to_dominance_info (enum cdi_direction, basic_block);
871 extern void delete_from_dominance_info (enum cdi_direction, basic_block);
872 basic_block recompute_dominator (enum cdi_direction, basic_block);
873 extern void redirect_immediate_dominators (enum cdi_direction, basic_block,
875 extern void iterate_fix_dominators (enum cdi_direction,
876 VEC (basic_block, heap) *, bool);
877 extern void verify_dominators (enum cdi_direction);
878 extern basic_block first_dom_son (enum cdi_direction, basic_block);
879 extern basic_block next_dom_son (enum cdi_direction, basic_block);
880 unsigned bb_dom_dfs_in (enum cdi_direction, basic_block);
881 unsigned bb_dom_dfs_out (enum cdi_direction, basic_block);
883 extern edge try_redirect_by_replacing_jump (edge, basic_block, bool);
884 extern void break_superblocks (void);
885 extern void relink_block_chain (bool);
886 extern void check_bb_profile (basic_block, FILE *);
887 extern void update_bb_profile_for_threading (basic_block, int, gcov_type, edge);
888 extern void init_rtl_bb_info (basic_block);
890 extern void initialize_original_copy_tables (void);
891 extern void free_original_copy_tables (void);
892 extern void set_bb_original (basic_block, basic_block);
893 extern basic_block get_bb_original (basic_block);
894 extern void set_bb_copy (basic_block, basic_block);
895 extern basic_block get_bb_copy (basic_block);
896 void set_loop_copy (struct loop *, struct loop *);
897 struct loop *get_loop_copy (struct loop *);
899 #include "cfghooks.h"
901 /* Return true when one of the predecessor edges of BB is marked with EDGE_EH. */
903 bb_has_eh_pred (basic_block bb)
908 FOR_EACH_EDGE (e, ei, bb->preds)
910 if (e->flags & EDGE_EH)
916 /* Return true when one of the predecessor edges of BB is marked with EDGE_ABNORMAL. */
918 bb_has_abnormal_pred (basic_block bb)
923 FOR_EACH_EDGE (e, ei, bb->preds)
925 if (e->flags & EDGE_ABNORMAL)
931 /* Return the fallthru edge in EDGES if it exists, NULL otherwise. */
933 find_fallthru_edge (VEC(edge,gc) *edges)
938 FOR_EACH_EDGE (e, ei, edges)
939 if (e->flags & EDGE_FALLTHRU)
945 /* In cfgloopmanip.c. */
946 extern edge mfb_kj_edge;
947 extern bool mfb_keep_just (edge);
949 /* In cfgexpand.c. */
950 extern void rtl_profile_for_bb (basic_block);
951 extern void rtl_profile_for_edge (edge);
952 extern void default_rtl_profile (void);
954 #endif /* GCC_BASIC_BLOCK_H */