gcc/basic-block.h

   1 /* Define control flow data structures for the CFG.
   2    Copyright (C) 1987-2014 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 3, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #ifndef GCC_BASIC_BLOCK_H
  21 #define GCC_BASIC_BLOCK_H
  22
  23 #include "predict.h"
  24 #include "vec.h"
  25 #include "hashtab.h"
  26 #include "hash-set.h"
  27 #include "machmode.h"
  28 #include "tm.h"
  29 #include "hard-reg-set.h"
  30 #include "input.h"
  31 #include "function.h"
  32 #include "cfgrtl.h"
  33 #include "cfg.h"
  34 #include "cfganal.h"
  35 #include "lcm.h"
  36
  37 /* Use gcov_type to hold basic block counters.  Should be at least
  38    64bit.  Although a counter cannot be negative, we use a signed
  39    type, because erroneous negative counts can be generated when the
  40    flow graph is manipulated by various optimizations.  A signed type
  41    makes those easy to detect.  */
  42
  43 /* Control flow edge information.  */
  44 struct GTY((user)) edge_def {
  45   /* The two blocks at the ends of the edge.  */
  46   basic_block src;
  47   basic_block dest;
  48
  49   /* Instructions queued on the edge.  */
  50   union edge_def_insns {
  51     gimple_seq g;
  52     rtx_insn *r;
  53   } insns;
  54
  55   /* Auxiliary info specific to a pass.  */
  56   PTR aux;
  57
  58   /* Location of any goto implicit in the edge.  */
  59   location_t goto_locus;
  60
  61   /* The index number corresponding to this edge in the edge vector
  62      dest->preds.  */
  63   unsigned int dest_idx;
  64
  65   int flags;                    /* see cfg-flags.def */
  66   int probability;              /* biased by REG_BR_PROB_BASE */
  67   gcov_type count;              /* Expected number of executions calculated
  68                                    in profile.c  */
  69 };
  70
  71 /* Masks for edge.flags.  */
  72 #define DEF_EDGE_FLAG(NAME,IDX) EDGE_##NAME = 1 << IDX ,
  73 enum cfg_edge_flags {
  74 #include "cfg-flags.def"
  75   LAST_CFG_EDGE_FLAG            /* this is only used for EDGE_ALL_FLAGS */
  76 };
  77 #undef DEF_EDGE_FLAG
  78
  79 /* Bit mask for all edge flags.  */
  80 #define EDGE_ALL_FLAGS          ((LAST_CFG_EDGE_FLAG - 1) * 2 - 1)
  81
  82 /* The following four flags all indicate something special about an edge.
  83    Test the edge flags on EDGE_COMPLEX to detect all forms of "strange"
  84    control flow transfers.  */
  85 #define EDGE_COMPLEX \
  86   (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_EH | EDGE_PRESERVE)
  87
  88 /* Structure to gather statistic about profile consistency, per pass.
  89    An array of this structure, indexed by pass static number, is allocated
  90    in passes.c.  The structure is defined here so that different CFG modes
  91    can do their book-keeping via CFG hooks.
  92
  93    For every field[2], field[0] is the count before the pass runs, and
  94    field[1] is the post-pass count.  This allows us to monitor the effect
  95    of each individual pass on the profile consistency.
  96
  97    This structure is not supposed to be used by anything other than passes.c
  98    and one CFG hook per CFG mode.  */
  99 struct profile_record
 100 {
 101   /* The number of basic blocks where sum(freq) of the block's predecessors
 102      doesn't match reasonably well with the incoming frequency.  */
 103   int num_mismatched_freq_in[2];
 104   /* Likewise for a basic block's successors.  */
 105   int num_mismatched_freq_out[2];
 106   /* The number of basic blocks where sum(count) of the block's predecessors
 107      doesn't match reasonably well with the incoming frequency.  */
 108   int num_mismatched_count_in[2];
 109   /* Likewise for a basic block's successors.  */
 110   int num_mismatched_count_out[2];
 111   /* A weighted cost of the run-time of the function body.  */
 112   gcov_type time[2];
 113   /* A weighted cost of the size of the function body.  */
 114   int size[2];
 115   /* True iff this pass actually was run.  */
 116   bool run;
 117 };
 118
 119
 120 struct GTY(()) rtl_bb_info {
 121   /* The first insn of the block is embedded into bb->il.x.  */
 122   /* The last insn of the block.  */
 123   rtx_insn *end_;
 124
 125   /* In CFGlayout mode points to insn notes/jumptables to be placed just before
 126      and after the block.   */
 127   rtx_insn *header_;
 128   rtx_insn *footer_;
 129 };
 130
 131 struct GTY(()) gimple_bb_info {
 132   /* Sequence of statements in this block.  */
 133   gimple_seq seq;
 134
 135   /* PHI nodes for this block.  */
 136   gimple_seq phi_nodes;
 137 };
 138
 139 /* A basic block is a sequence of instructions with only one entry and
 140    only one exit.  If any one of the instructions are executed, they
 141    will all be executed, and in sequence from first to last.
 142
 143    There may be COND_EXEC instructions in the basic block.  The
 144    COND_EXEC *instructions* will be executed -- but if the condition
 145    is false the conditionally executed *expressions* will of course
 146    not be executed.  We don't consider the conditionally executed
 147    expression (which might have side-effects) to be in a separate
 148    basic block because the program counter will always be at the same
 149    location after the COND_EXEC instruction, regardless of whether the
 150    condition is true or not.
 151
 152    Basic blocks need not start with a label nor end with a jump insn.
 153    For example, a previous basic block may just "conditionally fall"
 154    into the succeeding basic block, and the last basic block need not
 155    end with a jump insn.  Block 0 is a descendant of the entry block.
 156
 157    A basic block beginning with two labels cannot have notes between
 158    the labels.
 159
 160    Data for jump tables are stored in jump_insns that occur in no
 161    basic block even though these insns can follow or precede insns in
 162    basic blocks.  */
 163
 164 /* Basic block information indexed by block number.  */
 165 struct GTY((chain_next ("%h.next_bb"), chain_prev ("%h.prev_bb"))) basic_block_def {
 166   /* The edges into and out of the block.  */
 167   vec<edge, va_gc> *preds;
 168   vec<edge, va_gc> *succs;
 169
 170   /* Auxiliary info specific to a pass.  */
 171   PTR GTY ((skip (""))) aux;
 172
 173   /* Innermost loop containing the block.  */
 174   struct loop *loop_father;
 175
 176   /* The dominance and postdominance information node.  */
 177   struct et_node * GTY ((skip (""))) dom[2];
 178
 179   /* Previous and next blocks in the chain.  */
 180   basic_block prev_bb;
 181   basic_block next_bb;
 182
 183   union basic_block_il_dependent {
 184       struct gimple_bb_info GTY ((tag ("0"))) gimple;
 185       struct {
 186         rtx_insn *head_;
 187         struct rtl_bb_info * rtl;
 188       } GTY ((tag ("1"))) x;
 189     } GTY ((desc ("((%1.flags & BB_RTL) != 0)"))) il;
 190
 191   /* Various flags.  See cfg-flags.def.  */
 192   int flags;
 193
 194   /* The index of this block.  */
 195   int index;
 196
 197   /* Expected number of executions: calculated in profile.c.  */
 198   gcov_type count;
 199
 200   /* Expected frequency.  Normalized to be in range 0 to BB_FREQ_MAX.  */
 201   int frequency;
 202
 203   /* The discriminator for this block.  The discriminator distinguishes
 204      among several basic blocks that share a common locus, allowing for
 205      more accurate sample-based profiling.  */
 206   int discriminator;
 207 };
 208
 209 /* This ensures that struct gimple_bb_info is smaller than
 210    struct rtl_bb_info, so that inlining the former into basic_block_def
 211    is the better choice.  */
 212 typedef int __assert_gimple_bb_smaller_rtl_bb
 213               [(int) sizeof (struct rtl_bb_info)
 214                - (int) sizeof (struct gimple_bb_info)];
 215
 216
 217 #define BB_FREQ_MAX 10000
 218
 219 /* Masks for basic_block.flags.  */
 220 #define DEF_BASIC_BLOCK_FLAG(NAME,IDX) BB_##NAME = 1 << IDX ,
 221 enum cfg_bb_flags
 222 {
 223 #include "cfg-flags.def"
 224   LAST_CFG_BB_FLAG              /* this is only used for BB_ALL_FLAGS */
 225 };
 226 #undef DEF_BASIC_BLOCK_FLAG
 227
 228 /* Bit mask for all basic block flags.  */
 229 #define BB_ALL_FLAGS            ((LAST_CFG_BB_FLAG - 1) * 2 - 1)
 230
 231 /* Bit mask for all basic block flags that must be preserved.  These are
 232    the bit masks that are *not* cleared by clear_bb_flags.  */
 233 #define BB_FLAGS_TO_PRESERVE                                    \
 234   (BB_DISABLE_SCHEDULE | BB_RTL | BB_NON_LOCAL_GOTO_TARGET      \
 235    | BB_HOT_PARTITION | BB_COLD_PARTITION)
 236
 237 /* Dummy bitmask for convenience in the hot/cold partitioning code.  */
 238 #define BB_UNPARTITIONED        0
 239
 240 /* Partitions, to be used when partitioning hot and cold basic blocks into
 241    separate sections.  */
 242 #define BB_PARTITION(bb) ((bb)->flags & (BB_HOT_PARTITION|BB_COLD_PARTITION))
 243 #define BB_SET_PARTITION(bb, part) do {                                 \
 244   basic_block bb_ = (bb);                                               \
 245   bb_->flags = ((bb_->flags & ~(BB_HOT_PARTITION|BB_COLD_PARTITION))    \
 246                 | (part));                                              \
 247 } while (0)
 248
 249 #define BB_COPY_PARTITION(dstbb, srcbb) \
 250   BB_SET_PARTITION (dstbb, BB_PARTITION (srcbb))
 251
 252 /* State of dominance information.  */
 253
 254 enum dom_state
 255 {
 256   DOM_NONE,             /* Not computed at all.  */
 257   DOM_NO_FAST_QUERY,    /* The data is OK, but the fast query data are not usable.  */
 258   DOM_OK                /* Everything is ok.  */
 259 };
 260
 261 /* What sort of profiling information we have.  */
 262 enum profile_status_d
 263 {
 264   PROFILE_ABSENT,
 265   PROFILE_GUESSED,
 266   PROFILE_READ,
 267   PROFILE_LAST  /* Last value, used by profile streaming.  */
 268 };
 269
 270 /* A structure to group all the per-function control flow graph data.
 271    The x_* prefixing is necessary because otherwise references to the
 272    fields of this struct are interpreted as the defines for backward
 273    source compatibility following the definition of this struct.  */
 274 struct GTY(()) control_flow_graph {
 275   /* Block pointers for the exit and entry of a function.
 276      These are always the head and tail of the basic block list.  */
 277   basic_block x_entry_block_ptr;
 278   basic_block x_exit_block_ptr;
 279
 280   /* Index by basic block number, get basic block struct info.  */
 281   vec<basic_block, va_gc> *x_basic_block_info;
 282
 283   /* Number of basic blocks in this flow graph.  */
 284   int x_n_basic_blocks;
 285
 286   /* Number of edges in this flow graph.  */
 287   int x_n_edges;
 288
 289   /* The first free basic block number.  */
 290   int x_last_basic_block;
 291
 292   /* UIDs for LABEL_DECLs.  */
 293   int last_label_uid;
 294
 295   /* Mapping of labels to their associated blocks.  At present
 296      only used for the gimple CFG.  */
 297   vec<basic_block, va_gc> *x_label_to_block_map;
 298
 299   enum profile_status_d x_profile_status;
 300
 301   /* Whether the dominators and the postdominators are available.  */
 302   enum dom_state x_dom_computed[2];
 303
 304   /* Number of basic blocks in the dominance tree.  */
 305   unsigned x_n_bbs_in_dom_tree[2];
 306
 307   /* Maximal number of entities in the single jumptable.  Used to estimate
 308      final flowgraph size.  */
 309   int max_jumptable_ents;
 310 };
 311
 312 /* Defines for accessing the fields of the CFG structure for function FN.  */
 313 #define ENTRY_BLOCK_PTR_FOR_FN(FN)           ((FN)->cfg->x_entry_block_ptr)
 314 #define EXIT_BLOCK_PTR_FOR_FN(FN)            ((FN)->cfg->x_exit_block_ptr)
 315 #define basic_block_info_for_fn(FN)          ((FN)->cfg->x_basic_block_info)
 316 #define n_basic_blocks_for_fn(FN)            ((FN)->cfg->x_n_basic_blocks)
 317 #define n_edges_for_fn(FN)                   ((FN)->cfg->x_n_edges)
 318 #define last_basic_block_for_fn(FN)          ((FN)->cfg->x_last_basic_block)
 319 #define label_to_block_map_for_fn(FN)        ((FN)->cfg->x_label_to_block_map)
 320 #define profile_status_for_fn(FN)            ((FN)->cfg->x_profile_status)
 321
 322 #define BASIC_BLOCK_FOR_FN(FN,N) \
 323   ((*basic_block_info_for_fn (FN))[(N)])
 324 #define SET_BASIC_BLOCK_FOR_FN(FN,N,BB) \
 325   ((*basic_block_info_for_fn (FN))[(N)] = (BB))
 326
 327 /* For iterating over basic blocks.  */
 328 #define FOR_BB_BETWEEN(BB, FROM, TO, DIR) \
 329   for (BB = FROM; BB != TO; BB = BB->DIR)
 330
 331 #define FOR_EACH_BB_FN(BB, FN) \
 332   FOR_BB_BETWEEN (BB, (FN)->cfg->x_entry_block_ptr->next_bb, (FN)->cfg->x_exit_block_ptr, next_bb)
 333
 334 #define FOR_EACH_BB_REVERSE_FN(BB, FN) \
 335   FOR_BB_BETWEEN (BB, (FN)->cfg->x_exit_block_ptr->prev_bb, (FN)->cfg->x_entry_block_ptr, prev_bb)
 336
 337 /* For iterating over insns in basic block.  */
 338 #define FOR_BB_INSNS(BB, INSN)                  \
 339   for ((INSN) = BB_HEAD (BB);                   \
 340        (INSN) && (INSN) != NEXT_INSN (BB_END (BB));     \
 341        (INSN) = NEXT_INSN (INSN))
 342
 343 /* For iterating over insns in basic block when we might remove the
 344    current insn.  */
 345 #define FOR_BB_INSNS_SAFE(BB, INSN, CURR)                       \
 346   for ((INSN) = BB_HEAD (BB), (CURR) = (INSN) ? NEXT_INSN ((INSN)): NULL;       \
 347        (INSN) && (INSN) != NEXT_INSN (BB_END (BB));     \
 348        (INSN) = (CURR), (CURR) = (INSN) ? NEXT_INSN ((INSN)) : NULL)
 349
 350 #define FOR_BB_INSNS_REVERSE(BB, INSN)          \
 351   for ((INSN) = BB_END (BB);                    \
 352        (INSN) && (INSN) != PREV_INSN (BB_HEAD (BB));    \
 353        (INSN) = PREV_INSN (INSN))
 354
 355 #define FOR_BB_INSNS_REVERSE_SAFE(BB, INSN, CURR)       \
 356   for ((INSN) = BB_END (BB),(CURR) = (INSN) ? PREV_INSN ((INSN)) : NULL;        \
 357        (INSN) && (INSN) != PREV_INSN (BB_HEAD (BB));    \
 358        (INSN) = (CURR), (CURR) = (INSN) ? PREV_INSN ((INSN)) : NULL)
 359
 360 /* Cycles through _all_ basic blocks, even the fake ones (entry and
 361    exit block).  */
 362
 363 #define FOR_ALL_BB_FN(BB, FN) \
 364   for (BB = ENTRY_BLOCK_PTR_FOR_FN (FN); BB; BB = BB->next_bb)
 365
 366 \f
 367 /* Stuff for recording basic block info.  */
 368
 369 /* For now, these will be functions (so that they can include checked casts
 370    to rtx_insn.   Once the underlying fields are converted from rtx
 371    to rtx_insn, these can be converted back to macros.  */
 372
 373 #define BB_HEAD(B)      (B)->il.x.head_
 374 #define BB_END(B)       (B)->il.x.rtl->end_
 375 #define BB_HEADER(B)    (B)->il.x.rtl->header_
 376 #define BB_FOOTER(B)    (B)->il.x.rtl->footer_
 377
 378 /* Special block numbers [markers] for entry and exit.
 379    Neither of them is supposed to hold actual statements.  */
 380 #define ENTRY_BLOCK (0)
 381 #define EXIT_BLOCK (1)
 382
 383 /* The two blocks that are always in the cfg.  */
 384 #define NUM_FIXED_BLOCKS (2)
 385
 386
 387 extern edge redirect_edge_succ_nodup (edge, basic_block);
 388
 389 /* Structure to group all of the information to process IF-THEN and
 390    IF-THEN-ELSE blocks for the conditional execution support.  This
 391    needs to be in a public file in case the IFCVT macros call
 392    functions passing the ce_if_block data structure.  */
 393
 394 struct ce_if_block
 395 {
 396   basic_block test_bb;                  /* First test block.  */
 397   basic_block then_bb;                  /* THEN block.  */
 398   basic_block else_bb;                  /* ELSE block or NULL.  */
 399   basic_block join_bb;                  /* Join THEN/ELSE blocks.  */
 400   basic_block last_test_bb;             /* Last bb to hold && or || tests.  */
 401   int num_multiple_test_blocks;         /* # of && and || basic blocks.  */
 402   int num_and_and_blocks;               /* # of && blocks.  */
 403   int num_or_or_blocks;                 /* # of || blocks.  */
 404   int num_multiple_test_insns;          /* # of insns in && and || blocks.  */
 405   int and_and_p;                        /* Complex test is &&.  */
 406   int num_then_insns;                   /* # of insns in THEN block.  */
 407   int num_else_insns;                   /* # of insns in ELSE block.  */
 408   int pass;                             /* Pass number.  */
 409 };
 410
 411 /* The base value for branch probability notes and edge probabilities.  */
 412 #define REG_BR_PROB_BASE  10000
 413
 414 /* This is the value which indicates no edge is present.  */
 415 #define EDGE_INDEX_NO_EDGE      -1
 416
 417 /* EDGE_INDEX returns an integer index for an edge, or EDGE_INDEX_NO_EDGE
 418    if there is no edge between the 2 basic blocks.  */
 419 #define EDGE_INDEX(el, pred, succ) (find_edge_index ((el), (pred), (succ)))
 420
 421 /* INDEX_EDGE_PRED_BB and INDEX_EDGE_SUCC_BB return a pointer to the basic
 422    block which is either the pred or succ end of the indexed edge.  */
 423 #define INDEX_EDGE_PRED_BB(el, index)   ((el)->index_to_edge[(index)]->src)
 424 #define INDEX_EDGE_SUCC_BB(el, index)   ((el)->index_to_edge[(index)]->dest)
 425
 426 /* INDEX_EDGE returns a pointer to the edge.  */
 427 #define INDEX_EDGE(el, index)           ((el)->index_to_edge[(index)])
 428
 429 /* Number of edges in the compressed edge list.  */
 430 #define NUM_EDGES(el)                   ((el)->num_edges)
 431
 432 /* BB is assumed to contain conditional jump.  Return the fallthru edge.  */
 433 #define FALLTHRU_EDGE(bb)               (EDGE_SUCC ((bb), 0)->flags & EDGE_FALLTHRU \
 434                                          ? EDGE_SUCC ((bb), 0) : EDGE_SUCC ((bb), 1))
 435
 436 /* BB is assumed to contain conditional jump.  Return the branch edge.  */
 437 #define BRANCH_EDGE(bb)                 (EDGE_SUCC ((bb), 0)->flags & EDGE_FALLTHRU \
 438                                          ? EDGE_SUCC ((bb), 1) : EDGE_SUCC ((bb), 0))
 439
 440 #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
 441 /* Return expected execution frequency of the edge E.  */
 442 #define EDGE_FREQUENCY(e)               RDIV ((e)->src->frequency * (e)->probability, \
 443                                               REG_BR_PROB_BASE)
 444
 445 /* Compute a scale factor (or probability) suitable for scaling of
 446    gcov_type values via apply_probability() and apply_scale().  */
 447 #define GCOV_COMPUTE_SCALE(num,den) \
 448   ((den) ? RDIV ((num) * REG_BR_PROB_BASE, (den)) : REG_BR_PROB_BASE)
 449
 450 /* Return nonzero if edge is critical.  */
 451 #define EDGE_CRITICAL_P(e)              (EDGE_COUNT ((e)->src->succs) >= 2 \
 452                                          && EDGE_COUNT ((e)->dest->preds) >= 2)
 453
 454 #define EDGE_COUNT(ev)                  vec_safe_length (ev)
 455 #define EDGE_I(ev,i)                    (*ev)[(i)]
 456 #define EDGE_PRED(bb,i)                 (*(bb)->preds)[(i)]
 457 #define EDGE_SUCC(bb,i)                 (*(bb)->succs)[(i)]
 458
 459 /* Returns true if BB has precisely one successor.  */
 460
 461 static inline bool
 462 single_succ_p (const_basic_block bb)
 463 {
 464   return EDGE_COUNT (bb->succs) == 1;
 465 }
 466
 467 /* Returns true if BB has precisely one predecessor.  */
 468
 469 static inline bool
 470 single_pred_p (const_basic_block bb)
 471 {
 472   return EDGE_COUNT (bb->preds) == 1;
 473 }
 474
 475 /* Returns the single successor edge of basic block BB.  Aborts if
 476    BB does not have exactly one successor.  */
 477
 478 static inline edge
 479 single_succ_edge (const_basic_block bb)
 480 {
 481   gcc_checking_assert (single_succ_p (bb));
 482   return EDGE_SUCC (bb, 0);
 483 }
 484
 485 /* Returns the single predecessor edge of basic block BB.  Aborts
 486    if BB does not have exactly one predecessor.  */
 487
 488 static inline edge
 489 single_pred_edge (const_basic_block bb)
 490 {
 491   gcc_checking_assert (single_pred_p (bb));
 492   return EDGE_PRED (bb, 0);
 493 }
 494
 495 /* Returns the single successor block of basic block BB.  Aborts
 496    if BB does not have exactly one successor.  */
 497
 498 static inline basic_block
 499 single_succ (const_basic_block bb)
 500 {
 501   return single_succ_edge (bb)->dest;
 502 }
 503
 504 /* Returns the single predecessor block of basic block BB.  Aborts
 505    if BB does not have exactly one predecessor.*/
 506
 507 static inline basic_block
 508 single_pred (const_basic_block bb)
 509 {
 510   return single_pred_edge (bb)->src;
 511 }
 512
 513 /* Iterator object for edges.  */
 514
 515 struct edge_iterator {
 516   unsigned index;
 517   vec<edge, va_gc> **container;
 518 };
 519
 520 static inline vec<edge, va_gc> *
 521 ei_container (edge_iterator i)
 522 {
 523   gcc_checking_assert (i.container);
 524   return *i.container;
 525 }
 526
 527 #define ei_start(iter) ei_start_1 (&(iter))
 528 #define ei_last(iter) ei_last_1 (&(iter))
 529
 530 /* Return an iterator pointing to the start of an edge vector.  */
 531 static inline edge_iterator
 532 ei_start_1 (vec<edge, va_gc> **ev)
 533 {
 534   edge_iterator i;
 535
 536   i.index = 0;
 537   i.container = ev;
 538
 539   return i;
 540 }
 541
 542 /* Return an iterator pointing to the last element of an edge
 543    vector.  */
 544 static inline edge_iterator
 545 ei_last_1 (vec<edge, va_gc> **ev)
 546 {
 547   edge_iterator i;
 548
 549   i.index = EDGE_COUNT (*ev) - 1;
 550   i.container = ev;
 551
 552   return i;
 553 }
 554
 555 /* Is the iterator `i' at the end of the sequence?  */
 556 static inline bool
 557 ei_end_p (edge_iterator i)
 558 {
 559   return (i.index == EDGE_COUNT (ei_container (i)));
 560 }
 561
 562 /* Is the iterator `i' at one position before the end of the
 563    sequence?  */
 564 static inline bool
 565 ei_one_before_end_p (edge_iterator i)
 566 {
 567   return (i.index + 1 == EDGE_COUNT (ei_container (i)));
 568 }
 569
 570 /* Advance the iterator to the next element.  */
 571 static inline void
 572 ei_next (edge_iterator *i)
 573 {
 574   gcc_checking_assert (i->index < EDGE_COUNT (ei_container (*i)));
 575   i->index++;
 576 }
 577
 578 /* Move the iterator to the previous element.  */
 579 static inline void
 580 ei_prev (edge_iterator *i)
 581 {
 582   gcc_checking_assert (i->index > 0);
 583   i->index--;
 584 }
 585
 586 /* Return the edge pointed to by the iterator `i'.  */
 587 static inline edge
 588 ei_edge (edge_iterator i)
 589 {
 590   return EDGE_I (ei_container (i), i.index);
 591 }
 592
 593 /* Return an edge pointed to by the iterator.  Do it safely so that
 594    NULL is returned when the iterator is pointing at the end of the
 595    sequence.  */
 596 static inline edge
 597 ei_safe_edge (edge_iterator i)
 598 {
 599   return !ei_end_p (i) ? ei_edge (i) : NULL;
 600 }
 601
 602 /* Return 1 if we should continue to iterate.  Return 0 otherwise.
 603    *Edge P is set to the next edge if we are to continue to iterate
 604    and NULL otherwise.  */
 605
 606 static inline bool
 607 ei_cond (edge_iterator ei, edge *p)
 608 {
 609   if (!ei_end_p (ei))
 610     {
 611       *p = ei_edge (ei);
 612       return 1;
 613     }
 614   else
 615     {
 616       *p = NULL;
 617       return 0;
 618     }
 619 }
 620
 621 /* This macro serves as a convenient way to iterate each edge in a
 622    vector of predecessor or successor edges.  It must not be used when
 623    an element might be removed during the traversal, otherwise
 624    elements will be missed.  Instead, use a for-loop like that shown
 625    in the following pseudo-code:
 626
 627    FOR (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
 628      {
 629         IF (e != taken_edge)
 630           remove_edge (e);
 631         ELSE
 632           ei_next (&ei);
 633      }
 634 */
 635
 636 #define FOR_EACH_EDGE(EDGE,ITER,EDGE_VEC)       \
 637   for ((ITER) = ei_start ((EDGE_VEC));          \
 638        ei_cond ((ITER), &(EDGE));               \
 639        ei_next (&(ITER)))
 640
 641 #define CLEANUP_EXPENSIVE       1       /* Do relatively expensive optimizations
 642                                            except for edge forwarding */
 643 #define CLEANUP_CROSSJUMP       2       /* Do crossjumping.  */
 644 #define CLEANUP_POST_REGSTACK   4       /* We run after reg-stack and need
 645                                            to care REG_DEAD notes.  */
 646 #define CLEANUP_THREADING       8       /* Do jump threading.  */
 647 #define CLEANUP_NO_INSN_DEL     16      /* Do not try to delete trivially dead
 648                                            insns.  */
 649 #define CLEANUP_CFGLAYOUT       32      /* Do cleanup in cfglayout mode.  */
 650 #define CLEANUP_CFG_CHANGED     64      /* The caller changed the CFG.  */
 651
 652 extern void dump_flow_info (FILE *, int);
 653
 654 /* In predict.c */
 655 extern bool maybe_hot_count_p (struct function *, gcov_type);
 656 extern bool maybe_hot_bb_p (struct function *, const_basic_block);
 657 extern bool maybe_hot_edge_p (edge);
 658 extern bool probably_never_executed_bb_p (struct function *, const_basic_block);
 659 extern bool probably_never_executed_edge_p (struct function *, edge);
 660 extern bool optimize_bb_for_size_p (const_basic_block);
 661 extern bool optimize_bb_for_speed_p (const_basic_block);
 662 extern bool optimize_edge_for_size_p (edge);
 663 extern bool optimize_edge_for_speed_p (edge);
 664 extern bool optimize_loop_for_size_p (struct loop *);
 665 extern bool optimize_loop_for_speed_p (struct loop *);
 666 extern bool optimize_loop_nest_for_size_p (struct loop *);
 667 extern bool optimize_loop_nest_for_speed_p (struct loop *);
 668 extern bool gimple_predicted_by_p (const_basic_block, enum br_predictor);
 669 extern bool rtl_predicted_by_p (const_basic_block, enum br_predictor);
 670 extern void gimple_predict_edge (edge, enum br_predictor, int);
 671 extern void rtl_predict_edge (edge, enum br_predictor, int);
 672 extern void predict_edge_def (edge, enum br_predictor, enum prediction);
 673 extern void guess_outgoing_edge_probabilities (basic_block);
 674 extern void remove_predictions_associated_with_edge (edge);
 675 extern bool edge_probability_reliable_p (const_edge);
 676 extern bool br_prob_note_reliable_p (const_rtx);
 677 extern bool predictable_edge_p (edge);
 678
 679 /* In cfgbuild.c.  */
 680 extern void find_many_sub_basic_blocks (sbitmap);
 681 extern void rtl_make_eh_edge (sbitmap, basic_block, rtx);
 682
 683 enum replace_direction { dir_none, dir_forward, dir_backward, dir_both };
 684
 685 /* In cfgcleanup.c.  */
 686 extern bool cleanup_cfg (int);
 687 extern int flow_find_cross_jump (basic_block, basic_block, rtx_insn **,
 688                                  rtx_insn **, enum replace_direction*);
 689 extern int flow_find_head_matching_sequence (basic_block, basic_block,
 690                                              rtx_insn **, rtx_insn **, int);
 691
 692 extern bool delete_unreachable_blocks (void);
 693
 694 extern bool inside_basic_block_p (const rtx_insn *);
 695 extern bool control_flow_insn_p (const rtx_insn *);
 696 extern rtx_insn *get_last_bb_insn (basic_block);
 697
 698 /* In dominance.c */
 699
 700 enum cdi_direction
 701 {
 702   CDI_DOMINATORS = 1,
 703   CDI_POST_DOMINATORS = 2
 704 };
 705
 706 extern enum dom_state dom_info_state (function *, enum cdi_direction);
 707 extern enum dom_state dom_info_state (enum cdi_direction);
 708 extern void set_dom_info_availability (enum cdi_direction, enum dom_state);
 709 extern bool dom_info_available_p (function *, enum cdi_direction);
 710 extern bool dom_info_available_p (enum cdi_direction);
 711 extern void calculate_dominance_info (enum cdi_direction);
 712 extern void free_dominance_info (function *, enum cdi_direction);
 713 extern void free_dominance_info (enum cdi_direction);
 714 extern basic_block nearest_common_dominator (enum cdi_direction,
 715                                              basic_block, basic_block);
 716 extern basic_block nearest_common_dominator_for_set (enum cdi_direction,
 717                                                      bitmap);
 718 extern void set_immediate_dominator (enum cdi_direction, basic_block,
 719                                      basic_block);
 720 extern basic_block get_immediate_dominator (enum cdi_direction, basic_block);
 721 extern bool dominated_by_p (enum cdi_direction, const_basic_block, const_basic_block);
 722 extern vec<basic_block> get_dominated_by (enum cdi_direction, basic_block);
 723 extern vec<basic_block> get_dominated_by_region (enum cdi_direction,
 724                                                          basic_block *,
 725                                                          unsigned);
 726 extern vec<basic_block> get_dominated_to_depth (enum cdi_direction,
 727                                                         basic_block, int);
 728 extern vec<basic_block> get_all_dominated_blocks (enum cdi_direction,
 729                                                           basic_block);
 730 extern void add_to_dominance_info (enum cdi_direction, basic_block);
 731 extern void delete_from_dominance_info (enum cdi_direction, basic_block);
 732 basic_block recompute_dominator (enum cdi_direction, basic_block);
 733 extern void redirect_immediate_dominators (enum cdi_direction, basic_block,
 734                                            basic_block);
 735 extern void iterate_fix_dominators (enum cdi_direction,
 736                                     vec<basic_block> , bool);
 737 extern void verify_dominators (enum cdi_direction);
 738 extern basic_block first_dom_son (enum cdi_direction, basic_block);
 739 extern basic_block next_dom_son (enum cdi_direction, basic_block);
 740 unsigned bb_dom_dfs_in (enum cdi_direction, basic_block);
 741 unsigned bb_dom_dfs_out (enum cdi_direction, basic_block);
 742
 743 #include "cfghooks.h"
 744
 745 /* Return true if BB is in a transaction.  */
 746
 747 static inline bool
 748 bb_in_transaction (basic_block bb)
 749 {
 750   return bb->flags & BB_IN_TRANSACTION;
 751 }
 752
 753 /* Return true when one of the predecessor edges of BB is marked with EDGE_EH.  */
 754 static inline bool
 755 bb_has_eh_pred (basic_block bb)
 756 {
 757   edge e;
 758   edge_iterator ei;
 759
 760   FOR_EACH_EDGE (e, ei, bb->preds)
 761     {
 762       if (e->flags & EDGE_EH)
 763         return true;
 764     }
 765   return false;
 766 }
 767
 768 /* Return true when one of the predecessor edges of BB is marked with EDGE_ABNORMAL.  */
 769 static inline bool
 770 bb_has_abnormal_pred (basic_block bb)
 771 {
 772   edge e;
 773   edge_iterator ei;
 774
 775   FOR_EACH_EDGE (e, ei, bb->preds)
 776     {
 777       if (e->flags & EDGE_ABNORMAL)
 778         return true;
 779     }
 780   return false;
 781 }
 782
 783 /* Return the fallthru edge in EDGES if it exists, NULL otherwise.  */
 784 static inline edge
 785 find_fallthru_edge (vec<edge, va_gc> *edges)
 786 {
 787   edge e;
 788   edge_iterator ei;
 789
 790   FOR_EACH_EDGE (e, ei, edges)
 791     if (e->flags & EDGE_FALLTHRU)
 792       break;
 793
 794   return e;
 795 }
 796
 797 /* In cfgloopmanip.c.  */
 798 extern edge mfb_kj_edge;
 799 extern bool mfb_keep_just (edge);
 800
 801 /* In cfgexpand.c.  */
 802 extern void rtl_profile_for_bb (basic_block);
 803 extern void rtl_profile_for_edge (edge);
 804 extern void default_rtl_profile (void);
 805
 806 /* In profile.c.  */
 807 typedef struct gcov_working_set_info gcov_working_set_t;
 808 extern gcov_working_set_t *find_working_set (unsigned pct_times_10);
 809 extern void add_working_set (gcov_working_set_t *);
 810
 811 /* Check tha probability is sane.  */
 812
 813 static inline void
 814 check_probability (int prob)
 815 {
 816   gcc_checking_assert (prob >= 0 && prob <= REG_BR_PROB_BASE);
 817 }
 818
 819 /* Given PROB1 and PROB2, return PROB1*PROB2/REG_BR_PROB_BASE.
 820    Used to combine BB probabilities.  */
 821
 822 static inline int
 823 combine_probabilities (int prob1, int prob2)
 824 {
 825   check_probability (prob1);
 826   check_probability (prob2);
 827   return RDIV (prob1 * prob2, REG_BR_PROB_BASE);
 828 }
 829
 830 /* Apply scale factor SCALE on frequency or count FREQ. Use this
 831    interface when potentially scaling up, so that SCALE is not
 832    constrained to be < REG_BR_PROB_BASE.  */
 833
 834 static inline gcov_type
 835 apply_scale (gcov_type freq, gcov_type scale)
 836 {
 837   return RDIV (freq * scale, REG_BR_PROB_BASE);
 838 }
 839
 840 /* Apply probability PROB on frequency or count FREQ.  */
 841
 842 static inline gcov_type
 843 apply_probability (gcov_type freq, int prob)
 844 {
 845   check_probability (prob);
 846   return apply_scale (freq, prob);
 847 }
 848
 849 /* Return inverse probability for PROB.  */
 850
 851 static inline int
 852 inverse_probability (int prob1)
 853 {
 854   check_probability (prob1);
 855   return REG_BR_PROB_BASE - prob1;
 856 }
 857
 858 /* Return true if BB has at least one abnormal outgoing edge.  */
 859
 860 static inline bool
 861 has_abnormal_or_eh_outgoing_edge_p (basic_block bb)
 862 {
 863   edge e;
 864   edge_iterator ei;
 865
 866   FOR_EACH_EDGE (e, ei, bb->succs)
 867     if (e->flags & (EDGE_ABNORMAL | EDGE_EH))
 868       return true;
 869
 870   return false;
 871 }
 872 #endif /* GCC_BASIC_BLOCK_H */