1 /* Define control and data flow tables, and regsets. 2 Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2002, 2003 3 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 2, 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 COPYING. If not, write to the Free 19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA 20 02111-1307, USA. */ 21 22 #ifndef GCC_BASIC_BLOCK_H 23 #define GCC_BASIC_BLOCK_H 24 25 #include "bitmap.h" 26 #include "sbitmap.h" 27 #include "varray.h" 28 #include "partition.h" 29 #include "hard-reg-set.h" 30 31 /* Head of register set linked list. */ 32 typedef bitmap_head regset_head; 33 /* A pointer to a regset_head. */ 34 typedef bitmap regset; 35 36 /* Initialize a new regset. */ 37 #define INIT_REG_SET(HEAD) bitmap_initialize (HEAD, 1) 38 39 /* Clear a register set by freeing up the linked list. */ 40 #define CLEAR_REG_SET(HEAD) bitmap_clear (HEAD) 41 42 /* Copy a register set to another register set. */ 43 #define COPY_REG_SET(TO, FROM) bitmap_copy (TO, FROM) 44 45 /* Compare two register sets. */ 46 #define REG_SET_EQUAL_P(A, B) bitmap_equal_p (A, B) 47 48 /* `and' a register set with a second register set. */ 49 #define AND_REG_SET(TO, FROM) bitmap_operation (TO, TO, FROM, BITMAP_AND) 50 51 /* `and' the complement of a register set with a register set. */ 52 #define AND_COMPL_REG_SET(TO, FROM) \ 53 bitmap_operation (TO, TO, FROM, BITMAP_AND_COMPL) 54 55 /* Inclusive or a register set with a second register set. */ 56 #define IOR_REG_SET(TO, FROM) bitmap_operation (TO, TO, FROM, BITMAP_IOR) 57 58 /* Exclusive or a register set with a second register set. */ 59 #define XOR_REG_SET(TO, FROM) bitmap_operation (TO, TO, FROM, BITMAP_XOR) 60 61 /* Or into TO the register set FROM1 `and'ed with the complement of FROM2. */ 62 #define IOR_AND_COMPL_REG_SET(TO, FROM1, FROM2) \ 63 bitmap_ior_and_compl (TO, FROM1, FROM2) 64 65 /* Clear a single register in a register set. */ 66 #define CLEAR_REGNO_REG_SET(HEAD, REG) bitmap_clear_bit (HEAD, REG) 67 68 /* Set a single register in a register set. */ 69 #define SET_REGNO_REG_SET(HEAD, REG) bitmap_set_bit (HEAD, REG) 70 71 /* Return true if a register is set in a register set. */ 72 #define REGNO_REG_SET_P(TO, REG) bitmap_bit_p (TO, REG) 73 74 /* Copy the hard registers in a register set to the hard register set. */ 75 extern void reg_set_to_hard_reg_set PARAMS ((HARD_REG_SET *, bitmap)); 76 #define REG_SET_TO_HARD_REG_SET(TO, FROM) \ 77 do { \ 78 CLEAR_HARD_REG_SET (TO); \ 79 reg_set_to_hard_reg_set (&TO, FROM); \ 80 } while (0) 81 82 /* Loop over all registers in REGSET, starting with MIN, setting REGNUM to the 83 register number and executing CODE for all registers that are set. */ 84 #define EXECUTE_IF_SET_IN_REG_SET(REGSET, MIN, REGNUM, CODE) \ 85 EXECUTE_IF_SET_IN_BITMAP (REGSET, MIN, REGNUM, CODE) 86 87 /* Loop over all registers in REGSET1 and REGSET2, starting with MIN, setting 88 REGNUM to the register number and executing CODE for all registers that are 89 set in the first regset and not set in the second. */ 90 #define EXECUTE_IF_AND_COMPL_IN_REG_SET(REGSET1, REGSET2, MIN, REGNUM, CODE) \ 91 EXECUTE_IF_AND_COMPL_IN_BITMAP (REGSET1, REGSET2, MIN, REGNUM, CODE) 92 93 /* Loop over all registers in REGSET1 and REGSET2, starting with MIN, setting 94 REGNUM to the register number and executing CODE for all registers that are 95 set in both regsets. */ 96 #define EXECUTE_IF_AND_IN_REG_SET(REGSET1, REGSET2, MIN, REGNUM, CODE) \ 97 EXECUTE_IF_AND_IN_BITMAP (REGSET1, REGSET2, MIN, REGNUM, CODE) 98 99 /* Allocate a register set with oballoc. */ 100 #define OBSTACK_ALLOC_REG_SET(OBSTACK) BITMAP_OBSTACK_ALLOC (OBSTACK) 101 102 /* Initialize a register set. Returns the new register set. */ 103 #define INITIALIZE_REG_SET(HEAD) bitmap_initialize (&HEAD, 1) 104 105 /* Do any cleanup needed on a regset when it is no longer used. */ 106 #define FREE_REG_SET(REGSET) BITMAP_FREE(REGSET) 107 108 /* Do any one-time initializations needed for regsets. */ 109 #define INIT_ONCE_REG_SET() BITMAP_INIT_ONCE () 110 111 /* Grow any tables needed when the number of registers is calculated 112 or extended. For the linked list allocation, nothing needs to 113 be done, other than zero the statistics on the first allocation. */ 114 #define MAX_REGNO_REG_SET(NUM_REGS, NEW_P, RENUMBER_P) 115 116 /* Type we use to hold basic block counters. Should be at least 64bit. */ 117 typedef HOST_WIDEST_INT gcov_type; 118 119 /* Control flow edge information. */ 120 typedef struct edge_def { 121 /* Links through the predecessor and successor lists. */ 122 struct edge_def *pred_next, *succ_next; 123 124 /* The two blocks at the ends of the edge. */ 125 struct basic_block_def *src, *dest; 126 127 /* Instructions queued on the edge. */ 128 rtx insns; 129 130 /* Auxiliary info specific to a pass. */ 131 void *aux; 132 133 int flags; /* see EDGE_* below */ 134 int probability; /* biased by REG_BR_PROB_BASE */ 135 gcov_type count; /* Expected number of executions calculated 136 in profile.c */ 137 } *edge; 138 139 #define EDGE_FALLTHRU 1 /* 'Straight line' flow */ 140 #define EDGE_ABNORMAL 2 /* Strange flow, like computed 141 label, or eh */ 142 #define EDGE_ABNORMAL_CALL 4 /* Call with abnormal exit 143 like an exception, or sibcall */ 144 #define EDGE_EH 8 /* Exception throw */ 145 #define EDGE_FAKE 16 /* Not a real edge (profile.c) */ 146 #define EDGE_DFS_BACK 32 /* A backwards edge */ 147 #define EDGE_CAN_FALLTHRU 64 /* Candidate for straight line 148 flow. */ 149 150 #define EDGE_COMPLEX (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_EH) 151 152 153 /* A basic block is a sequence of instructions with only 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 typedef struct basic_block_def { 180 /* The first and last insns of the block. */ 181 rtx head, end; 182 183 /* The first and last trees of the block. */ 184 tree head_tree; 185 tree end_tree; 186 187 /* The edges into and out of the block. */ 188 edge pred, succ; 189 190 /* Liveness info. */ 191 192 /* The registers that are modified within this in block. */ 193 regset local_set; 194 /* The registers that are conditionally modified within this block. 195 In other words, registers that are set only as part of a 196 COND_EXEC. */ 197 regset cond_local_set; 198 /* The registers that are live on entry to this block. 199 200 Note that in SSA form, global_live_at_start does not reflect the 201 use of regs in phi functions, since the liveness of these regs 202 may depend on which edge was taken into the block. */ 203 regset global_live_at_start; 204 /* The registers that are live on exit from this block. */ 205 regset global_live_at_end; 206 207 /* Auxiliary info specific to a pass. */ 208 void *aux; 209 210 /* The index of this block. */ 211 int index; 212 213 /* Previous and next blocks in the chain. */ 214 struct basic_block_def *prev_bb, *next_bb; 215 216 /* The loop depth of this block. */ 217 int loop_depth; 218 219 /* Outermost loop containing the block. */ 220 struct loop *loop_father; 221 222 /* Expected number of executions: calculated in profile.c. */ 223 gcov_type count; 224 225 /* Expected frequency. Normalized to be in range 0 to BB_FREQ_MAX. */ 226 int frequency; 227 228 /* Various flags. See BB_* below. */ 229 int flags; 230 } *basic_block; 231 232 #define BB_FREQ_MAX 10000 233 234 /* Masks for basic_block.flags. */ 235 #define BB_DIRTY 1 236 #define BB_NEW 2 237 #define BB_REACHABLE 4 238 #define BB_VISITED 8 239 240 /* Number of basic blocks in the current function. */ 241 242 extern int n_basic_blocks; 243 244 /* First free basic block number. */ 245 246 extern int last_basic_block; 247 248 /* Number of edges in the current function. */ 249 250 extern int n_edges; 251 252 /* Index by basic block number, get basic block struct info. */ 253 254 extern varray_type basic_block_info; 255 256 #define BASIC_BLOCK(N) (VARRAY_BB (basic_block_info, (N))) 257 258 /* For iterating over basic blocks. */ 259 #define FOR_BB_BETWEEN(BB, FROM, TO, DIR) \ 260 for (BB = FROM; BB != TO; BB = BB->DIR) 261 262 #define FOR_EACH_BB(BB) \ 263 FOR_BB_BETWEEN (BB, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR, next_bb) 264 265 #define FOR_EACH_BB_REVERSE(BB) \ 266 FOR_BB_BETWEEN (BB, EXIT_BLOCK_PTR->prev_bb, ENTRY_BLOCK_PTR, prev_bb) 267 268 /* Cycles through _all_ basic blocks, even the fake ones (entry and 269 exit block). */ 270 271 #define FOR_ALL_BB(BB) \ 272 for (BB = ENTRY_BLOCK_PTR; BB; BB = BB->next_bb) 273 274 /* What registers are live at the setjmp call. */ 275 276 extern regset regs_live_at_setjmp; 277 278 /* Special labels found during CFG build. */ 279 280 extern GTY(()) rtx label_value_list; 281 extern GTY(()) rtx tail_recursion_label_list; 282 283 extern struct obstack flow_obstack; 284 285 /* Indexed by n, gives number of basic block that (REG n) is used in. 286 If the value is REG_BLOCK_GLOBAL (-2), 287 it means (REG n) is used in more than one basic block. 288 REG_BLOCK_UNKNOWN (-1) means it hasn't been seen yet so we don't know. 289 This information remains valid for the rest of the compilation 290 of the current function; it is used to control register allocation. */ 291 292 #define REG_BLOCK_UNKNOWN -1 293 #define REG_BLOCK_GLOBAL -2 294 295 #define REG_BASIC_BLOCK(N) (VARRAY_REG (reg_n_info, N)->basic_block) 296 297 /* Stuff for recording basic block info. */ 298 299 #define BLOCK_HEAD(B) (BASIC_BLOCK (B)->head) 300 #define BLOCK_END(B) (BASIC_BLOCK (B)->end) 301 302 #define BLOCK_HEAD_TREE(B) (BASIC_BLOCK (B)->head_tree) 303 #define BLOCK_END_TREE(B) (BASIC_BLOCK (B)->end_tree) 304 305 /* Special block numbers [markers] for entry and exit. */ 306 #define ENTRY_BLOCK (-1) 307 #define EXIT_BLOCK (-2) 308 309 /* Special block number not valid for any block. */ 310 #define INVALID_BLOCK (-3) 311 312 /* Similarly, block pointers for the edge list. */ 313 extern struct basic_block_def entry_exit_blocks[2]; 314 #define ENTRY_BLOCK_PTR (&entry_exit_blocks[0]) 315 #define EXIT_BLOCK_PTR (&entry_exit_blocks[1]) 316 317 #define BLOCK_NUM(INSN) (BLOCK_FOR_INSN (INSN)->index + 0) 318 #define set_block_for_insn(INSN, BB) (BLOCK_FOR_INSN (INSN) = BB) 319 320 extern void compute_bb_for_insn PARAMS ((void)); 321 extern void free_bb_for_insn PARAMS ((void)); 322 extern void update_bb_for_insn PARAMS ((basic_block)); 323 324 extern void free_basic_block_vars PARAMS ((int)); 325 326 extern edge split_block PARAMS ((basic_block, rtx)); 327 extern basic_block split_edge PARAMS ((edge)); 328 extern void insert_insn_on_edge PARAMS ((rtx, edge)); 329 330 extern void commit_edge_insertions PARAMS ((void)); 331 extern void commit_edge_insertions_watch_calls PARAMS ((void)); 332 333 extern void remove_fake_edges PARAMS ((void)); 334 extern void add_noreturn_fake_exit_edges PARAMS ((void)); 335 extern void connect_infinite_loops_to_exit PARAMS ((void)); 336 extern int flow_call_edges_add PARAMS ((sbitmap)); 337 extern edge cached_make_edge PARAMS ((sbitmap *, basic_block, 338 basic_block, int)); 339 extern edge unchecked_make_edge PARAMS ((basic_block, 340 basic_block, int)); 341 extern edge make_edge PARAMS ((basic_block, 342 basic_block, int)); 343 extern edge make_single_succ_edge PARAMS ((basic_block, 344 basic_block, int)); 345 extern void remove_edge PARAMS ((edge)); 346 extern void redirect_edge_succ PARAMS ((edge, basic_block)); 347 extern edge redirect_edge_succ_nodup PARAMS ((edge, basic_block)); 348 extern void redirect_edge_pred PARAMS ((edge, basic_block)); 349 extern basic_block create_basic_block_structure PARAMS ((rtx, rtx, rtx, basic_block)); 350 extern basic_block create_basic_block PARAMS ((rtx, rtx, basic_block)); 351 extern int flow_delete_block PARAMS ((basic_block)); 352 extern int flow_delete_block_noexpunge PARAMS ((basic_block)); 353 extern void clear_bb_flags PARAMS ((void)); 354 extern void merge_blocks_nomove PARAMS ((basic_block, basic_block)); 355 extern void tidy_fallthru_edge PARAMS ((edge, basic_block, 356 basic_block)); 357 extern void tidy_fallthru_edges PARAMS ((void)); 358 extern void flow_reverse_top_sort_order_compute PARAMS ((int *)); 359 extern int flow_depth_first_order_compute PARAMS ((int *, int *)); 360 extern void flow_preorder_transversal_compute PARAMS ((int *)); 361 extern void dump_edge_info PARAMS ((FILE *, edge, int)); 362 extern void clear_edges PARAMS ((void)); 363 extern void mark_critical_edges PARAMS ((void)); 364 extern rtx first_insn_after_basic_block_note PARAMS ((basic_block)); 365 366 /* Dominator information for basic blocks. */ 367 368 typedef struct dominance_info *dominance_info; 369 370 /* Structure to hold information for each natural loop. */ 371 struct loop 372 { 373 /* Index into loops array. */ 374 int num; 375 376 /* Basic block of loop header. */ 377 basic_block header; 378 379 /* Basic block of loop latch. */ 380 basic_block latch; 381 382 /* Basic block of loop pre-header or NULL if it does not exist. */ 383 basic_block pre_header; 384 385 /* Array of edges along the pre-header extended basic block trace. 386 The source of the first edge is the root node of pre-header 387 extended basic block, if it exists. */ 388 edge *pre_header_edges; 389 390 /* Number of edges along the pre_header extended basic block trace. */ 391 int num_pre_header_edges; 392 393 /* The first block in the loop. This is not necessarily the same as 394 the loop header. */ 395 basic_block first; 396 397 /* The last block in the loop. This is not necessarily the same as 398 the loop latch. */ 399 basic_block last; 400 401 /* Bitmap of blocks contained within the loop. */ 402 sbitmap nodes; 403 404 /* Number of blocks contained within the loop. */ 405 int num_nodes; 406 407 /* Array of edges that enter the loop. */ 408 edge *entry_edges; 409 410 /* Number of edges that enter the loop. */ 411 int num_entries; 412 413 /* Array of edges that exit the loop. */ 414 edge *exit_edges; 415 416 /* Number of edges that exit the loop. */ 417 int num_exits; 418 419 /* Bitmap of blocks that dominate all exits of the loop. */ 420 sbitmap exits_doms; 421 422 /* The loop nesting depth. */ 423 int depth; 424 425 /* Superloops of the loop. */ 426 struct loop **pred; 427 428 /* The height of the loop (enclosed loop levels) within the loop 429 hierarchy tree. */ 430 int level; 431 432 /* The outer (parent) loop or NULL if outermost loop. */ 433 struct loop *outer; 434 435 /* The first inner (child) loop or NULL if innermost loop. */ 436 struct loop *inner; 437 438 /* Link to the next (sibling) loop. */ 439 struct loop *next; 440 441 /* Nonzero if the loop is invalid (e.g., contains setjmp.). */ 442 int invalid; 443 444 /* Auxiliary info specific to a pass. */ 445 void *aux; 446 447 /* The following are currently used by loop.c but they are likely to 448 disappear as loop.c is converted to use the CFG. */ 449 450 /* Nonzero if the loop has a NOTE_INSN_LOOP_VTOP. */ 451 rtx vtop; 452 453 /* Nonzero if the loop has a NOTE_INSN_LOOP_CONT. 454 A continue statement will generate a branch to NEXT_INSN (cont). */ 455 rtx cont; 456 457 /* The NOTE_INSN_LOOP_BEG. */ 458 rtx start; 459 460 /* The NOTE_INSN_LOOP_END. */ 461 rtx end; 462 463 /* For a rotated loop that is entered near the bottom, 464 this is the label at the top. Otherwise it is zero. */ 465 rtx top; 466 467 /* Place in the loop where control enters. */ 468 rtx scan_start; 469 470 /* The position where to sink insns out of the loop. */ 471 rtx sink; 472 473 /* List of all LABEL_REFs which refer to code labels outside the 474 loop. Used by routines that need to know all loop exits, such as 475 final_biv_value and final_giv_value. 476 477 This does not include loop exits due to return instructions. 478 This is because all bivs and givs are pseudos, and hence must be 479 dead after a return, so the presense of a return does not affect 480 any of the optimizations that use this info. It is simpler to 481 just not include return instructions on this list. */ 482 rtx exit_labels; 483 484 /* The number of LABEL_REFs on exit_labels for this loop and all 485 loops nested inside it. */ 486 int exit_count; 487 }; 488 489 490 /* Structure to hold CFG information about natural loops within a function. */ 491 struct loops 492 { 493 /* Number of natural loops in the function. */ 494 int num; 495 496 /* Maxium nested loop level in the function. */ 497 int levels; 498 499 /* Array of natural loop descriptors (scanning this array in reverse order 500 will find the inner loops before their enclosing outer loops). */ 501 struct loop *array; 502 503 /* The above array is unused in new loop infrastructure and is kept only for 504 purposes of the old loop optimizer. Instead we store just pointers to 505 loops here. */ 506 struct loop **parray; 507 508 /* Pointer to root of loop heirachy tree. */ 509 struct loop *tree_root; 510 511 /* Information derived from the CFG. */ 512 struct cfg 513 { 514 /* The bitmap vector of dominators or NULL if not computed. */ 515 dominance_info dom; 516 517 /* The ordering of the basic blocks in a depth first search. */ 518 int *dfs_order; 519 520 /* The reverse completion ordering of the basic blocks found in a 521 depth first search. */ 522 int *rc_order; 523 } cfg; 524 525 /* Headers shared by multiple loops that should be merged. */ 526 sbitmap shared_headers; 527 }; 528 529 /* Structure to group all of the information to process IF-THEN and 530 IF-THEN-ELSE blocks for the conditional execution support. This 531 needs to be in a public file in case the IFCVT macros call 532 functions passing the ce_if_block data structure. */ 533 534 typedef struct ce_if_block 535 { 536 basic_block test_bb; /* First test block. */ 537 basic_block then_bb; /* THEN block. */ 538 basic_block else_bb; /* ELSE block or NULL. */ 539 basic_block join_bb; /* Join THEN/ELSE blocks. */ 540 basic_block last_test_bb; /* Last bb to hold && or || tests. */ 541 int num_multiple_test_blocks; /* # of && and || basic blocks. */ 542 int num_and_and_blocks; /* # of && blocks. */ 543 int num_or_or_blocks; /* # of || blocks. */ 544 int num_multiple_test_insns; /* # of insns in && and || blocks. */ 545 int and_and_p; /* Complex test is &&. */ 546 int num_then_insns; /* # of insns in THEN block. */ 547 int num_else_insns; /* # of insns in ELSE block. */ 548 int pass; /* Pass number. */ 549 550 #ifdef IFCVT_EXTRA_FIELDS 551 IFCVT_EXTRA_FIELDS /* Any machine dependent fields. */ 552 #endif 553 554 } ce_if_block_t; 555 556 extern int flow_loops_find PARAMS ((struct loops *, int flags)); 557 extern int flow_loops_update PARAMS ((struct loops *, int flags)); 558 extern void flow_loops_free PARAMS ((struct loops *)); 559 extern void flow_loops_dump PARAMS ((const struct loops *, FILE *, 560 void (*)(const struct loop *, 561 FILE *, int), int)); 562 extern void flow_loop_dump PARAMS ((const struct loop *, FILE *, 563 void (*)(const struct loop *, 564 FILE *, int), int)); 565 extern int flow_loop_scan PARAMS ((struct loops *, struct loop *, int)); 566 extern void flow_loop_tree_node_add PARAMS ((struct loop *, struct loop *)); 567 extern void flow_loop_tree_node_remove PARAMS ((struct loop *)); 568 569 /* This structure maintains an edge list vector. */ 570 struct edge_list 571 { 572 int num_blocks; 573 int num_edges; 574 edge *index_to_edge; 575 }; 576 577 /* This is the value which indicates no edge is present. */ 578 #define EDGE_INDEX_NO_EDGE -1 579 580 /* EDGE_INDEX returns an integer index for an edge, or EDGE_INDEX_NO_EDGE 581 if there is no edge between the 2 basic blocks. */ 582 #define EDGE_INDEX(el, pred, succ) (find_edge_index ((el), (pred), (succ))) 583 584 /* INDEX_EDGE_PRED_BB and INDEX_EDGE_SUCC_BB return a pointer to the basic 585 block which is either the pred or succ end of the indexed edge. */ 586 #define INDEX_EDGE_PRED_BB(el, index) ((el)->index_to_edge[(index)]->src) 587 #define INDEX_EDGE_SUCC_BB(el, index) ((el)->index_to_edge[(index)]->dest) 588 589 /* INDEX_EDGE returns a pointer to the edge. */ 590 #define INDEX_EDGE(el, index) ((el)->index_to_edge[(index)]) 591 592 /* Number of edges in the compressed edge list. */ 593 #define NUM_EDGES(el) ((el)->num_edges) 594 595 /* BB is assumed to contain conditional jump. Return the fallthru edge. */ 596 #define FALLTHRU_EDGE(bb) ((bb)->succ->flags & EDGE_FALLTHRU \ 597 ? (bb)->succ : (bb)->succ->succ_next) 598 599 /* BB is assumed to contain conditional jump. Return the branch edge. */ 600 #define BRANCH_EDGE(bb) ((bb)->succ->flags & EDGE_FALLTHRU \ 601 ? (bb)->succ->succ_next : (bb)->succ) 602 603 /* Return expected execution frequency of the edge E. */ 604 #define EDGE_FREQUENCY(e) (((e)->src->frequency \ 605 * (e)->probability \ 606 + REG_BR_PROB_BASE / 2) \ 607 / REG_BR_PROB_BASE) 608 609 /* Return nonzero if edge is critical. */ 610 #define EDGE_CRITICAL_P(e) ((e)->src->succ->succ_next \ 611 && (e)->dest->pred->pred_next) 612 613 struct edge_list * create_edge_list PARAMS ((void)); 614 void free_edge_list PARAMS ((struct edge_list *)); 615 void print_edge_list PARAMS ((FILE *, struct edge_list *)); 616 void verify_edge_list PARAMS ((FILE *, struct edge_list *)); 617 int find_edge_index PARAMS ((struct edge_list *, 618 basic_block, basic_block)); 619 620 621 enum update_life_extent 622 { 623 UPDATE_LIFE_LOCAL = 0, 624 UPDATE_LIFE_GLOBAL = 1, 625 UPDATE_LIFE_GLOBAL_RM_NOTES = 2 626 }; 627 628 /* Flags for life_analysis and update_life_info. */ 629 630 #define PROP_DEATH_NOTES 1 /* Create DEAD and UNUSED notes. */ 631 #define PROP_LOG_LINKS 2 /* Create LOG_LINKS. */ 632 #define PROP_REG_INFO 4 /* Update regs_ever_live et al. */ 633 #define PROP_KILL_DEAD_CODE 8 /* Remove dead code. */ 634 #define PROP_SCAN_DEAD_CODE 16 /* Scan for dead code. */ 635 #define PROP_ALLOW_CFG_CHANGES 32 /* Allow the CFG to be changed 636 by dead code removal. */ 637 #define PROP_AUTOINC 64 /* Create autoinc mem references. */ 638 #define PROP_EQUAL_NOTES 128 /* Take into account REG_EQUAL notes. */ 639 #define PROP_SCAN_DEAD_STORES 256 /* Scan for dead code. */ 640 #define PROP_FINAL (PROP_DEATH_NOTES | PROP_LOG_LINKS \ 641 | PROP_REG_INFO | PROP_KILL_DEAD_CODE \ 642 | PROP_SCAN_DEAD_CODE | PROP_AUTOINC \ 643 | PROP_ALLOW_CFG_CHANGES \ 644 | PROP_SCAN_DEAD_STORES) 645 646 #define CLEANUP_EXPENSIVE 1 /* Do relativly expensive optimizations 647 except for edge forwarding */ 648 #define CLEANUP_CROSSJUMP 2 /* Do crossjumping. */ 649 #define CLEANUP_POST_REGSTACK 4 /* We run after reg-stack and need 650 to care REG_DEAD notes. */ 651 #define CLEANUP_PRE_SIBCALL 8 /* Do not get confused by code hidden 652 inside call_placeholders.. */ 653 #define CLEANUP_PRE_LOOP 16 /* Take care to preserve syntactic loop 654 notes. */ 655 #define CLEANUP_UPDATE_LIFE 32 /* Keep life information up to date. */ 656 #define CLEANUP_THREADING 64 /* Do jump threading. */ 657 #define CLEANUP_NO_INSN_DEL 128 /* Do not try to delete trivially dead 658 insns. */ 659 /* Flags for loop discovery. */ 660 661 #define LOOP_TREE 1 /* Build loop hierarchy tree. */ 662 #define LOOP_PRE_HEADER 2 /* Analyse loop pre-header. */ 663 #define LOOP_ENTRY_EDGES 4 /* Find entry edges. */ 664 #define LOOP_EXIT_EDGES 8 /* Find exit edges. */ 665 #define LOOP_EDGES (LOOP_ENTRY_EDGES | LOOP_EXIT_EDGES) 666 #define LOOP_ALL 15 /* All of the above */ 667 668 extern void life_analysis PARAMS ((rtx, FILE *, int)); 669 extern int update_life_info PARAMS ((sbitmap, enum update_life_extent, 670 int)); 671 extern int update_life_info_in_dirty_blocks PARAMS ((enum update_life_extent, 672 int)); 673 extern int count_or_remove_death_notes PARAMS ((sbitmap, int)); 674 extern int propagate_block PARAMS ((basic_block, regset, regset, regset, 675 int)); 676 677 struct propagate_block_info; 678 extern rtx propagate_one_insn PARAMS ((struct propagate_block_info *, rtx)); 679 extern struct propagate_block_info *init_propagate_block_info 680 PARAMS ((basic_block, regset, regset, regset, int)); 681 extern void free_propagate_block_info PARAMS ((struct propagate_block_info *)); 682 683 /* In lcm.c */ 684 extern struct edge_list *pre_edge_lcm PARAMS ((FILE *, int, sbitmap *, 685 sbitmap *, sbitmap *, 686 sbitmap *, sbitmap **, 687 sbitmap **)); 688 extern struct edge_list *pre_edge_rev_lcm PARAMS ((FILE *, int, sbitmap *, 689 sbitmap *, sbitmap *, 690 sbitmap *, sbitmap **, 691 sbitmap **)); 692 extern void compute_available PARAMS ((sbitmap *, sbitmap *, 693 sbitmap *, sbitmap *)); 694 extern int optimize_mode_switching PARAMS ((FILE *)); 695 696 /* In emit-rtl.c. */ 697 extern rtx emit_block_insn_after PARAMS ((rtx, rtx, basic_block)); 698 extern rtx emit_block_insn_before PARAMS ((rtx, rtx, basic_block)); 699 700 /* In predict.c */ 701 extern void estimate_probability PARAMS ((struct loops *)); 702 extern void note_prediction_to_br_prob PARAMS ((void)); 703 extern void expected_value_to_br_prob PARAMS ((void)); 704 extern void note_prediction_to_br_prob PARAMS ((void)); 705 extern bool maybe_hot_bb_p PARAMS ((basic_block)); 706 extern bool probably_cold_bb_p PARAMS ((basic_block)); 707 extern bool probably_never_executed_bb_p PARAMS ((basic_block)); 708 709 /* In flow.c */ 710 extern void init_flow PARAMS ((void)); 711 extern void reorder_basic_blocks PARAMS ((void)); 712 extern void dump_bb PARAMS ((basic_block, FILE *)); 713 extern void debug_bb PARAMS ((basic_block)); 714 extern void debug_bb_n PARAMS ((int)); 715 extern void dump_regset PARAMS ((regset, FILE *)); 716 extern void debug_regset PARAMS ((regset)); 717 extern void allocate_reg_life_data PARAMS ((void)); 718 extern void allocate_bb_life_data PARAMS ((void)); 719 extern void expunge_block PARAMS ((basic_block)); 720 extern void link_block PARAMS ((basic_block, basic_block)); 721 extern void unlink_block PARAMS ((basic_block)); 722 extern void compact_blocks PARAMS ((void)); 723 extern basic_block alloc_block PARAMS ((void)); 724 extern void find_unreachable_blocks PARAMS ((void)); 725 extern int delete_noop_moves PARAMS ((rtx)); 726 extern basic_block redirect_edge_and_branch_force PARAMS ((edge, basic_block)); 727 extern basic_block force_nonfallthru PARAMS ((edge)); 728 extern bool redirect_edge_and_branch PARAMS ((edge, basic_block)); 729 extern rtx block_label PARAMS ((basic_block)); 730 extern bool forwarder_block_p PARAMS ((basic_block)); 731 extern bool purge_all_dead_edges PARAMS ((int)); 732 extern bool purge_dead_edges PARAMS ((basic_block)); 733 extern void find_sub_basic_blocks PARAMS ((basic_block)); 734 extern void find_many_sub_basic_blocks PARAMS ((sbitmap)); 735 extern bool can_fallthru PARAMS ((basic_block, basic_block)); 736 extern void flow_nodes_print PARAMS ((const char *, const sbitmap, 737 FILE *)); 738 extern void flow_edge_list_print PARAMS ((const char *, const edge *, 739 int, FILE *)); 740 extern void alloc_aux_for_block PARAMS ((basic_block, int)); 741 extern void alloc_aux_for_blocks PARAMS ((int)); 742 extern void clear_aux_for_blocks PARAMS ((void)); 743 extern void free_aux_for_blocks PARAMS ((void)); 744 extern void alloc_aux_for_edge PARAMS ((edge, int)); 745 extern void alloc_aux_for_edges PARAMS ((int)); 746 extern void clear_aux_for_edges PARAMS ((void)); 747 extern void free_aux_for_edges PARAMS ((void)); 748 749 /* This function is always defined so it can be called from the 750 debugger, and it is declared extern so we don't get warnings about 751 it being unused. */ 752 extern void verify_flow_info PARAMS ((void)); 753 extern bool flow_loop_outside_edge_p PARAMS ((const struct loop *, edge)); 754 extern bool flow_loop_nested_p PARAMS ((const struct loop *, 755 const struct loop *)); 756 extern bool flow_bb_inside_loop_p PARAMS ((const struct loop *, 757 const basic_block)); 758 extern basic_block *get_loop_body PARAMS ((const struct loop *)); 759 extern int dfs_enumerate_from PARAMS ((basic_block, int, 760 bool (*)(basic_block, void *), 761 basic_block *, int, void *)); 762 763 extern edge loop_preheader_edge PARAMS ((struct loop *)); 764 extern edge loop_latch_edge PARAMS ((struct loop *)); 765 766 extern void add_bb_to_loop PARAMS ((basic_block, struct loop *)); 767 extern void remove_bb_from_loops PARAMS ((basic_block)); 768 extern struct loop * find_common_loop PARAMS ((struct loop *, struct loop *)); 769 770 extern void verify_loop_structure PARAMS ((struct loops *, int)); 771 #define VLS_EXPECT_PREHEADERS 1 772 #define VLS_EXPECT_SIMPLE_LATCHES 2 773 774 typedef struct conflict_graph_def *conflict_graph; 775 776 /* Callback function when enumerating conflicts. The arguments are 777 the smaller and larger regno in the conflict. Returns zero if 778 enumeration is to continue, nonzero to halt enumeration. */ 779 typedef int (*conflict_graph_enum_fn) PARAMS ((int, int, void *)); 780 781 782 /* Prototypes of operations on conflict graphs. */ 783 784 extern conflict_graph conflict_graph_new 785 PARAMS ((int)); 786 extern void conflict_graph_delete PARAMS ((conflict_graph)); 787 extern int conflict_graph_add PARAMS ((conflict_graph, 788 int, int)); 789 extern int conflict_graph_conflict_p PARAMS ((conflict_graph, 790 int, int)); 791 extern void conflict_graph_enum PARAMS ((conflict_graph, int, 792 conflict_graph_enum_fn, 793 void *)); 794 extern void conflict_graph_merge_regs PARAMS ((conflict_graph, int, 795 int)); 796 extern void conflict_graph_print PARAMS ((conflict_graph, FILE*)); 797 extern conflict_graph conflict_graph_compute 798 PARAMS ((regset, 799 partition)); 800 extern bool mark_dfs_back_edges PARAMS ((void)); 801 extern void set_edge_can_fallthru_flag PARAMS ((void)); 802 extern void update_br_prob_note PARAMS ((basic_block)); 803 extern void fixup_abnormal_edges PARAMS ((void)); 804 extern bool can_hoist_insn_p PARAMS ((rtx, rtx, regset)); 805 extern rtx hoist_insn_after PARAMS ((rtx, rtx, rtx, rtx)); 806 extern rtx hoist_insn_to_edge PARAMS ((rtx, edge, rtx, rtx)); 807 extern bool control_flow_insn_p PARAMS ((rtx)); 808 809 /* In dominance.c */ 810 811 enum cdi_direction 812 { 813 CDI_DOMINATORS, 814 CDI_POST_DOMINATORS 815 }; 816 817 extern dominance_info calculate_dominance_info PARAMS ((enum cdi_direction)); 818 extern void free_dominance_info PARAMS ((dominance_info)); 819 extern basic_block nearest_common_dominator PARAMS ((dominance_info, 820 basic_block, basic_block)); 821 extern void set_immediate_dominator PARAMS ((dominance_info, 822 basic_block, basic_block)); 823 extern basic_block get_immediate_dominator PARAMS ((dominance_info, 824 basic_block)); 825 extern bool dominated_by_p PARAMS ((dominance_info, basic_block, basic_block)); 826 extern int get_dominated_by PARAMS ((dominance_info, basic_block, basic_block **)); 827 extern void add_to_dominance_info PARAMS ((dominance_info, basic_block)); 828 extern void delete_from_dominance_info PARAMS ((dominance_info, basic_block)); 829 basic_block recount_dominator PARAMS ((dominance_info, basic_block)); 830 extern void redirect_immediate_dominators PARAMS ((dominance_info, basic_block, 831 basic_block)); 832 void iterate_fix_dominators PARAMS ((dominance_info, basic_block *, int)); 833 extern void verify_dominators PARAMS ((dominance_info)); 834 #endif /* GCC_BASIC_BLOCK_H */ 835