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 struct GTY(()) rtl_bb_info {
105 /* The first insn of the block is embedded into bb->il.x. */
106 /* The last insn of the block. */
109 /* In CFGlayout mode points to insn notes/jumptables to be placed just before
110 and after the block. */
115 struct GTY(()) gimple_bb_info {
116 /* Sequence of statements in this block. */
119 /* PHI nodes for this block. */
120 gimple_seq phi_nodes;
123 /* A basic block is a sequence of instructions with only entry and
124 only one exit. If any one of the instructions are executed, they
125 will all be executed, and in sequence from first to last.
127 There may be COND_EXEC instructions in the basic block. The
128 COND_EXEC *instructions* will be executed -- but if the condition
129 is false the conditionally executed *expressions* will of course
130 not be executed. We don't consider the conditionally executed
131 expression (which might have side-effects) to be in a separate
132 basic block because the program counter will always be at the same
133 location after the COND_EXEC instruction, regardless of whether the
134 condition is true or not.
136 Basic blocks need not start with a label nor end with a jump insn.
137 For example, a previous basic block may just "conditionally fall"
138 into the succeeding basic block, and the last basic block need not
139 end with a jump insn. Block 0 is a descendant of the entry block.
141 A basic block beginning with two labels cannot have notes between
144 Data for jump tables are stored in jump_insns that occur in no
145 basic block even though these insns can follow or precede insns in
148 /* Basic block information indexed by block number. */
149 struct GTY((chain_next ("%h.next_bb"), chain_prev ("%h.prev_bb"))) basic_block_def {
150 /* The edges into and out of the block. */
154 /* Auxiliary info specific to a pass. */
155 PTR GTY ((skip (""))) aux;
157 /* Innermost loop containing the block. */
158 struct loop *loop_father;
160 /* The dominance and postdominance information node. */
161 struct et_node * GTY ((skip (""))) dom[2];
163 /* Previous and next blocks in the chain. */
164 struct basic_block_def *prev_bb;
165 struct basic_block_def *next_bb;
167 union basic_block_il_dependent {
168 struct gimple_bb_info GTY ((tag ("0"))) gimple;
171 struct rtl_bb_info * rtl;
172 } GTY ((tag ("1"))) x;
173 } GTY ((desc ("((%1.flags & BB_RTL) != 0)"))) il;
175 /* Expected number of executions: calculated in profile.c. */
178 /* The index of this block. */
181 /* The loop depth of this block. */
184 /* Expected frequency. Normalized to be in range 0 to BB_FREQ_MAX. */
187 /* The discriminator for this block. */
190 /* Various flags. See BB_* below. */
194 /* This ensures that struct gimple_bb_info is smaller than
195 struct rtl_bb_info, so that inlining the former into basic_block_def
196 is the better choice. */
197 typedef int __assert_gimple_bb_smaller_rtl_bb
198 [(int)sizeof(struct rtl_bb_info)
199 - (int)sizeof (struct gimple_bb_info)];
201 DEF_VEC_P(basic_block);
202 DEF_VEC_ALLOC_P(basic_block,gc);
203 DEF_VEC_ALLOC_P(basic_block,heap);
205 #define BB_FREQ_MAX 10000
207 /* Masks for basic_block.flags.
209 BB_HOT_PARTITION and BB_COLD_PARTITION should be preserved throughout
210 the compilation, so they are never cleared.
212 All other flags may be cleared by clear_bb_flags(). It is generally
213 a bad idea to rely on any flags being up-to-date.
215 Always update the table in cfg.c dump_bb_info. */
219 /* Only set on blocks that have just been created by create_bb. */
222 /* Set by find_unreachable_blocks. Do not rely on this being set in any
224 BB_REACHABLE = 1 << 1,
226 /* Set for blocks in an irreducible loop by loop analysis. */
227 BB_IRREDUCIBLE_LOOP = 1 << 2,
229 /* Set on blocks that may actually not be single-entry single-exit block. */
230 BB_SUPERBLOCK = 1 << 3,
232 /* Set on basic blocks that the scheduler should not touch. This is used
233 by SMS to prevent other schedulers from messing with the loop schedule. */
234 BB_DISABLE_SCHEDULE = 1 << 4,
236 /* Set on blocks that should be put in a hot section. */
237 BB_HOT_PARTITION = 1 << 5,
239 /* Set on blocks that should be put in a cold section. */
240 BB_COLD_PARTITION = 1 << 6,
242 /* Set on block that was duplicated. */
243 BB_DUPLICATED = 1 << 7,
245 /* Set if the label at the top of this block is the target of a non-local goto. */
246 BB_NON_LOCAL_GOTO_TARGET = 1 << 8,
248 /* Set on blocks that are in RTL format. */
251 /* Set on blocks that are forwarder blocks.
252 Only used in cfgcleanup.c. */
253 BB_FORWARDER_BLOCK = 1 << 10,
255 /* Set on blocks that cannot be threaded through.
256 Only used in cfgcleanup.c. */
257 BB_NONTHREADABLE_BLOCK = 1 << 11,
259 /* Set on blocks that were modified in some way. This bit is set in
260 df_set_bb_dirty, but not cleared by df_analyze, so it can be used
261 to test whether a block has been modified prior to a df_analyze
263 BB_MODIFIED = 1 << 12,
265 /* A general visited flag for passes to use. */
266 BB_VISITED = 1 << 13,
268 /* Set on blocks that are in a transaction. This is calculated on
269 demand, and is available after calling
270 compute_transaction_bits(). */
271 BB_IN_TRANSACTION = 1 << 14
274 /* Dummy flag for convenience in the hot/cold partitioning code. */
275 #define BB_UNPARTITIONED 0
277 /* Partitions, to be used when partitioning hot and cold basic blocks into
278 separate sections. */
279 #define BB_PARTITION(bb) ((bb)->flags & (BB_HOT_PARTITION|BB_COLD_PARTITION))
280 #define BB_SET_PARTITION(bb, part) do { \
281 basic_block bb_ = (bb); \
282 bb_->flags = ((bb_->flags & ~(BB_HOT_PARTITION|BB_COLD_PARTITION)) \
286 #define BB_COPY_PARTITION(dstbb, srcbb) \
287 BB_SET_PARTITION (dstbb, BB_PARTITION (srcbb))
289 /* State of dominance information. */
293 DOM_NONE, /* Not computed at all. */
294 DOM_NO_FAST_QUERY, /* The data is OK, but the fast query data are not usable. */
295 DOM_OK /* Everything is ok. */
298 /* What sort of profiling information we have. */
299 enum profile_status_d
304 PROFILE_LAST /* Last value, used by profile streaming. */
307 /* A structure to group all the per-function control flow graph data.
308 The x_* prefixing is necessary because otherwise references to the
309 fields of this struct are interpreted as the defines for backward
310 source compatibility following the definition of this struct. */
311 struct GTY(()) control_flow_graph {
312 /* Block pointers for the exit and entry of a function.
313 These are always the head and tail of the basic block list. */
314 basic_block x_entry_block_ptr;
315 basic_block x_exit_block_ptr;
317 /* Index by basic block number, get basic block struct info. */
318 VEC(basic_block,gc) *x_basic_block_info;
320 /* Number of basic blocks in this flow graph. */
321 int x_n_basic_blocks;
323 /* Number of edges in this flow graph. */
326 /* The first free basic block number. */
327 int x_last_basic_block;
329 /* UIDs for LABEL_DECLs. */
332 /* Mapping of labels to their associated blocks. At present
333 only used for the gimple CFG. */
334 VEC(basic_block,gc) *x_label_to_block_map;
336 enum profile_status_d x_profile_status;
338 /* Whether the dominators and the postdominators are available. */
339 enum dom_state x_dom_computed[2];
341 /* Number of basic blocks in the dominance tree. */
342 unsigned x_n_bbs_in_dom_tree[2];
344 /* Maximal number of entities in the single jumptable. Used to estimate
345 final flowgraph size. */
346 int max_jumptable_ents;
349 /* Defines for accessing the fields of the CFG structure for function FN. */
350 #define ENTRY_BLOCK_PTR_FOR_FUNCTION(FN) ((FN)->cfg->x_entry_block_ptr)
351 #define EXIT_BLOCK_PTR_FOR_FUNCTION(FN) ((FN)->cfg->x_exit_block_ptr)
352 #define basic_block_info_for_function(FN) ((FN)->cfg->x_basic_block_info)
353 #define n_basic_blocks_for_function(FN) ((FN)->cfg->x_n_basic_blocks)
354 #define n_edges_for_function(FN) ((FN)->cfg->x_n_edges)
355 #define last_basic_block_for_function(FN) ((FN)->cfg->x_last_basic_block)
356 #define label_to_block_map_for_function(FN) ((FN)->cfg->x_label_to_block_map)
357 #define profile_status_for_function(FN) ((FN)->cfg->x_profile_status)
359 #define BASIC_BLOCK_FOR_FUNCTION(FN,N) \
360 (VEC_index (basic_block, basic_block_info_for_function(FN), (N)))
361 #define SET_BASIC_BLOCK_FOR_FUNCTION(FN,N,BB) \
362 (VEC_replace (basic_block, basic_block_info_for_function(FN), (N), (BB)))
364 /* Defines for textual backward source compatibility. */
365 #define ENTRY_BLOCK_PTR (cfun->cfg->x_entry_block_ptr)
366 #define EXIT_BLOCK_PTR (cfun->cfg->x_exit_block_ptr)
367 #define basic_block_info (cfun->cfg->x_basic_block_info)
368 #define n_basic_blocks (cfun->cfg->x_n_basic_blocks)
369 #define n_edges (cfun->cfg->x_n_edges)
370 #define last_basic_block (cfun->cfg->x_last_basic_block)
371 #define label_to_block_map (cfun->cfg->x_label_to_block_map)
372 #define profile_status (cfun->cfg->x_profile_status)
374 #define BASIC_BLOCK(N) (VEC_index (basic_block, basic_block_info, (N)))
375 #define SET_BASIC_BLOCK(N,BB) (VEC_replace (basic_block, basic_block_info, (N), (BB)))
377 /* For iterating over basic blocks. */
378 #define FOR_BB_BETWEEN(BB, FROM, TO, DIR) \
379 for (BB = FROM; BB != TO; BB = BB->DIR)
381 #define FOR_EACH_BB_FN(BB, FN) \
382 FOR_BB_BETWEEN (BB, (FN)->cfg->x_entry_block_ptr->next_bb, (FN)->cfg->x_exit_block_ptr, next_bb)
384 #define FOR_EACH_BB(BB) FOR_EACH_BB_FN (BB, cfun)
386 #define FOR_EACH_BB_REVERSE_FN(BB, FN) \
387 FOR_BB_BETWEEN (BB, (FN)->cfg->x_exit_block_ptr->prev_bb, (FN)->cfg->x_entry_block_ptr, prev_bb)
389 #define FOR_EACH_BB_REVERSE(BB) FOR_EACH_BB_REVERSE_FN(BB, cfun)
391 /* For iterating over insns in basic block. */
392 #define FOR_BB_INSNS(BB, INSN) \
393 for ((INSN) = BB_HEAD (BB); \
394 (INSN) && (INSN) != NEXT_INSN (BB_END (BB)); \
395 (INSN) = NEXT_INSN (INSN))
397 /* For iterating over insns in basic block when we might remove the
399 #define FOR_BB_INSNS_SAFE(BB, INSN, CURR) \
400 for ((INSN) = BB_HEAD (BB), (CURR) = (INSN) ? NEXT_INSN ((INSN)): NULL; \
401 (INSN) && (INSN) != NEXT_INSN (BB_END (BB)); \
402 (INSN) = (CURR), (CURR) = (INSN) ? NEXT_INSN ((INSN)) : NULL)
404 #define FOR_BB_INSNS_REVERSE(BB, INSN) \
405 for ((INSN) = BB_END (BB); \
406 (INSN) && (INSN) != PREV_INSN (BB_HEAD (BB)); \
407 (INSN) = PREV_INSN (INSN))
409 #define FOR_BB_INSNS_REVERSE_SAFE(BB, INSN, CURR) \
410 for ((INSN) = BB_END (BB),(CURR) = (INSN) ? PREV_INSN ((INSN)) : NULL; \
411 (INSN) && (INSN) != PREV_INSN (BB_HEAD (BB)); \
412 (INSN) = (CURR), (CURR) = (INSN) ? PREV_INSN ((INSN)) : NULL)
414 /* Cycles through _all_ basic blocks, even the fake ones (entry and
417 #define FOR_ALL_BB(BB) \
418 for (BB = ENTRY_BLOCK_PTR; BB; BB = BB->next_bb)
420 #define FOR_ALL_BB_FN(BB, FN) \
421 for (BB = ENTRY_BLOCK_PTR_FOR_FUNCTION (FN); BB; BB = BB->next_bb)
424 /* Stuff for recording basic block info. */
426 #define BB_HEAD(B) (B)->il.x.head_
427 #define BB_END(B) (B)->il.x.rtl->end_
428 #define BB_HEADER(B) (B)->il.x.rtl->header_
429 #define BB_FOOTER(B) (B)->il.x.rtl->footer_
431 /* Special block numbers [markers] for entry and exit.
432 Neither of them is supposed to hold actual statements. */
433 #define ENTRY_BLOCK (0)
434 #define EXIT_BLOCK (1)
436 /* The two blocks that are always in the cfg. */
437 #define NUM_FIXED_BLOCKS (2)
439 #define set_block_for_insn(INSN, BB) (BLOCK_FOR_INSN (INSN) = BB)
441 extern void compute_bb_for_insn (void);
442 extern unsigned int free_bb_for_insn (void);
443 extern void update_bb_for_insn (basic_block);
445 extern void insert_insn_on_edge (rtx, edge);
446 basic_block split_edge_and_insert (edge, rtx);
448 extern void commit_one_edge_insertion (edge e);
449 extern void commit_edge_insertions (void);
451 extern void remove_fake_edges (void);
452 extern void remove_fake_exit_edges (void);
453 extern void add_noreturn_fake_exit_edges (void);
454 extern void connect_infinite_loops_to_exit (void);
455 extern edge unchecked_make_edge (basic_block, basic_block, int);
456 extern edge cached_make_edge (sbitmap, basic_block, basic_block, int);
457 extern edge make_edge (basic_block, basic_block, int);
458 extern edge make_single_succ_edge (basic_block, basic_block, int);
459 extern void remove_edge_raw (edge);
460 extern void redirect_edge_succ (edge, basic_block);
461 extern edge redirect_edge_succ_nodup (edge, basic_block);
462 extern void redirect_edge_pred (edge, basic_block);
463 extern basic_block create_basic_block_structure (rtx, rtx, rtx, basic_block);
464 extern void clear_bb_flags (void);
465 extern int post_order_compute (int *, bool, bool);
466 extern int inverted_post_order_compute (int *);
467 extern int pre_and_rev_post_order_compute (int *, int *, bool);
468 extern int dfs_enumerate_from (basic_block, int,
469 bool (*)(const_basic_block, const void *),
470 basic_block *, int, const void *);
471 extern void compute_dominance_frontiers (struct bitmap_head_def *);
472 extern bitmap compute_idf (bitmap, struct bitmap_head_def *);
473 extern void dump_bb_info (basic_block, bool, bool, int, const char *, FILE *);
474 extern void dump_edge_info (FILE *, edge, int);
475 extern void brief_dump_cfg (FILE *);
476 extern void clear_edges (void);
477 extern void scale_bbs_frequencies_int (basic_block *, int, int, int);
478 extern void scale_bbs_frequencies_gcov_type (basic_block *, int, gcov_type,
481 /* Structure to group all of the information to process IF-THEN and
482 IF-THEN-ELSE blocks for the conditional execution support. This
483 needs to be in a public file in case the IFCVT macros call
484 functions passing the ce_if_block data structure. */
486 typedef struct ce_if_block
488 basic_block test_bb; /* First test block. */
489 basic_block then_bb; /* THEN block. */
490 basic_block else_bb; /* ELSE block or NULL. */
491 basic_block join_bb; /* Join THEN/ELSE blocks. */
492 basic_block last_test_bb; /* Last bb to hold && or || tests. */
493 int num_multiple_test_blocks; /* # of && and || basic blocks. */
494 int num_and_and_blocks; /* # of && blocks. */
495 int num_or_or_blocks; /* # of || blocks. */
496 int num_multiple_test_insns; /* # of insns in && and || blocks. */
497 int and_and_p; /* Complex test is &&. */
498 int num_then_insns; /* # of insns in THEN block. */
499 int num_else_insns; /* # of insns in ELSE block. */
500 int pass; /* Pass number. */
502 #ifdef IFCVT_EXTRA_FIELDS
503 IFCVT_EXTRA_FIELDS /* Any machine dependent fields. */
508 /* This structure maintains an edge list vector. */
516 /* The base value for branch probability notes and edge probabilities. */
517 #define REG_BR_PROB_BASE 10000
519 /* This is the value which indicates no edge is present. */
520 #define EDGE_INDEX_NO_EDGE -1
522 /* EDGE_INDEX returns an integer index for an edge, or EDGE_INDEX_NO_EDGE
523 if there is no edge between the 2 basic blocks. */
524 #define EDGE_INDEX(el, pred, succ) (find_edge_index ((el), (pred), (succ)))
526 /* INDEX_EDGE_PRED_BB and INDEX_EDGE_SUCC_BB return a pointer to the basic
527 block which is either the pred or succ end of the indexed edge. */
528 #define INDEX_EDGE_PRED_BB(el, index) ((el)->index_to_edge[(index)]->src)
529 #define INDEX_EDGE_SUCC_BB(el, index) ((el)->index_to_edge[(index)]->dest)
531 /* INDEX_EDGE returns a pointer to the edge. */
532 #define INDEX_EDGE(el, index) ((el)->index_to_edge[(index)])
534 /* Number of edges in the compressed edge list. */
535 #define NUM_EDGES(el) ((el)->num_edges)
537 /* BB is assumed to contain conditional jump. Return the fallthru edge. */
538 #define FALLTHRU_EDGE(bb) (EDGE_SUCC ((bb), 0)->flags & EDGE_FALLTHRU \
539 ? EDGE_SUCC ((bb), 0) : EDGE_SUCC ((bb), 1))
541 /* BB is assumed to contain conditional jump. Return the branch edge. */
542 #define BRANCH_EDGE(bb) (EDGE_SUCC ((bb), 0)->flags & EDGE_FALLTHRU \
543 ? EDGE_SUCC ((bb), 1) : EDGE_SUCC ((bb), 0))
545 /* Return expected execution frequency of the edge E. */
546 #define EDGE_FREQUENCY(e) (((e)->src->frequency \
548 + REG_BR_PROB_BASE / 2) \
551 /* Return nonzero if edge is critical. */
552 #define EDGE_CRITICAL_P(e) (EDGE_COUNT ((e)->src->succs) >= 2 \
553 && EDGE_COUNT ((e)->dest->preds) >= 2)
555 #define EDGE_COUNT(ev) VEC_length (edge, (ev))
556 #define EDGE_I(ev,i) VEC_index (edge, (ev), (i))
557 #define EDGE_PRED(bb,i) VEC_index (edge, (bb)->preds, (i))
558 #define EDGE_SUCC(bb,i) VEC_index (edge, (bb)->succs, (i))
560 /* Returns true if BB has precisely one successor. */
563 single_succ_p (const_basic_block bb)
565 return EDGE_COUNT (bb->succs) == 1;
568 /* Returns true if BB has precisely one predecessor. */
571 single_pred_p (const_basic_block bb)
573 return EDGE_COUNT (bb->preds) == 1;
576 /* Returns the single successor edge of basic block BB. Aborts if
577 BB does not have exactly one successor. */
580 single_succ_edge (const_basic_block bb)
582 gcc_checking_assert (single_succ_p (bb));
583 return EDGE_SUCC (bb, 0);
586 /* Returns the single predecessor edge of basic block BB. Aborts
587 if BB does not have exactly one predecessor. */
590 single_pred_edge (const_basic_block bb)
592 gcc_checking_assert (single_pred_p (bb));
593 return EDGE_PRED (bb, 0);
596 /* Returns the single successor block of basic block BB. Aborts
597 if BB does not have exactly one successor. */
599 static inline basic_block
600 single_succ (const_basic_block bb)
602 return single_succ_edge (bb)->dest;
605 /* Returns the single predecessor block of basic block BB. Aborts
606 if BB does not have exactly one predecessor.*/
608 static inline basic_block
609 single_pred (const_basic_block bb)
611 return single_pred_edge (bb)->src;
614 /* Iterator object for edges. */
618 VEC(edge,gc) **container;
621 static inline VEC(edge,gc) *
622 ei_container (edge_iterator i)
624 gcc_checking_assert (i.container);
628 #define ei_start(iter) ei_start_1 (&(iter))
629 #define ei_last(iter) ei_last_1 (&(iter))
631 /* Return an iterator pointing to the start of an edge vector. */
632 static inline edge_iterator
633 ei_start_1 (VEC(edge,gc) **ev)
643 /* Return an iterator pointing to the last element of an edge
645 static inline edge_iterator
646 ei_last_1 (VEC(edge,gc) **ev)
650 i.index = EDGE_COUNT (*ev) - 1;
656 /* Is the iterator `i' at the end of the sequence? */
658 ei_end_p (edge_iterator i)
660 return (i.index == EDGE_COUNT (ei_container (i)));
663 /* Is the iterator `i' at one position before the end of the
666 ei_one_before_end_p (edge_iterator i)
668 return (i.index + 1 == EDGE_COUNT (ei_container (i)));
671 /* Advance the iterator to the next element. */
673 ei_next (edge_iterator *i)
675 gcc_checking_assert (i->index < EDGE_COUNT (ei_container (*i)));
679 /* Move the iterator to the previous element. */
681 ei_prev (edge_iterator *i)
683 gcc_checking_assert (i->index > 0);
687 /* Return the edge pointed to by the iterator `i'. */
689 ei_edge (edge_iterator i)
691 return EDGE_I (ei_container (i), i.index);
694 /* Return an edge pointed to by the iterator. Do it safely so that
695 NULL is returned when the iterator is pointing at the end of the
698 ei_safe_edge (edge_iterator i)
700 return !ei_end_p (i) ? ei_edge (i) : NULL;
703 /* Return 1 if we should continue to iterate. Return 0 otherwise.
704 *Edge P is set to the next edge if we are to continue to iterate
705 and NULL otherwise. */
708 ei_cond (edge_iterator ei, edge *p)
722 /* This macro serves as a convenient way to iterate each edge in a
723 vector of predecessor or successor edges. It must not be used when
724 an element might be removed during the traversal, otherwise
725 elements will be missed. Instead, use a for-loop like that shown
726 in the following pseudo-code:
728 FOR (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
737 #define FOR_EACH_EDGE(EDGE,ITER,EDGE_VEC) \
738 for ((ITER) = ei_start ((EDGE_VEC)); \
739 ei_cond ((ITER), &(EDGE)); \
742 struct edge_list * create_edge_list (void);
743 void free_edge_list (struct edge_list *);
744 void print_edge_list (FILE *, struct edge_list *);
745 void verify_edge_list (FILE *, struct edge_list *);
746 int find_edge_index (struct edge_list *, basic_block, basic_block);
747 edge find_edge (basic_block, basic_block);
749 #define CLEANUP_EXPENSIVE 1 /* Do relatively expensive optimizations
750 except for edge forwarding */
751 #define CLEANUP_CROSSJUMP 2 /* Do crossjumping. */
752 #define CLEANUP_POST_REGSTACK 4 /* We run after reg-stack and need
753 to care REG_DEAD notes. */
754 #define CLEANUP_THREADING 8 /* Do jump threading. */
755 #define CLEANUP_NO_INSN_DEL 16 /* Do not try to delete trivially dead
757 #define CLEANUP_CFGLAYOUT 32 /* Do cleanup in cfglayout mode. */
758 #define CLEANUP_CFG_CHANGED 64 /* The caller changed the CFG. */
761 extern struct edge_list *pre_edge_lcm (int, sbitmap *, sbitmap *,
762 sbitmap *, sbitmap *, sbitmap **,
764 extern struct edge_list *pre_edge_rev_lcm (int, sbitmap *,
765 sbitmap *, sbitmap *,
766 sbitmap *, sbitmap **,
768 extern void compute_available (sbitmap *, sbitmap *, sbitmap *, sbitmap *);
771 extern bool maybe_hot_bb_p (const_basic_block);
772 extern bool maybe_hot_edge_p (edge);
773 extern bool probably_never_executed_bb_p (const_basic_block);
774 extern bool optimize_bb_for_size_p (const_basic_block);
775 extern bool optimize_bb_for_speed_p (const_basic_block);
776 extern bool optimize_edge_for_size_p (edge);
777 extern bool optimize_edge_for_speed_p (edge);
778 extern bool optimize_loop_for_size_p (struct loop *);
779 extern bool optimize_loop_for_speed_p (struct loop *);
780 extern bool optimize_loop_nest_for_size_p (struct loop *);
781 extern bool optimize_loop_nest_for_speed_p (struct loop *);
782 extern bool gimple_predicted_by_p (const_basic_block, enum br_predictor);
783 extern bool rtl_predicted_by_p (const_basic_block, enum br_predictor);
784 extern void gimple_predict_edge (edge, enum br_predictor, int);
785 extern void rtl_predict_edge (edge, enum br_predictor, int);
786 extern void predict_edge_def (edge, enum br_predictor, enum prediction);
787 extern void guess_outgoing_edge_probabilities (basic_block);
788 extern void remove_predictions_associated_with_edge (edge);
789 extern bool edge_probability_reliable_p (const_edge);
790 extern bool br_prob_note_reliable_p (const_rtx);
791 extern bool predictable_edge_p (edge);
794 extern void init_flow (struct function *);
795 extern void debug_bb (basic_block);
796 extern basic_block debug_bb_n (int);
797 extern void expunge_block (basic_block);
798 extern void link_block (basic_block, basic_block);
799 extern void unlink_block (basic_block);
800 extern void compact_blocks (void);
801 extern basic_block alloc_block (void);
802 extern void alloc_aux_for_blocks (int);
803 extern void clear_aux_for_blocks (void);
804 extern void free_aux_for_blocks (void);
805 extern void alloc_aux_for_edges (int);
806 extern void clear_aux_for_edges (void);
807 extern void free_aux_for_edges (void);
810 extern void find_unreachable_blocks (void);
811 extern bool forwarder_block_p (const_basic_block);
812 extern bool can_fallthru (basic_block, basic_block);
813 extern bool could_fall_through (basic_block, basic_block);
814 extern void flow_nodes_print (const char *, const_sbitmap, FILE *);
815 extern void flow_edge_list_print (const char *, const edge *, int, FILE *);
818 extern rtx block_label (basic_block);
819 extern rtx bb_note (basic_block);
820 extern bool purge_all_dead_edges (void);
821 extern bool purge_dead_edges (basic_block);
822 extern bool fixup_abnormal_edges (void);
823 extern basic_block force_nonfallthru_and_redirect (edge, basic_block, rtx);
826 extern void find_many_sub_basic_blocks (sbitmap);
827 extern void rtl_make_eh_edge (sbitmap, basic_block, rtx);
829 enum replace_direction { dir_none, dir_forward, dir_backward, dir_both };
831 /* In cfgcleanup.c. */
832 extern bool cleanup_cfg (int);
833 extern int flow_find_cross_jump (basic_block, basic_block, rtx *, rtx *,
834 enum replace_direction*);
835 extern int flow_find_head_matching_sequence (basic_block, basic_block,
838 extern bool delete_unreachable_blocks (void);
840 extern bool mark_dfs_back_edges (void);
841 extern void set_edge_can_fallthru_flag (void);
842 extern void update_br_prob_note (basic_block);
843 extern bool inside_basic_block_p (const_rtx);
844 extern bool control_flow_insn_p (const_rtx);
845 extern rtx get_last_bb_insn (basic_block);
852 CDI_POST_DOMINATORS = 2
855 extern enum dom_state dom_info_state (enum cdi_direction);
856 extern void set_dom_info_availability (enum cdi_direction, enum dom_state);
857 extern bool dom_info_available_p (enum cdi_direction);
858 extern void calculate_dominance_info (enum cdi_direction);
859 extern void free_dominance_info (enum cdi_direction);
860 extern basic_block nearest_common_dominator (enum cdi_direction,
861 basic_block, basic_block);
862 extern basic_block nearest_common_dominator_for_set (enum cdi_direction,
864 extern void set_immediate_dominator (enum cdi_direction, basic_block,
866 extern basic_block get_immediate_dominator (enum cdi_direction, basic_block);
867 extern bool dominated_by_p (enum cdi_direction, const_basic_block, const_basic_block);
868 extern VEC (basic_block, heap) *get_dominated_by (enum cdi_direction, basic_block);
869 extern VEC (basic_block, heap) *get_dominated_by_region (enum cdi_direction,
872 extern VEC (basic_block, heap) *get_dominated_to_depth (enum cdi_direction,
874 extern VEC (basic_block, heap) *get_all_dominated_blocks (enum cdi_direction,
876 extern void add_to_dominance_info (enum cdi_direction, basic_block);
877 extern void delete_from_dominance_info (enum cdi_direction, basic_block);
878 basic_block recompute_dominator (enum cdi_direction, basic_block);
879 extern void redirect_immediate_dominators (enum cdi_direction, basic_block,
881 extern void iterate_fix_dominators (enum cdi_direction,
882 VEC (basic_block, heap) *, bool);
883 extern void verify_dominators (enum cdi_direction);
884 extern basic_block first_dom_son (enum cdi_direction, basic_block);
885 extern basic_block next_dom_son (enum cdi_direction, basic_block);
886 unsigned bb_dom_dfs_in (enum cdi_direction, basic_block);
887 unsigned bb_dom_dfs_out (enum cdi_direction, basic_block);
889 extern edge try_redirect_by_replacing_jump (edge, basic_block, bool);
890 extern void break_superblocks (void);
891 extern void relink_block_chain (bool);
892 extern void check_bb_profile (basic_block, FILE *);
893 extern void update_bb_profile_for_threading (basic_block, int, gcov_type, edge);
894 extern void init_rtl_bb_info (basic_block);
896 extern void initialize_original_copy_tables (void);
897 extern void free_original_copy_tables (void);
898 extern void set_bb_original (basic_block, basic_block);
899 extern basic_block get_bb_original (basic_block);
900 extern void set_bb_copy (basic_block, basic_block);
901 extern basic_block get_bb_copy (basic_block);
902 void set_loop_copy (struct loop *, struct loop *);
903 struct loop *get_loop_copy (struct loop *);
905 #include "cfghooks.h"
907 /* Return true when one of the predecessor edges of BB is marked with EDGE_EH. */
909 bb_has_eh_pred (basic_block bb)
914 FOR_EACH_EDGE (e, ei, bb->preds)
916 if (e->flags & EDGE_EH)
922 /* Return true when one of the predecessor edges of BB is marked with EDGE_ABNORMAL. */
924 bb_has_abnormal_pred (basic_block bb)
929 FOR_EACH_EDGE (e, ei, bb->preds)
931 if (e->flags & EDGE_ABNORMAL)
937 /* Return the fallthru edge in EDGES if it exists, NULL otherwise. */
939 find_fallthru_edge (VEC(edge,gc) *edges)
944 FOR_EACH_EDGE (e, ei, edges)
945 if (e->flags & EDGE_FALLTHRU)
951 /* In cfgloopmanip.c. */
952 extern edge mfb_kj_edge;
953 extern bool mfb_keep_just (edge);
955 /* In cfgexpand.c. */
956 extern void rtl_profile_for_bb (basic_block);
957 extern void rtl_profile_for_edge (edge);
958 extern void default_rtl_profile (void);
960 #endif /* GCC_BASIC_BLOCK_H */