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