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   /* Mapping of labels to their associated blocks.  At present
 307      only used for the gimple CFG.  */
 308   VEC(basic_block,gc) *x_label_to_block_map;
 309
 310   enum profile_status_d x_profile_status;
 311
 312   /* Whether the dominators and the postdominators are available.  */
 313   enum dom_state x_dom_computed[2];
 314
 315   /* Number of basic blocks in the dominance tree.  */
 316   unsigned x_n_bbs_in_dom_tree[2];
 317
 318   /* Maximal number of entities in the single jumptable.  Used to estimate
 319      final flowgraph size.  */
 320   int max_jumptable_ents;
 321
 322   /* UIDs for LABEL_DECLs.  */
 323   int last_label_uid;
 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 (bitmap *);
 447 extern bitmap compute_idf (bitmap, bitmap *);
 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   gcc_assert (single_succ_p (bb));
 558   return EDGE_SUCC (bb, 0);
 559 }
 560
 561 /* Returns the single predecessor edge of basic block BB.  Aborts
 562    if BB does not have exactly one predecessor.  */
 563
 564 static inline edge
 565 single_pred_edge (const_basic_block bb)
 566 {
 567   gcc_assert (single_pred_p (bb));
 568   return EDGE_PRED (bb, 0);
 569 }
 570
 571 /* Returns the single successor block of basic block BB.  Aborts
 572    if BB does not have exactly one successor.  */
 573
 574 static inline basic_block
 575 single_succ (const_basic_block bb)
 576 {
 577   return single_succ_edge (bb)->dest;
 578 }
 579
 580 /* Returns the single predecessor block of basic block BB.  Aborts
 581    if BB does not have exactly one predecessor.*/
 582
 583 static inline basic_block
 584 single_pred (const_basic_block bb)
 585 {
 586   return single_pred_edge (bb)->src;
 587 }
 588
 589 /* Iterator object for edges.  */
 590
 591 typedef struct {
 592   unsigned index;
 593   VEC(edge,gc) **container;
 594 } edge_iterator;
 595
 596 static inline VEC(edge,gc) *
 597 ei_container (edge_iterator i)
 598 {
 599   gcc_assert (i.container);
 600   return *i.container;
 601 }
 602
 603 #define ei_start(iter) ei_start_1 (&(iter))
 604 #define ei_last(iter) ei_last_1 (&(iter))
 605
 606 /* Return an iterator pointing to the start of an edge vector.  */
 607 static inline edge_iterator
 608 ei_start_1 (VEC(edge,gc) **ev)
 609 {
 610   edge_iterator i;
 611
 612   i.index = 0;
 613   i.container = ev;
 614
 615   return i;
 616 }
 617
 618 /* Return an iterator pointing to the last element of an edge
 619    vector.  */
 620 static inline edge_iterator
 621 ei_last_1 (VEC(edge,gc) **ev)
 622 {
 623   edge_iterator i;
 624
 625   i.index = EDGE_COUNT (*ev) - 1;
 626   i.container = ev;
 627
 628   return i;
 629 }
 630
 631 /* Is the iterator `i' at the end of the sequence?  */
 632 static inline bool
 633 ei_end_p (edge_iterator i)
 634 {
 635   return (i.index == EDGE_COUNT (ei_container (i)));
 636 }
 637
 638 /* Is the iterator `i' at one position before the end of the
 639    sequence?  */
 640 static inline bool
 641 ei_one_before_end_p (edge_iterator i)
 642 {
 643   return (i.index + 1 == EDGE_COUNT (ei_container (i)));
 644 }
 645
 646 /* Advance the iterator to the next element.  */
 647 static inline void
 648 ei_next (edge_iterator *i)
 649 {
 650   gcc_assert (i->index < EDGE_COUNT (ei_container (*i)));
 651   i->index++;
 652 }
 653
 654 /* Move the iterator to the previous element.  */
 655 static inline void
 656 ei_prev (edge_iterator *i)
 657 {
 658   gcc_assert (i->index > 0);
 659   i->index--;
 660 }
 661
 662 /* Return the edge pointed to by the iterator `i'.  */
 663 static inline edge
 664 ei_edge (edge_iterator i)
 665 {
 666   return EDGE_I (ei_container (i), i.index);
 667 }
 668
 669 /* Return an edge pointed to by the iterator.  Do it safely so that
 670    NULL is returned when the iterator is pointing at the end of the
 671    sequence.  */
 672 static inline edge
 673 ei_safe_edge (edge_iterator i)
 674 {
 675   return !ei_end_p (i) ? ei_edge (i) : NULL;
 676 }
 677
 678 /* Return 1 if we should continue to iterate.  Return 0 otherwise.
 679    *Edge P is set to the next edge if we are to continue to iterate
 680    and NULL otherwise.  */
 681
 682 static inline bool
 683 ei_cond (edge_iterator ei, edge *p)
 684 {
 685   if (!ei_end_p (ei))
 686     {
 687       *p = ei_edge (ei);
 688       return 1;
 689     }
 690   else
 691     {
 692       *p = NULL;
 693       return 0;
 694     }
 695 }
 696
 697 /* This macro serves as a convenient way to iterate each edge in a
 698    vector of predecessor or successor edges.  It must not be used when
 699    an element might be removed during the traversal, otherwise
 700    elements will be missed.  Instead, use a for-loop like that shown
 701    in the following pseudo-code:
 702
 703    FOR (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
 704      {
 705         IF (e != taken_edge)
 706           remove_edge (e);
 707         ELSE
 708           ei_next (&ei);
 709      }
 710 */
 711
 712 #define FOR_EACH_EDGE(EDGE,ITER,EDGE_VEC)       \
 713   for ((ITER) = ei_start ((EDGE_VEC));          \
 714        ei_cond ((ITER), &(EDGE));               \
 715        ei_next (&(ITER)))
 716
 717 struct edge_list * create_edge_list (void);
 718 void free_edge_list (struct edge_list *);
 719 void print_edge_list (FILE *, struct edge_list *);
 720 void verify_edge_list (FILE *, struct edge_list *);
 721 int find_edge_index (struct edge_list *, basic_block, basic_block);
 722 edge find_edge (basic_block, basic_block);
 723
 724 #define CLEANUP_EXPENSIVE       1       /* Do relatively expensive optimizations
 725                                            except for edge forwarding */
 726 #define CLEANUP_CROSSJUMP       2       /* Do crossjumping.  */
 727 #define CLEANUP_POST_REGSTACK   4       /* We run after reg-stack and need
 728                                            to care REG_DEAD notes.  */
 729 #define CLEANUP_THREADING       8       /* Do jump threading.  */
 730 #define CLEANUP_NO_INSN_DEL     16      /* Do not try to delete trivially dead
 731                                            insns.  */
 732 #define CLEANUP_CFGLAYOUT       32      /* Do cleanup in cfglayout mode.  */
 733
 734 /* In lcm.c */
 735 extern struct edge_list *pre_edge_lcm (int, sbitmap *, sbitmap *,
 736                                        sbitmap *, sbitmap *, sbitmap **,
 737                                        sbitmap **);
 738 extern struct edge_list *pre_edge_rev_lcm (int, sbitmap *,
 739                                            sbitmap *, sbitmap *,
 740                                            sbitmap *, sbitmap **,
 741                                            sbitmap **);
 742 extern void compute_available (sbitmap *, sbitmap *, sbitmap *, sbitmap *);
 743
 744 /* In predict.c */
 745 extern bool maybe_hot_bb_p (const_basic_block);
 746 extern bool maybe_hot_edge_p (edge);
 747 extern bool probably_never_executed_bb_p (const_basic_block);
 748 extern bool optimize_bb_for_size_p (const_basic_block);
 749 extern bool optimize_bb_for_speed_p (const_basic_block);
 750 extern bool optimize_edge_for_size_p (edge);
 751 extern bool optimize_edge_for_speed_p (edge);
 752 extern bool optimize_function_for_size_p (struct function *);
 753 extern bool optimize_function_for_speed_p (struct function *);
 754 extern bool optimize_loop_for_size_p (struct loop *);
 755 extern bool optimize_loop_for_speed_p (struct loop *);
 756 extern bool optimize_loop_nest_for_size_p (struct loop *);
 757 extern bool optimize_loop_nest_for_speed_p (struct loop *);
 758 extern bool gimple_predicted_by_p (const_basic_block, enum br_predictor);
 759 extern bool rtl_predicted_by_p (const_basic_block, enum br_predictor);
 760 extern void gimple_predict_edge (edge, enum br_predictor, int);
 761 extern void rtl_predict_edge (edge, enum br_predictor, int);
 762 extern void predict_edge_def (edge, enum br_predictor, enum prediction);
 763 extern void guess_outgoing_edge_probabilities (basic_block);
 764 extern void remove_predictions_associated_with_edge (edge);
 765 extern bool edge_probability_reliable_p (const_edge);
 766 extern bool br_prob_note_reliable_p (const_rtx);
 767 extern bool predictable_edge_p (edge);
 768
 769 /* In cfg.c  */
 770 extern void init_flow (struct function *);
 771 extern void debug_bb (basic_block);
 772 extern basic_block debug_bb_n (int);
 773 extern void expunge_block (basic_block);
 774 extern void link_block (basic_block, basic_block);
 775 extern void unlink_block (basic_block);
 776 extern void compact_blocks (void);
 777 extern basic_block alloc_block (void);
 778 extern void alloc_aux_for_block (basic_block, int);
 779 extern void alloc_aux_for_blocks (int);
 780 extern void clear_aux_for_blocks (void);
 781 extern void free_aux_for_blocks (void);
 782 extern void alloc_aux_for_edge (edge, int);
 783 extern void alloc_aux_for_edges (int);
 784 extern void clear_aux_for_edges (void);
 785 extern void free_aux_for_edges (void);
 786
 787 /* In cfganal.c  */
 788 extern void find_unreachable_blocks (void);
 789 extern bool forwarder_block_p (const_basic_block);
 790 extern bool can_fallthru (basic_block, basic_block);
 791 extern bool could_fall_through (basic_block, basic_block);
 792 extern void flow_nodes_print (const char *, const_sbitmap, FILE *);
 793 extern void flow_edge_list_print (const char *, const edge *, int, FILE *);
 794
 795 /* In cfgrtl.c  */
 796 extern basic_block force_nonfallthru (edge);
 797 extern rtx block_label (basic_block);
 798 extern bool purge_all_dead_edges (void);
 799 extern bool purge_dead_edges (basic_block);
 800
 801 /* In cfgbuild.c.  */
 802 extern void find_many_sub_basic_blocks (sbitmap);
 803 extern void rtl_make_eh_edge (sbitmap, basic_block, rtx);
 804
 805 /* In cfgcleanup.c.  */
 806 extern bool cleanup_cfg (int);
 807 extern int flow_find_cross_jump (basic_block, basic_block, rtx *, rtx *);
 808 extern int flow_find_head_matching_sequence (basic_block, basic_block,
 809                                              rtx *, rtx *, int);
 810
 811 extern bool delete_unreachable_blocks (void);
 812
 813 extern bool mark_dfs_back_edges (void);
 814 extern void set_edge_can_fallthru_flag (void);
 815 extern void update_br_prob_note (basic_block);
 816 extern void fixup_abnormal_edges (void);
 817 extern bool inside_basic_block_p (const_rtx);
 818 extern bool control_flow_insn_p (const_rtx);
 819 extern rtx get_last_bb_insn (basic_block);
 820
 821 /* In bb-reorder.c */
 822 extern void reorder_basic_blocks (void);
 823
 824 /* In dominance.c */
 825
 826 enum cdi_direction
 827 {
 828   CDI_DOMINATORS = 1,
 829   CDI_POST_DOMINATORS = 2
 830 };
 831
 832 extern enum dom_state dom_info_state (enum cdi_direction);
 833 extern void set_dom_info_availability (enum cdi_direction, enum dom_state);
 834 extern bool dom_info_available_p (enum cdi_direction);
 835 extern void calculate_dominance_info (enum cdi_direction);
 836 extern void free_dominance_info (enum cdi_direction);
 837 extern basic_block nearest_common_dominator (enum cdi_direction,
 838                                              basic_block, basic_block);
 839 extern basic_block nearest_common_dominator_for_set (enum cdi_direction,
 840                                                      bitmap);
 841 extern void set_immediate_dominator (enum cdi_direction, basic_block,
 842                                      basic_block);
 843 extern basic_block get_immediate_dominator (enum cdi_direction, basic_block);
 844 extern bool dominated_by_p (enum cdi_direction, const_basic_block, const_basic_block);
 845 extern VEC (basic_block, heap) *get_dominated_by (enum cdi_direction, basic_block);
 846 extern VEC (basic_block, heap) *get_dominated_by_region (enum cdi_direction,
 847                                                          basic_block *,
 848                                                          unsigned);
 849 extern VEC (basic_block, heap) *get_all_dominated_blocks (enum cdi_direction,
 850                                                           basic_block);
 851 extern void add_to_dominance_info (enum cdi_direction, basic_block);
 852 extern void delete_from_dominance_info (enum cdi_direction, basic_block);
 853 basic_block recompute_dominator (enum cdi_direction, basic_block);
 854 extern void redirect_immediate_dominators (enum cdi_direction, basic_block,
 855                                            basic_block);
 856 extern void iterate_fix_dominators (enum cdi_direction,
 857                                     VEC (basic_block, heap) *, bool);
 858 extern void verify_dominators (enum cdi_direction);
 859 extern basic_block first_dom_son (enum cdi_direction, basic_block);
 860 extern basic_block next_dom_son (enum cdi_direction, basic_block);
 861 unsigned bb_dom_dfs_in (enum cdi_direction, basic_block);
 862 unsigned bb_dom_dfs_out (enum cdi_direction, basic_block);
 863
 864 extern edge try_redirect_by_replacing_jump (edge, basic_block, bool);
 865 extern void break_superblocks (void);
 866 extern void relink_block_chain (bool);
 867 extern void check_bb_profile (basic_block, FILE *);
 868 extern void update_bb_profile_for_threading (basic_block, int, gcov_type, edge);
 869 extern void init_rtl_bb_info (basic_block);
 870
 871 extern void initialize_original_copy_tables (void);
 872 extern void free_original_copy_tables (void);
 873 extern void set_bb_original (basic_block, basic_block);
 874 extern basic_block get_bb_original (basic_block);
 875 extern void set_bb_copy (basic_block, basic_block);
 876 extern basic_block get_bb_copy (basic_block);
 877 void set_loop_copy (struct loop *, struct loop *);
 878 struct loop *get_loop_copy (struct loop *);
 879
 880
 881 extern rtx insert_insn_end_bb_new (rtx, basic_block);
 882
 883 #include "cfghooks.h"
 884
 885 /* Return true when one of the predecessor edges of BB is marked with EDGE_EH.  */
 886 static inline bool
 887 bb_has_eh_pred (basic_block bb)
 888 {
 889   edge e;
 890   edge_iterator ei;
 891
 892   FOR_EACH_EDGE (e, ei, bb->preds)
 893     {
 894       if (e->flags & EDGE_EH)
 895         return true;
 896     }
 897   return false;
 898 }
 899
 900 /* Return true when one of the predecessor edges of BB is marked with EDGE_ABNORMAL.  */
 901 static inline bool
 902 bb_has_abnormal_pred (basic_block bb)
 903 {
 904   edge e;
 905   edge_iterator ei;
 906
 907   FOR_EACH_EDGE (e, ei, bb->preds)
 908     {
 909       if (e->flags & EDGE_ABNORMAL)
 910         return true;
 911     }
 912   return false;
 913 }
 914
 915 /* In cfgloopmanip.c.  */
 916 extern edge mfb_kj_edge;
 917 extern bool mfb_keep_just (edge);
 918
 919 /* In cfgexpand.c.  */
 920 extern void rtl_profile_for_bb (basic_block);
 921 extern void rtl_profile_for_edge (edge);
 922 extern void default_rtl_profile (void);
 923
 924 #endif /* GCC_BASIC_BLOCK_H */