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 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 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 151typedef struct edge_def *edge; 152typedef const struct edge_def *const_edge; 153DEF_VEC_P(edge); 154DEF_VEC_ALLOC_P(edge,gc); 155DEF_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. */ 185extern const struct gcov_ctr_summary *profile_info; 186 187/* Declared in cfgloop.h. */ 188struct loop; 189 190/* Declared in tree-flow.h. */ 191struct edge_prediction; 192struct 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 219enum sample_profile_confidence 220{ 221 LOW_CONFIDENCE = 0, 222 NORMAL_CONFIDENCE, 223 HIGH_CONFIDENCE 224}; 225 226/* Basic block information indexed by block number. */ 227struct 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 270struct 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 285struct 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 294typedef struct basic_block_def *basic_block; 295typedef const struct basic_block_def *const_basic_block; 296 297DEF_VEC_P(basic_block); 298DEF_VEC_ALLOC_P(basic_block,gc); 299DEF_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 311enum 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 371enum 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. */ 382struct 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 499extern bitmap_obstack reg_obstack; 500 501 502/* Stuff for recording basic block info. */ 503 504#define BB_HEAD(B) (B)->il.rtl->head_ 505#define BB_END(B) (B)->il.rtl->end_ 506 507/* Special block numbers [markers] for entry and exit. */ 508#define ENTRY_BLOCK (0) 509#define EXIT_BLOCK (1) 510 511/* The two blocks that are always in the cfg. */ 512#define NUM_FIXED_BLOCKS (2) 513 514 515#define BLOCK_NUM(INSN) (BLOCK_FOR_INSN (INSN)->index + 0) 516#define set_block_for_insn(INSN, BB) (BLOCK_FOR_INSN (INSN) = BB) 517 518extern bool profile_info_available_p (void); 519extern void compute_bb_for_insn (void); 520extern unsigned int free_bb_for_insn (void); 521extern void update_bb_for_insn (basic_block); 522 523extern void insert_insn_on_edge (rtx, edge); 524basic_block split_edge_and_insert (edge, rtx); 525 526extern bool commit_edge_insertions (void); 527 528extern void remove_fake_edges (void); 529extern void remove_fake_exit_edges (void); 530extern void add_noreturn_fake_exit_edges (void); 531extern void connect_infinite_loops_to_exit (void); 532extern edge unchecked_make_edge (basic_block, basic_block, int); 533extern edge cached_make_edge (sbitmap, basic_block, basic_block, int); 534extern edge make_edge (basic_block, basic_block, int); 535extern edge make_single_succ_edge (basic_block, basic_block, int); 536extern void remove_edge_raw (edge); 537extern void redirect_edge_succ (edge, basic_block); 538extern edge redirect_edge_succ_nodup (edge, basic_block); 539extern void redirect_edge_pred (edge, basic_block); 540extern basic_block create_basic_block_structure (rtx, rtx, rtx, basic_block); 541extern void clear_bb_flags (void); 542extern int post_order_compute (int *, bool, bool); 543extern int inverted_post_order_compute (int *); 544extern int pre_and_rev_post_order_compute (int *, int *, bool); 545extern int dfs_enumerate_from (basic_block, int, 546 bool (*)(const_basic_block, const void *), 547 basic_block *, int, const void *); 548extern void compute_dominance_frontiers (bitmap *); 549extern bitmap compute_idf (bitmap, bitmap *); 550extern void dump_bb_info (basic_block, bool, bool, int, const char *, FILE *); 551extern void dump_edge_info (FILE *, edge, int); 552extern void brief_dump_cfg (FILE *); 553extern void clear_edges (void); 554extern void scale_bbs_frequencies_int (basic_block *, int, int, int); 555extern void scale_bbs_frequencies_gcov_type (basic_block *, int, gcov_type, 556 gcov_type); 557 558/* Structure to group all of the information to process IF-THEN and 559 IF-THEN-ELSE blocks for the conditional execution support. This 560 needs to be in a public file in case the IFCVT macros call 561 functions passing the ce_if_block data structure. */ 562 563typedef struct ce_if_block 564{ 565 basic_block test_bb; /* First test block. */ 566 basic_block then_bb; /* THEN block. */ 567 basic_block else_bb; /* ELSE block or NULL. */ 568 basic_block join_bb; /* Join THEN/ELSE blocks. */ 569 basic_block last_test_bb; /* Last bb to hold && or || tests. */ 570 int num_multiple_test_blocks; /* # of && and || basic blocks. */ 571 int num_and_and_blocks; /* # of && blocks. */ 572 int num_or_or_blocks; /* # of || blocks. */ 573 int num_multiple_test_insns; /* # of insns in && and || blocks. */ 574 int and_and_p; /* Complex test is &&. */ 575 int num_then_insns; /* # of insns in THEN block. */ 576 int num_else_insns; /* # of insns in ELSE block. */ 577 int pass; /* Pass number. */ 578 579#ifdef IFCVT_EXTRA_FIELDS 580 IFCVT_EXTRA_FIELDS /* Any machine dependent fields. */ 581#endif 582 583} ce_if_block_t; 584 585/* This structure maintains an edge list vector. */ 586struct edge_list 587{ 588 int num_blocks; 589 int num_edges; 590 edge *index_to_edge; 591}; 592 593/* The base value for branch probability notes and edge probabilities. */ 594#define REG_BR_PROB_BASE 10000 595 596/* This is the value which indicates no edge is present. */ 597#define EDGE_INDEX_NO_EDGE -1 598 599/* EDGE_INDEX returns an integer index for an edge, or EDGE_INDEX_NO_EDGE 600 if there is no edge between the 2 basic blocks. */ 601#define EDGE_INDEX(el, pred, succ) (find_edge_index ((el), (pred), (succ))) 602 603/* INDEX_EDGE_PRED_BB and INDEX_EDGE_SUCC_BB return a pointer to the basic 604 block which is either the pred or succ end of the indexed edge. */ 605#define INDEX_EDGE_PRED_BB(el, index) ((el)->index_to_edge[(index)]->src) 606#define INDEX_EDGE_SUCC_BB(el, index) ((el)->index_to_edge[(index)]->dest) 607 608/* INDEX_EDGE returns a pointer to the edge. */ 609#define INDEX_EDGE(el, index) ((el)->index_to_edge[(index)]) 610 611/* Number of edges in the compressed edge list. */ 612#define NUM_EDGES(el) ((el)->num_edges) 613 614/* BB is assumed to contain conditional jump. Return the fallthru edge. */ 615#define FALLTHRU_EDGE(bb) (EDGE_SUCC ((bb), 0)->flags & EDGE_FALLTHRU \ 616 ? EDGE_SUCC ((bb), 0) : EDGE_SUCC ((bb), 1)) 617 618/* BB is assumed to contain conditional jump. Return the branch edge. */ 619#define BRANCH_EDGE(bb) (EDGE_SUCC ((bb), 0)->flags & EDGE_FALLTHRU \ 620 ? EDGE_SUCC ((bb), 1) : EDGE_SUCC ((bb), 0)) 621 622/* Return expected execution frequency of the edge E. */ 623#define EDGE_FREQUENCY(e) (((e)->src->frequency \ 624 * (e)->probability \ 625 + REG_BR_PROB_BASE / 2) \ 626 / REG_BR_PROB_BASE) 627 628/* Return nonzero if edge is critical. */ 629#define EDGE_CRITICAL_P(e) (EDGE_COUNT ((e)->src->succs) >= 2 \ 630 && EDGE_COUNT ((e)->dest->preds) >= 2) 631 632#define EDGE_COUNT(ev) VEC_length (edge, (ev)) 633#define EDGE_I(ev,i) VEC_index (edge, (ev), (i)) 634#define EDGE_PRED(bb,i) VEC_index (edge, (bb)->preds, (i)) 635#define EDGE_SUCC(bb,i) VEC_index (edge, (bb)->succs, (i)) 636 637/* Returns true if BB has precisely one successor. */ 638 639static inline bool 640single_succ_p (const_basic_block bb) 641{ 642 return EDGE_COUNT (bb->succs) == 1; 643} 644 645/* Returns true if BB has precisely one predecessor. */ 646 647static inline bool 648single_pred_p (const_basic_block bb) 649{ 650 return EDGE_COUNT (bb->preds) == 1; 651} 652 653/* Returns the single successor edge of basic block BB. Aborts if 654 BB does not have exactly one successor. */ 655 656static inline edge 657single_succ_edge (const_basic_block bb) 658{ 659 gcc_assert (single_succ_p (bb)); 660 return EDGE_SUCC (bb, 0); 661} 662 663/* Returns the single predecessor edge of basic block BB. Aborts 664 if BB does not have exactly one predecessor. */ 665 666static inline edge 667single_pred_edge (const_basic_block bb) 668{ 669 gcc_assert (single_pred_p (bb)); 670 return EDGE_PRED (bb, 0); 671} 672 673/* Returns the single successor block of basic block BB. Aborts 674 if BB does not have exactly one successor. */ 675 676static inline basic_block 677single_succ (const_basic_block bb) 678{ 679 return single_succ_edge (bb)->dest; 680} 681 682/* Returns the single predecessor block of basic block BB. Aborts 683 if BB does not have exactly one predecessor.*/ 684 685static inline basic_block 686single_pred (const_basic_block bb) 687{ 688 return single_pred_edge (bb)->src; 689} 690 691/* Iterator object for edges. */ 692 693typedef struct { 694 unsigned index; 695 VEC(edge,gc) **container; 696} edge_iterator; 697 698static inline VEC(edge,gc) * 699ei_container (edge_iterator i) 700{ 701 gcc_assert (i.container); 702 return *i.container; 703} 704 705#define ei_start(iter) ei_start_1 (&(iter)) 706#define ei_last(iter) ei_last_1 (&(iter)) 707 708/* Return an iterator pointing to the start of an edge vector. */ 709static inline edge_iterator 710ei_start_1 (VEC(edge,gc) **ev) 711{ 712 edge_iterator i; 713 714 i.index = 0; 715 i.container = ev; 716 717 return i; 718} 719 720/* Return an iterator pointing to the last element of an edge 721 vector. */ 722static inline edge_iterator 723ei_last_1 (VEC(edge,gc) **ev) 724{ 725 edge_iterator i; 726 727 i.index = EDGE_COUNT (*ev) - 1; 728 i.container = ev; 729 730 return i; 731} 732 733/* Is the iterator `i' at the end of the sequence? */ 734static inline bool 735ei_end_p (edge_iterator i) 736{ 737 return (i.index == EDGE_COUNT (ei_container (i))); 738} 739 740/* Is the iterator `i' at one position before the end of the 741 sequence? */ 742static inline bool 743ei_one_before_end_p (edge_iterator i) 744{ 745 return (i.index + 1 == EDGE_COUNT (ei_container (i))); 746} 747 748/* Advance the iterator to the next element. */ 749static inline void 750ei_next (edge_iterator *i) 751{ 752 gcc_assert (i->index < EDGE_COUNT (ei_container (*i))); 753 i->index++; 754} 755 756/* Move the iterator to the previous element. */ 757static inline void 758ei_prev (edge_iterator *i) 759{ 760 gcc_assert (i->index > 0); 761 i->index--; 762} 763 764/* Return the edge pointed to by the iterator `i'. */ 765static inline edge 766ei_edge (edge_iterator i) 767{ 768 return EDGE_I (ei_container (i), i.index); 769} 770 771/* Return an edge pointed to by the iterator. Do it safely so that 772 NULL is returned when the iterator is pointing at the end of the 773 sequence. */ 774static inline edge 775ei_safe_edge (edge_iterator i) 776{ 777 return !ei_end_p (i) ? ei_edge (i) : NULL; 778} 779 780/* Return 1 if we should continue to iterate. Return 0 otherwise. 781 *Edge P is set to the next edge if we are to continue to iterate 782 and NULL otherwise. */ 783 784static inline bool 785ei_cond (edge_iterator ei, edge *p) 786{ 787 if (!ei_end_p (ei)) 788 { 789 *p = ei_edge (ei); 790 return 1; 791 } 792 else 793 { 794 *p = NULL; 795 return 0; 796 } 797} 798 799/* This macro serves as a convenient way to iterate each edge in a 800 vector of predecessor or successor edges. It must not be used when 801 an element might be removed during the traversal, otherwise 802 elements will be missed. Instead, use a for-loop like that shown 803 in the following pseudo-code: 804 805 FOR (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ) 806 { 807 IF (e != taken_edge) 808 remove_edge (e); 809 ELSE 810 ei_next (&ei); 811 } 812*/ 813 814#define FOR_EACH_EDGE(EDGE,ITER,EDGE_VEC) \ 815 for ((ITER) = ei_start ((EDGE_VEC)); \ 816 ei_cond ((ITER), &(EDGE)); \ 817 ei_next (&(ITER))) 818 819struct edge_list * create_edge_list (void); 820void free_edge_list (struct edge_list *); 821void print_edge_list (FILE *, struct edge_list *); 822void verify_edge_list (FILE *, struct edge_list *); 823int find_edge_index (struct edge_list *, basic_block, basic_block); 824edge find_edge (basic_block, basic_block); 825 826#define CLEANUP_EXPENSIVE 1 /* Do relatively expensive optimizations 827 except for edge forwarding */ 828#define CLEANUP_CROSSJUMP 2 /* Do crossjumping. */ 829#define CLEANUP_POST_REGSTACK 4 /* We run after reg-stack and need 830 to care REG_DEAD notes. */ 831#define CLEANUP_THREADING 8 /* Do jump threading. */ 832#define CLEANUP_NO_INSN_DEL 16 /* Do not try to delete trivially dead 833 insns. */ 834#define CLEANUP_CFGLAYOUT 32 /* Do cleanup in cfglayout mode. */ 835 836/* In lcm.c */ 837extern struct edge_list *pre_edge_lcm (int, sbitmap *, sbitmap *, 838 sbitmap *, sbitmap *, sbitmap **, 839 sbitmap **); 840extern struct edge_list *pre_edge_rev_lcm (int, sbitmap *, 841 sbitmap *, sbitmap *, 842 sbitmap *, sbitmap **, 843 sbitmap **); 844extern void compute_available (sbitmap *, sbitmap *, sbitmap *, sbitmap *); 845 846/* In predict.c */ 847extern bool maybe_hot_bb_p (const_basic_block); 848extern bool maybe_hot_bb_for_func_p (struct function *, const_basic_block); 849extern bool maybe_hot_edge_p (edge); 850extern bool probably_never_executed_bb_p (const_basic_block); 851extern bool optimize_bb_for_size_p (const_basic_block); 852extern bool optimize_bb_for_speed_p (const_basic_block); 853extern bool optimize_edge_for_size_p (edge); 854extern bool optimize_edge_for_speed_p (edge); 855extern bool optimize_function_for_size_p (struct function *); 856extern bool optimize_function_for_speed_p (struct function *); 857extern bool optimize_loop_for_size_p (struct loop *); 858extern bool optimize_loop_for_speed_p (struct loop *); 859extern bool optimize_loop_nest_for_size_p (struct loop *); 860extern bool optimize_loop_nest_for_speed_p (struct loop *); 861extern bool gimple_predicted_by_p (const_basic_block, enum br_predictor); 862extern bool rtl_predicted_by_p (const_basic_block, enum br_predictor); 863extern void gimple_predict_edge (edge, enum br_predictor, int); 864extern void rtl_predict_edge (edge, enum br_predictor, int); 865extern void predict_edge_def (edge, enum br_predictor, enum prediction); 866extern void guess_outgoing_edge_probabilities (basic_block); 867extern void remove_predictions_associated_with_edge (edge); 868extern bool edge_probability_reliable_p (const_edge); 869extern bool br_prob_note_reliable_p (const_rtx); 870extern bool predictable_edge_p (edge); 871extern unsigned int tree_estimate_probability (void); 872 873/* In cfg.c */ 874extern void dump_regset (regset, FILE *); 875extern void debug_regset (regset); 876extern void init_flow (struct function *); 877extern void debug_bb (basic_block); 878extern basic_block debug_bb_n (int); 879extern void dump_regset (regset, FILE *); 880extern void debug_regset (regset); 881extern void expunge_block (basic_block); 882extern void link_block (basic_block, basic_block); 883extern void unlink_block (basic_block); 884extern void compact_blocks (void); 885extern basic_block alloc_block (void); 886extern void alloc_aux_for_block (basic_block, int); 887extern void alloc_aux_for_blocks (int); 888extern void clear_aux_for_blocks (void); 889extern void free_aux_for_blocks (void); 890extern void alloc_aux_for_edge (edge, int); 891extern void alloc_aux_for_edges (int); 892extern void clear_aux_for_edges (void); 893extern void free_aux_for_edges (void); 894 895/* In cfganal.c */ 896extern void find_unreachable_blocks (void); 897extern bool forwarder_block_p (const_basic_block); 898extern bool can_fallthru (basic_block, basic_block); 899extern bool could_fall_through (basic_block, basic_block); 900extern void flow_nodes_print (const char *, const_sbitmap, FILE *); 901extern void flow_edge_list_print (const char *, const edge *, int, FILE *); 902 903/* In cfgrtl.c */ 904extern basic_block force_nonfallthru (edge); 905extern rtx block_label (basic_block); 906extern bool purge_all_dead_edges (void); 907extern bool purge_dead_edges (basic_block); 908 909/* In cfgbuild.c. */ 910extern void find_many_sub_basic_blocks (sbitmap); 911extern void rtl_make_eh_edge (sbitmap, basic_block, rtx); 912extern void find_basic_blocks (rtx); 913 914/* In cfgcleanup.c. */ 915extern bool cleanup_cfg (int); 916extern int flow_find_cross_jump (basic_block, basic_block, rtx *, rtx *); 917extern int flow_find_head_matching_sequence (basic_block, basic_block, 918 rtx *, rtx *, int); 919 920extern bool delete_unreachable_blocks (void); 921 922extern bool mark_dfs_back_edges (void); 923extern void set_edge_can_fallthru_flag (void); 924extern void update_br_prob_note (basic_block); 925extern void fixup_abnormal_edges (void); 926extern bool inside_basic_block_p (const_rtx); 927extern bool control_flow_insn_p (const_rtx); 928extern rtx get_last_bb_insn (basic_block); 929 930/* In bb-reorder.c */ 931extern void reorder_basic_blocks (void); 932 933/* In dominance.c */ 934 935enum cdi_direction 936{ 937 CDI_DOMINATORS = 1, 938 CDI_POST_DOMINATORS = 2 939}; 940 941extern enum dom_state dom_info_state (enum cdi_direction); 942extern void set_dom_info_availability (enum cdi_direction, enum dom_state); 943extern bool dom_info_available_p (enum cdi_direction); 944extern void calculate_dominance_info (enum cdi_direction); 945extern void free_dominance_info (enum cdi_direction); 946extern basic_block nearest_common_dominator (enum cdi_direction, 947 basic_block, basic_block); 948extern basic_block nearest_common_dominator_for_set (enum cdi_direction, 949 bitmap); 950extern void set_immediate_dominator (enum cdi_direction, basic_block, 951 basic_block); 952extern basic_block get_immediate_dominator (enum cdi_direction, basic_block); 953extern bool dominated_by_p (enum cdi_direction, const_basic_block, const_basic_block); 954extern VEC (basic_block, heap) *get_dominated_by (enum cdi_direction, basic_block); 955extern VEC (basic_block, heap) *get_dominated_by_region (enum cdi_direction, 956 basic_block *, 957 unsigned); 958extern void add_to_dominance_info (enum cdi_direction, basic_block); 959extern void delete_from_dominance_info (enum cdi_direction, basic_block); 960basic_block recompute_dominator (enum cdi_direction, basic_block); 961extern void redirect_immediate_dominators (enum cdi_direction, basic_block, 962 basic_block); 963extern void iterate_fix_dominators (enum cdi_direction, 964 VEC (basic_block, heap) *, bool); 965extern void verify_dominators (enum cdi_direction); 966extern basic_block first_dom_son (enum cdi_direction, basic_block); 967extern basic_block next_dom_son (enum cdi_direction, basic_block); 968unsigned bb_dom_dfs_in (enum cdi_direction, basic_block); 969unsigned bb_dom_dfs_out (enum cdi_direction, basic_block); 970 971extern edge try_redirect_by_replacing_jump (edge, basic_block, bool); 972extern void break_superblocks (void); 973extern void relink_block_chain (bool); 974extern void check_bb_profile (basic_block, FILE *); 975extern void update_bb_profile_for_threading (basic_block, int, gcov_type, edge); 976extern void init_rtl_bb_info (basic_block); 977 978extern void initialize_original_copy_tables (void); 979extern void free_original_copy_tables (void); 980extern void set_bb_original (basic_block, basic_block); 981extern basic_block get_bb_original (basic_block); 982extern void set_bb_copy (basic_block, basic_block); 983extern basic_block get_bb_copy (basic_block); 984void set_loop_copy (struct loop *, struct loop *); 985struct loop *get_loop_copy (struct loop *); 986 987 988extern rtx insert_insn_end_bb_new (rtx, basic_block); 989 990#include "cfghooks.h" 991 992/* Return true when one of the predecessor edges of BB is marked with EDGE_EH. */ 993static inline bool 994bb_has_eh_pred (basic_block bb) 995{ 996 edge e; 997 edge_iterator ei; 998 999 FOR_EACH_EDGE (e, ei, bb->preds) 1000 { 1001 if (e->flags & EDGE_EH) 1002 return true; 1003 } 1004 return false; 1005} 1006 1007/* Return true when one of the predecessor edges of BB is marked with EDGE_ABNORMAL. */ 1008static inline bool 1009bb_has_abnormal_pred (basic_block bb) 1010{ 1011 edge e; 1012 edge_iterator ei; 1013 1014 FOR_EACH_EDGE (e, ei, bb->preds) 1015 { 1016 if (e->flags & EDGE_ABNORMAL) 1017 return true; 1018 } 1019 return false; 1020} 1021 1022/* In cfgloopmanip.c. */ 1023extern edge mfb_kj_edge; 1024extern bool mfb_keep_just (edge); 1025 1026/* In cfgexpand.c. */ 1027extern void rtl_profile_for_bb (basic_block); 1028extern void rtl_profile_for_edge (edge); 1029extern void default_rtl_profile (void); 1030 1031#endif /* GCC_BASIC_BLOCK_H */ 1032