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