1/* Define control flow data structures for the CFG. 2 Copyright (C) 1987-2015 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify it under 7the terms of the GNU General Public License as published by the Free 8Software Foundation; either version 3, or (at your option) any later 9version. 10 11GCC is distributed in the hope that it will be useful, but WITHOUT ANY 12WARRANTY; without even the implied warranty of MERCHANTABILITY or 13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14for more details. 15 16You should have received a copy of the GNU General Public License 17along 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 24/* Use gcov_type to hold basic block counters. Should be at least 25 64bit. Although a counter cannot be negative, we use a signed 26 type, because erroneous negative counts can be generated when the 27 flow graph is manipulated by various optimizations. A signed type 28 makes those easy to detect. */ 29 30/* Control flow edge information. */ 31struct GTY((user)) edge_def { 32 /* The two blocks at the ends of the edge. */ 33 basic_block src; 34 basic_block dest; 35 36 /* Instructions queued on the edge. */ 37 union edge_def_insns { 38 gimple_seq g; 39 rtx_insn *r; 40 } insns; 41 42 /* Auxiliary info specific to a pass. */ 43 PTR aux; 44 45 /* Location of any goto implicit in the edge. */ 46 location_t goto_locus; 47 48 /* The index number corresponding to this edge in the edge vector 49 dest->preds. */ 50 unsigned int dest_idx; 51 52 int flags; /* see cfg-flags.def */ 53 int probability; /* biased by REG_BR_PROB_BASE */ 54 gcov_type count; /* Expected number of executions calculated 55 in profile.c */ 56}; 57 58/* Masks for edge.flags. */ 59#define DEF_EDGE_FLAG(NAME,IDX) EDGE_##NAME = 1 << IDX , 60enum cfg_edge_flags { 61#include "cfg-flags.def" 62 LAST_CFG_EDGE_FLAG /* this is only used for EDGE_ALL_FLAGS */ 63}; 64#undef DEF_EDGE_FLAG 65 66/* Bit mask for all edge flags. */ 67#define EDGE_ALL_FLAGS ((LAST_CFG_EDGE_FLAG - 1) * 2 - 1) 68 69/* The following four flags all indicate something special about an edge. 70 Test the edge flags on EDGE_COMPLEX to detect all forms of "strange" 71 control flow transfers. */ 72#define EDGE_COMPLEX \ 73 (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_EH | EDGE_PRESERVE) 74 75struct GTY(()) rtl_bb_info { 76 /* The first insn of the block is embedded into bb->il.x. */ 77 /* The last insn of the block. */ 78 rtx_insn *end_; 79 80 /* In CFGlayout mode points to insn notes/jumptables to be placed just before 81 and after the block. */ 82 rtx_insn *header_; 83 rtx_insn *footer_; 84}; 85 86struct GTY(()) gimple_bb_info { 87 /* Sequence of statements in this block. */ 88 gimple_seq seq; 89 90 /* PHI nodes for this block. */ 91 gimple_seq phi_nodes; 92}; 93 94/* A basic block is a sequence of instructions with only one entry and 95 only one exit. If any one of the instructions are executed, they 96 will all be executed, and in sequence from first to last. 97 98 There may be COND_EXEC instructions in the basic block. The 99 COND_EXEC *instructions* will be executed -- but if the condition 100 is false the conditionally executed *expressions* will of course 101 not be executed. We don't consider the conditionally executed 102 expression (which might have side-effects) to be in a separate 103 basic block because the program counter will always be at the same 104 location after the COND_EXEC instruction, regardless of whether the 105 condition is true or not. 106 107 Basic blocks need not start with a label nor end with a jump insn. 108 For example, a previous basic block may just "conditionally fall" 109 into the succeeding basic block, and the last basic block need not 110 end with a jump insn. Block 0 is a descendant of the entry block. 111 112 A basic block beginning with two labels cannot have notes between 113 the labels. 114 115 Data for jump tables are stored in jump_insns that occur in no 116 basic block even though these insns can follow or precede insns in 117 basic blocks. */ 118 119/* Basic block information indexed by block number. */ 120struct GTY((chain_next ("%h.next_bb"), chain_prev ("%h.prev_bb"))) basic_block_def { 121 /* The edges into and out of the block. */ 122 vec<edge, va_gc> *preds; 123 vec<edge, va_gc> *succs; 124 125 /* Auxiliary info specific to a pass. */ 126 PTR GTY ((skip (""))) aux; 127 128 /* Innermost loop containing the block. */ 129 struct loop *loop_father; 130 131 /* The dominance and postdominance information node. */ 132 struct et_node * GTY ((skip (""))) dom[2]; 133 134 /* Previous and next blocks in the chain. */ 135 basic_block prev_bb; 136 basic_block next_bb; 137 138 union basic_block_il_dependent { 139 struct gimple_bb_info GTY ((tag ("0"))) gimple; 140 struct { 141 rtx_insn *head_; 142 struct rtl_bb_info * rtl; 143 } GTY ((tag ("1"))) x; 144 } GTY ((desc ("((%1.flags & BB_RTL) != 0)"))) il; 145 146 /* Various flags. See cfg-flags.def. */ 147 int flags; 148 149 /* The index of this block. */ 150 int index; 151 152 /* Expected number of executions: calculated in profile.c. */ 153 gcov_type count; 154 155 /* Expected frequency. Normalized to be in range 0 to BB_FREQ_MAX. */ 156 int frequency; 157 158 /* The discriminator for this block. The discriminator distinguishes 159 among several basic blocks that share a common locus, allowing for 160 more accurate sample-based profiling. */ 161 int discriminator; 162}; 163 164/* This ensures that struct gimple_bb_info is smaller than 165 struct rtl_bb_info, so that inlining the former into basic_block_def 166 is the better choice. */ 167typedef int __assert_gimple_bb_smaller_rtl_bb 168 [(int) sizeof (struct rtl_bb_info) 169 - (int) sizeof (struct gimple_bb_info)]; 170 171 172#define BB_FREQ_MAX 10000 173 174/* Masks for basic_block.flags. */ 175#define DEF_BASIC_BLOCK_FLAG(NAME,IDX) BB_##NAME = 1 << IDX , 176enum cfg_bb_flags 177{ 178#include "cfg-flags.def" 179 LAST_CFG_BB_FLAG /* this is only used for BB_ALL_FLAGS */ 180}; 181#undef DEF_BASIC_BLOCK_FLAG 182 183/* Bit mask for all basic block flags. */ 184#define BB_ALL_FLAGS ((LAST_CFG_BB_FLAG - 1) * 2 - 1) 185 186/* Bit mask for all basic block flags that must be preserved. These are 187 the bit masks that are *not* cleared by clear_bb_flags. */ 188#define BB_FLAGS_TO_PRESERVE \ 189 (BB_DISABLE_SCHEDULE | BB_RTL | BB_NON_LOCAL_GOTO_TARGET \ 190 | BB_HOT_PARTITION | BB_COLD_PARTITION) 191 192/* Dummy bitmask for convenience in the hot/cold partitioning code. */ 193#define BB_UNPARTITIONED 0 194 195/* Partitions, to be used when partitioning hot and cold basic blocks into 196 separate sections. */ 197#define BB_PARTITION(bb) ((bb)->flags & (BB_HOT_PARTITION|BB_COLD_PARTITION)) 198#define BB_SET_PARTITION(bb, part) do { \ 199 basic_block bb_ = (bb); \ 200 bb_->flags = ((bb_->flags & ~(BB_HOT_PARTITION|BB_COLD_PARTITION)) \ 201 | (part)); \ 202} while (0) 203 204#define BB_COPY_PARTITION(dstbb, srcbb) \ 205 BB_SET_PARTITION (dstbb, BB_PARTITION (srcbb)) 206 207/* Defines for accessing the fields of the CFG structure for function FN. */ 208#define ENTRY_BLOCK_PTR_FOR_FN(FN) ((FN)->cfg->x_entry_block_ptr) 209#define EXIT_BLOCK_PTR_FOR_FN(FN) ((FN)->cfg->x_exit_block_ptr) 210#define basic_block_info_for_fn(FN) ((FN)->cfg->x_basic_block_info) 211#define n_basic_blocks_for_fn(FN) ((FN)->cfg->x_n_basic_blocks) 212#define n_edges_for_fn(FN) ((FN)->cfg->x_n_edges) 213#define last_basic_block_for_fn(FN) ((FN)->cfg->x_last_basic_block) 214#define label_to_block_map_for_fn(FN) ((FN)->cfg->x_label_to_block_map) 215#define profile_status_for_fn(FN) ((FN)->cfg->x_profile_status) 216 217#define BASIC_BLOCK_FOR_FN(FN,N) \ 218 ((*basic_block_info_for_fn (FN))[(N)]) 219#define SET_BASIC_BLOCK_FOR_FN(FN,N,BB) \ 220 ((*basic_block_info_for_fn (FN))[(N)] = (BB)) 221 222/* For iterating over basic blocks. */ 223#define FOR_BB_BETWEEN(BB, FROM, TO, DIR) \ 224 for (BB = FROM; BB != TO; BB = BB->DIR) 225 226#define FOR_EACH_BB_FN(BB, FN) \ 227 FOR_BB_BETWEEN (BB, (FN)->cfg->x_entry_block_ptr->next_bb, (FN)->cfg->x_exit_block_ptr, next_bb) 228 229#define FOR_EACH_BB_REVERSE_FN(BB, FN) \ 230 FOR_BB_BETWEEN (BB, (FN)->cfg->x_exit_block_ptr->prev_bb, (FN)->cfg->x_entry_block_ptr, prev_bb) 231 232/* For iterating over insns in basic block. */ 233#define FOR_BB_INSNS(BB, INSN) \ 234 for ((INSN) = BB_HEAD (BB); \ 235 (INSN) && (INSN) != NEXT_INSN (BB_END (BB)); \ 236 (INSN) = NEXT_INSN (INSN)) 237 238/* For iterating over insns in basic block when we might remove the 239 current insn. */ 240#define FOR_BB_INSNS_SAFE(BB, INSN, CURR) \ 241 for ((INSN) = BB_HEAD (BB), (CURR) = (INSN) ? NEXT_INSN ((INSN)): NULL; \ 242 (INSN) && (INSN) != NEXT_INSN (BB_END (BB)); \ 243 (INSN) = (CURR), (CURR) = (INSN) ? NEXT_INSN ((INSN)) : NULL) 244 245#define FOR_BB_INSNS_REVERSE(BB, INSN) \ 246 for ((INSN) = BB_END (BB); \ 247 (INSN) && (INSN) != PREV_INSN (BB_HEAD (BB)); \ 248 (INSN) = PREV_INSN (INSN)) 249 250#define FOR_BB_INSNS_REVERSE_SAFE(BB, INSN, CURR) \ 251 for ((INSN) = BB_END (BB),(CURR) = (INSN) ? PREV_INSN ((INSN)) : NULL; \ 252 (INSN) && (INSN) != PREV_INSN (BB_HEAD (BB)); \ 253 (INSN) = (CURR), (CURR) = (INSN) ? PREV_INSN ((INSN)) : NULL) 254 255/* Cycles through _all_ basic blocks, even the fake ones (entry and 256 exit block). */ 257 258#define FOR_ALL_BB_FN(BB, FN) \ 259 for (BB = ENTRY_BLOCK_PTR_FOR_FN (FN); BB; BB = BB->next_bb) 260 261 262/* Stuff for recording basic block info. */ 263 264/* For now, these will be functions (so that they can include checked casts 265 to rtx_insn. Once the underlying fields are converted from rtx 266 to rtx_insn, these can be converted back to macros. */ 267 268#define BB_HEAD(B) (B)->il.x.head_ 269#define BB_END(B) (B)->il.x.rtl->end_ 270#define BB_HEADER(B) (B)->il.x.rtl->header_ 271#define BB_FOOTER(B) (B)->il.x.rtl->footer_ 272 273/* Special block numbers [markers] for entry and exit. 274 Neither of them is supposed to hold actual statements. */ 275#define ENTRY_BLOCK (0) 276#define EXIT_BLOCK (1) 277 278/* The two blocks that are always in the cfg. */ 279#define NUM_FIXED_BLOCKS (2) 280 281/* The base value for branch probability notes and edge probabilities. */ 282#define REG_BR_PROB_BASE 10000 283 284/* This is the value which indicates no edge is present. */ 285#define EDGE_INDEX_NO_EDGE -1 286 287/* EDGE_INDEX returns an integer index for an edge, or EDGE_INDEX_NO_EDGE 288 if there is no edge between the 2 basic blocks. */ 289#define EDGE_INDEX(el, pred, succ) (find_edge_index ((el), (pred), (succ))) 290 291/* INDEX_EDGE_PRED_BB and INDEX_EDGE_SUCC_BB return a pointer to the basic 292 block which is either the pred or succ end of the indexed edge. */ 293#define INDEX_EDGE_PRED_BB(el, index) ((el)->index_to_edge[(index)]->src) 294#define INDEX_EDGE_SUCC_BB(el, index) ((el)->index_to_edge[(index)]->dest) 295 296/* INDEX_EDGE returns a pointer to the edge. */ 297#define INDEX_EDGE(el, index) ((el)->index_to_edge[(index)]) 298 299/* Number of edges in the compressed edge list. */ 300#define NUM_EDGES(el) ((el)->num_edges) 301 302/* BB is assumed to contain conditional jump. Return the fallthru edge. */ 303#define FALLTHRU_EDGE(bb) (EDGE_SUCC ((bb), 0)->flags & EDGE_FALLTHRU \ 304 ? EDGE_SUCC ((bb), 0) : EDGE_SUCC ((bb), 1)) 305 306/* BB is assumed to contain conditional jump. Return the branch edge. */ 307#define BRANCH_EDGE(bb) (EDGE_SUCC ((bb), 0)->flags & EDGE_FALLTHRU \ 308 ? EDGE_SUCC ((bb), 1) : EDGE_SUCC ((bb), 0)) 309 310#define RDIV(X,Y) (((X) + (Y) / 2) / (Y)) 311/* Return expected execution frequency of the edge E. */ 312#define EDGE_FREQUENCY(e) RDIV ((e)->src->frequency * (e)->probability, \ 313 REG_BR_PROB_BASE) 314 315/* Compute a scale factor (or probability) suitable for scaling of 316 gcov_type values via apply_probability() and apply_scale(). */ 317#define GCOV_COMPUTE_SCALE(num,den) \ 318 ((den) ? RDIV ((num) * REG_BR_PROB_BASE, (den)) : REG_BR_PROB_BASE) 319 320/* Return nonzero if edge is critical. */ 321#define EDGE_CRITICAL_P(e) (EDGE_COUNT ((e)->src->succs) >= 2 \ 322 && EDGE_COUNT ((e)->dest->preds) >= 2) 323 324#define EDGE_COUNT(ev) vec_safe_length (ev) 325#define EDGE_I(ev,i) (*ev)[(i)] 326#define EDGE_PRED(bb,i) (*(bb)->preds)[(i)] 327#define EDGE_SUCC(bb,i) (*(bb)->succs)[(i)] 328 329/* Returns true if BB has precisely one successor. */ 330 331static inline bool 332single_succ_p (const_basic_block bb) 333{ 334 return EDGE_COUNT (bb->succs) == 1; 335} 336 337/* Returns true if BB has precisely one predecessor. */ 338 339static inline bool 340single_pred_p (const_basic_block bb) 341{ 342 return EDGE_COUNT (bb->preds) == 1; 343} 344 345/* Returns the single successor edge of basic block BB. Aborts if 346 BB does not have exactly one successor. */ 347 348static inline edge 349single_succ_edge (const_basic_block bb) 350{ 351 gcc_checking_assert (single_succ_p (bb)); 352 return EDGE_SUCC (bb, 0); 353} 354 355/* Returns the single predecessor edge of basic block BB. Aborts 356 if BB does not have exactly one predecessor. */ 357 358static inline edge 359single_pred_edge (const_basic_block bb) 360{ 361 gcc_checking_assert (single_pred_p (bb)); 362 return EDGE_PRED (bb, 0); 363} 364 365/* Returns the single successor block of basic block BB. Aborts 366 if BB does not have exactly one successor. */ 367 368static inline basic_block 369single_succ (const_basic_block bb) 370{ 371 return single_succ_edge (bb)->dest; 372} 373 374/* Returns the single predecessor block of basic block BB. Aborts 375 if BB does not have exactly one predecessor.*/ 376 377static inline basic_block 378single_pred (const_basic_block bb) 379{ 380 return single_pred_edge (bb)->src; 381} 382 383/* Iterator object for edges. */ 384 385struct edge_iterator { 386 unsigned index; 387 vec<edge, va_gc> **container; 388}; 389 390static inline vec<edge, va_gc> * 391ei_container (edge_iterator i) 392{ 393 gcc_checking_assert (i.container); 394 return *i.container; 395} 396 397#define ei_start(iter) ei_start_1 (&(iter)) 398#define ei_last(iter) ei_last_1 (&(iter)) 399 400/* Return an iterator pointing to the start of an edge vector. */ 401static inline edge_iterator 402ei_start_1 (vec<edge, va_gc> **ev) 403{ 404 edge_iterator i; 405 406 i.index = 0; 407 i.container = ev; 408 409 return i; 410} 411 412/* Return an iterator pointing to the last element of an edge 413 vector. */ 414static inline edge_iterator 415ei_last_1 (vec<edge, va_gc> **ev) 416{ 417 edge_iterator i; 418 419 i.index = EDGE_COUNT (*ev) - 1; 420 i.container = ev; 421 422 return i; 423} 424 425/* Is the iterator `i' at the end of the sequence? */ 426static inline bool 427ei_end_p (edge_iterator i) 428{ 429 return (i.index == EDGE_COUNT (ei_container (i))); 430} 431 432/* Is the iterator `i' at one position before the end of the 433 sequence? */ 434static inline bool 435ei_one_before_end_p (edge_iterator i) 436{ 437 return (i.index + 1 == EDGE_COUNT (ei_container (i))); 438} 439 440/* Advance the iterator to the next element. */ 441static inline void 442ei_next (edge_iterator *i) 443{ 444 gcc_checking_assert (i->index < EDGE_COUNT (ei_container (*i))); 445 i->index++; 446} 447 448/* Move the iterator to the previous element. */ 449static inline void 450ei_prev (edge_iterator *i) 451{ 452 gcc_checking_assert (i->index > 0); 453 i->index--; 454} 455 456/* Return the edge pointed to by the iterator `i'. */ 457static inline edge 458ei_edge (edge_iterator i) 459{ 460 return EDGE_I (ei_container (i), i.index); 461} 462 463/* Return an edge pointed to by the iterator. Do it safely so that 464 NULL is returned when the iterator is pointing at the end of the 465 sequence. */ 466static inline edge 467ei_safe_edge (edge_iterator i) 468{ 469 return !ei_end_p (i) ? ei_edge (i) : NULL; 470} 471 472/* Return 1 if we should continue to iterate. Return 0 otherwise. 473 *Edge P is set to the next edge if we are to continue to iterate 474 and NULL otherwise. */ 475 476static inline bool 477ei_cond (edge_iterator ei, edge *p) 478{ 479 if (!ei_end_p (ei)) 480 { 481 *p = ei_edge (ei); 482 return 1; 483 } 484 else 485 { 486 *p = NULL; 487 return 0; 488 } 489} 490 491/* This macro serves as a convenient way to iterate each edge in a 492 vector of predecessor or successor edges. It must not be used when 493 an element might be removed during the traversal, otherwise 494 elements will be missed. Instead, use a for-loop like that shown 495 in the following pseudo-code: 496 497 FOR (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ) 498 { 499 IF (e != taken_edge) 500 remove_edge (e); 501 ELSE 502 ei_next (&ei); 503 } 504*/ 505 506#define FOR_EACH_EDGE(EDGE,ITER,EDGE_VEC) \ 507 for ((ITER) = ei_start ((EDGE_VEC)); \ 508 ei_cond ((ITER), &(EDGE)); \ 509 ei_next (&(ITER))) 510 511#define CLEANUP_EXPENSIVE 1 /* Do relatively expensive optimizations 512 except for edge forwarding */ 513#define CLEANUP_CROSSJUMP 2 /* Do crossjumping. */ 514#define CLEANUP_POST_REGSTACK 4 /* We run after reg-stack and need 515 to care REG_DEAD notes. */ 516#define CLEANUP_THREADING 8 /* Do jump threading. */ 517#define CLEANUP_NO_INSN_DEL 16 /* Do not try to delete trivially dead 518 insns. */ 519#define CLEANUP_CFGLAYOUT 32 /* Do cleanup in cfglayout mode. */ 520#define CLEANUP_CFG_CHANGED 64 /* The caller changed the CFG. */ 521 522#include "cfghooks.h" 523 524/* Return true if BB is in a transaction. */ 525 526static inline bool 527bb_in_transaction (basic_block bb) 528{ 529 return bb->flags & BB_IN_TRANSACTION; 530} 531 532/* Return true when one of the predecessor edges of BB is marked with EDGE_EH. */ 533static inline bool 534bb_has_eh_pred (basic_block bb) 535{ 536 edge e; 537 edge_iterator ei; 538 539 FOR_EACH_EDGE (e, ei, bb->preds) 540 { 541 if (e->flags & EDGE_EH) 542 return true; 543 } 544 return false; 545} 546 547/* Return true when one of the predecessor edges of BB is marked with EDGE_ABNORMAL. */ 548static inline bool 549bb_has_abnormal_pred (basic_block bb) 550{ 551 edge e; 552 edge_iterator ei; 553 554 FOR_EACH_EDGE (e, ei, bb->preds) 555 { 556 if (e->flags & EDGE_ABNORMAL) 557 return true; 558 } 559 return false; 560} 561 562/* Return the fallthru edge in EDGES if it exists, NULL otherwise. */ 563static inline edge 564find_fallthru_edge (vec<edge, va_gc> *edges) 565{ 566 edge e; 567 edge_iterator ei; 568 569 FOR_EACH_EDGE (e, ei, edges) 570 if (e->flags & EDGE_FALLTHRU) 571 break; 572 573 return e; 574} 575 576/* Check tha probability is sane. */ 577 578static inline void 579check_probability (int prob) 580{ 581 gcc_checking_assert (prob >= 0 && prob <= REG_BR_PROB_BASE); 582} 583 584/* Given PROB1 and PROB2, return PROB1*PROB2/REG_BR_PROB_BASE. 585 Used to combine BB probabilities. */ 586 587static inline int 588combine_probabilities (int prob1, int prob2) 589{ 590 check_probability (prob1); 591 check_probability (prob2); 592 return RDIV (prob1 * prob2, REG_BR_PROB_BASE); 593} 594 595/* Apply scale factor SCALE on frequency or count FREQ. Use this 596 interface when potentially scaling up, so that SCALE is not 597 constrained to be < REG_BR_PROB_BASE. */ 598 599static inline gcov_type 600apply_scale (gcov_type freq, gcov_type scale) 601{ 602 return RDIV (freq * scale, REG_BR_PROB_BASE); 603} 604 605/* Apply probability PROB on frequency or count FREQ. */ 606 607static inline gcov_type 608apply_probability (gcov_type freq, int prob) 609{ 610 check_probability (prob); 611 return apply_scale (freq, prob); 612} 613 614/* Return inverse probability for PROB. */ 615 616static inline int 617inverse_probability (int prob1) 618{ 619 check_probability (prob1); 620 return REG_BR_PROB_BASE - prob1; 621} 622 623/* Return true if BB has at least one abnormal outgoing edge. */ 624 625static inline bool 626has_abnormal_or_eh_outgoing_edge_p (basic_block bb) 627{ 628 edge e; 629 edge_iterator ei; 630 631 FOR_EACH_EDGE (e, ei, bb->succs) 632 if (e->flags & (EDGE_ABNORMAL | EDGE_EH)) 633 return true; 634 635 return false; 636} 637#endif /* GCC_BASIC_BLOCK_H */ 638