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