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