gcc/basic-block.h

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