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