118334Speter/* Define control and data flow tables, and regsets. 2169689Skan Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005 390075Sobrien Free Software Foundation, Inc. 418334Speter 590075SobrienThis file is part of GCC. 618334Speter 790075SobrienGCC is free software; you can redistribute it and/or modify it under 890075Sobrienthe terms of the GNU General Public License as published by the Free 990075SobrienSoftware Foundation; either version 2, or (at your option) any later 1090075Sobrienversion. 1118334Speter 1290075SobrienGCC is distributed in the hope that it will be useful, but WITHOUT ANY 1390075SobrienWARRANTY; without even the implied warranty of MERCHANTABILITY or 1490075SobrienFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1590075Sobrienfor more details. 1618334Speter 1718334SpeterYou should have received a copy of the GNU General Public License 1890075Sobrienalong with GCC; see the file COPYING. If not, write to the Free 19169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 20169689Skan02110-1301, USA. */ 2118334Speter 2290075Sobrien#ifndef GCC_BASIC_BLOCK_H 2390075Sobrien#define GCC_BASIC_BLOCK_H 2418334Speter 2550397Sobrien#include "bitmap.h" 2652284Sobrien#include "sbitmap.h" 2752284Sobrien#include "varray.h" 2890075Sobrien#include "partition.h" 29117395Skan#include "hard-reg-set.h" 30169689Skan#include "predict.h" 31169689Skan#include "vec.h" 32169689Skan#include "function.h" 3318334Speter 3490075Sobrien/* Head of register set linked list. */ 3590075Sobrientypedef bitmap_head regset_head; 36169689Skan 3790075Sobrien/* A pointer to a regset_head. */ 3890075Sobrientypedef bitmap regset; 3918334Speter 40169689Skan/* Allocate a register set with oballoc. */ 41169689Skan#define ALLOC_REG_SET(OBSTACK) BITMAP_ALLOC (OBSTACK) 42169689Skan 43169689Skan/* Do any cleanup needed on a regset when it is no longer used. */ 44169689Skan#define FREE_REG_SET(REGSET) BITMAP_FREE (REGSET) 45169689Skan 4690075Sobrien/* Initialize a new regset. */ 47169689Skan#define INIT_REG_SET(HEAD) bitmap_initialize (HEAD, ®_obstack) 4890075Sobrien 4950397Sobrien/* Clear a register set by freeing up the linked list. */ 5050397Sobrien#define CLEAR_REG_SET(HEAD) bitmap_clear (HEAD) 5118334Speter 5250397Sobrien/* Copy a register set to another register set. */ 5350397Sobrien#define COPY_REG_SET(TO, FROM) bitmap_copy (TO, FROM) 5418334Speter 5590075Sobrien/* Compare two register sets. */ 5690075Sobrien#define REG_SET_EQUAL_P(A, B) bitmap_equal_p (A, B) 5790075Sobrien 5850397Sobrien/* `and' a register set with a second register set. */ 59169689Skan#define AND_REG_SET(TO, FROM) bitmap_and_into (TO, FROM) 6018334Speter 6150397Sobrien/* `and' the complement of a register set with a register set. */ 62169689Skan#define AND_COMPL_REG_SET(TO, FROM) bitmap_and_compl_into (TO, FROM) 6318334Speter 6450397Sobrien/* Inclusive or a register set with a second register set. */ 65169689Skan#define IOR_REG_SET(TO, FROM) bitmap_ior_into (TO, FROM) 6618334Speter 6790075Sobrien/* Exclusive or a register set with a second register set. */ 68169689Skan#define XOR_REG_SET(TO, FROM) bitmap_xor_into (TO, FROM) 6990075Sobrien 7050397Sobrien/* Or into TO the register set FROM1 `and'ed with the complement of FROM2. */ 7150397Sobrien#define IOR_AND_COMPL_REG_SET(TO, FROM1, FROM2) \ 72169689Skan bitmap_ior_and_compl_into (TO, FROM1, FROM2) 7318334Speter 7450397Sobrien/* Clear a single register in a register set. */ 7550397Sobrien#define CLEAR_REGNO_REG_SET(HEAD, REG) bitmap_clear_bit (HEAD, REG) 7650397Sobrien 7750397Sobrien/* Set a single register in a register set. */ 7850397Sobrien#define SET_REGNO_REG_SET(HEAD, REG) bitmap_set_bit (HEAD, REG) 7950397Sobrien 8050397Sobrien/* Return true if a register is set in a register set. */ 8150397Sobrien#define REGNO_REG_SET_P(TO, REG) bitmap_bit_p (TO, REG) 8250397Sobrien 8350397Sobrien/* Copy the hard registers in a register set to the hard register set. */ 84132718Skanextern void reg_set_to_hard_reg_set (HARD_REG_SET *, bitmap); 8550397Sobrien#define REG_SET_TO_HARD_REG_SET(TO, FROM) \ 8650397Sobriendo { \ 8750397Sobrien CLEAR_HARD_REG_SET (TO); \ 8890075Sobrien reg_set_to_hard_reg_set (&TO, FROM); \ 8950397Sobrien} while (0) 9050397Sobrien 91169689Skantypedef bitmap_iterator reg_set_iterator; 92169689Skan 9350397Sobrien/* Loop over all registers in REGSET, starting with MIN, setting REGNUM to the 9490075Sobrien register number and executing CODE for all registers that are set. */ 95169689Skan#define EXECUTE_IF_SET_IN_REG_SET(REGSET, MIN, REGNUM, RSI) \ 96169689Skan EXECUTE_IF_SET_IN_BITMAP (REGSET, MIN, REGNUM, RSI) 9750397Sobrien 9850397Sobrien/* Loop over all registers in REGSET1 and REGSET2, starting with MIN, setting 9950397Sobrien REGNUM to the register number and executing CODE for all registers that are 10090075Sobrien set in the first regset and not set in the second. */ 101169689Skan#define EXECUTE_IF_AND_COMPL_IN_REG_SET(REGSET1, REGSET2, MIN, REGNUM, RSI) \ 102169689Skan EXECUTE_IF_AND_COMPL_IN_BITMAP (REGSET1, REGSET2, MIN, REGNUM, RSI) 10350397Sobrien 10450397Sobrien/* Loop over all registers in REGSET1 and REGSET2, starting with MIN, setting 10550397Sobrien REGNUM to the register number and executing CODE for all registers that are 10690075Sobrien set in both regsets. */ 107169689Skan#define EXECUTE_IF_AND_IN_REG_SET(REGSET1, REGSET2, MIN, REGNUM, RSI) \ 108169689Skan EXECUTE_IF_AND_IN_BITMAP (REGSET1, REGSET2, MIN, REGNUM, RSI) \ 10950397Sobrien 110132718Skan/* Type we use to hold basic block counters. Should be at least 111132718Skan 64bit. Although a counter cannot be negative, we use a signed 112132718Skan type, because erroneous negative counts can be generated when the 113132718Skan flow graph is manipulated by various optimizations. A signed type 114132718Skan makes those easy to detect. */ 11590075Sobrientypedef HOST_WIDEST_INT gcov_type; 11690075Sobrien 11752284Sobrien/* Control flow edge information. */ 118169689Skanstruct edge_def GTY(()) 119169689Skan{ 12052284Sobrien /* The two blocks at the ends of the edge. */ 121169689Skan struct basic_block_def *src; 122169689Skan struct basic_block_def *dest; 12318334Speter 12452284Sobrien /* Instructions queued on the edge. */ 125169689Skan union edge_def_insns { 126169689Skan rtx GTY ((tag ("0"))) r; 127169689Skan tree GTY ((tag ("1"))) t; 128169689Skan } GTY ((desc ("ir_type ()"))) insns; 12918334Speter 13052284Sobrien /* Auxiliary info specific to a pass. */ 131169689Skan PTR GTY ((skip (""))) aux; 13218334Speter 133169689Skan /* Location of any goto implicit in the edge, during tree-ssa. */ 134169689Skan source_locus goto_locus; 135169689Skan 13652284Sobrien int flags; /* see EDGE_* below */ 13752284Sobrien int probability; /* biased by REG_BR_PROB_BASE */ 13890075Sobrien gcov_type count; /* Expected number of executions calculated 13990075Sobrien in profile.c */ 14018334Speter 141169689Skan /* The index number corresponding to this edge in the edge vector 142169689Skan dest->preds. */ 143169689Skan unsigned int dest_idx; 144169689Skan}; 145169689Skan 146169689Skantypedef struct edge_def *edge; 147169689SkanDEF_VEC_P(edge); 148169689SkanDEF_VEC_ALLOC_P(edge,gc); 149169689Skan 150117395Skan#define EDGE_FALLTHRU 1 /* 'Straight line' flow */ 151117395Skan#define EDGE_ABNORMAL 2 /* Strange flow, like computed 152117395Skan label, or eh */ 153117395Skan#define EDGE_ABNORMAL_CALL 4 /* Call with abnormal exit 154117395Skan like an exception, or sibcall */ 155117395Skan#define EDGE_EH 8 /* Exception throw */ 156117395Skan#define EDGE_FAKE 16 /* Not a real edge (profile.c) */ 157117395Skan#define EDGE_DFS_BACK 32 /* A backwards edge */ 158117395Skan#define EDGE_CAN_FALLTHRU 64 /* Candidate for straight line 159117395Skan flow. */ 160132718Skan#define EDGE_IRREDUCIBLE_LOOP 128 /* Part of irreducible loop. */ 161132718Skan#define EDGE_SIBCALL 256 /* Edge from sibcall to exit. */ 162132718Skan#define EDGE_LOOP_EXIT 512 /* Exit of a loop. */ 163169689Skan#define EDGE_TRUE_VALUE 1024 /* Edge taken when controlling 164169689Skan predicate is nonzero. */ 165169689Skan#define EDGE_FALSE_VALUE 2048 /* Edge taken when controlling 166169689Skan predicate is zero. */ 167169689Skan#define EDGE_EXECUTABLE 4096 /* Edge is executable. Only 168169689Skan valid during SSA-CCP. */ 169169689Skan#define EDGE_CROSSING 8192 /* Edge crosses between hot 170169689Skan and cold sections, when we 171169689Skan do partitioning. */ 172169689Skan#define EDGE_ALL_FLAGS 16383 17318334Speter 17490075Sobrien#define EDGE_COMPLEX (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_EH) 17550397Sobrien 176132718Skan/* Counter summary from the last set of coverage counts read by 177132718Skan profile.c. */ 178132718Skanextern const struct gcov_ctr_summary *profile_info; 17990075Sobrien 180132718Skan/* Declared in cfgloop.h. */ 181132718Skanstruct loop; 182132718Skanstruct loops; 183132718Skan 184169689Skan/* Declared in tree-flow.h. */ 185169689Skanstruct edge_prediction; 186169689Skanstruct rtl_bb_info; 187169689Skan 18890075Sobrien/* A basic block is a sequence of instructions with only entry and 18990075Sobrien only one exit. If any one of the instructions are executed, they 19090075Sobrien will all be executed, and in sequence from first to last. 19190075Sobrien 19290075Sobrien There may be COND_EXEC instructions in the basic block. The 19390075Sobrien COND_EXEC *instructions* will be executed -- but if the condition 19490075Sobrien is false the conditionally executed *expressions* will of course 19590075Sobrien not be executed. We don't consider the conditionally executed 19690075Sobrien expression (which might have side-effects) to be in a separate 19790075Sobrien basic block because the program counter will always be at the same 19890075Sobrien location after the COND_EXEC instruction, regardless of whether the 19990075Sobrien condition is true or not. 20090075Sobrien 20190075Sobrien Basic blocks need not start with a label nor end with a jump insn. 20290075Sobrien For example, a previous basic block may just "conditionally fall" 20390075Sobrien into the succeeding basic block, and the last basic block need not 20490075Sobrien end with a jump insn. Block 0 is a descendant of the entry block. 20590075Sobrien 20690075Sobrien A basic block beginning with two labels cannot have notes between 20790075Sobrien the labels. 20890075Sobrien 20990075Sobrien Data for jump tables are stored in jump_insns that occur in no 21090075Sobrien basic block even though these insns can follow or precede insns in 21190075Sobrien basic blocks. */ 21290075Sobrien 21352284Sobrien/* Basic block information indexed by block number. */ 214169689Skanstruct basic_block_def GTY((chain_next ("%h.next_bb"), chain_prev ("%h.prev_bb"))) 215169689Skan{ 216169689Skan /* Pointers to the first and last trees of the block. */ 217169689Skan tree stmt_list; 21850397Sobrien 21952284Sobrien /* The edges into and out of the block. */ 220169689Skan VEC(edge,gc) *preds; 221169689Skan VEC(edge,gc) *succs; 22218334Speter 223169689Skan /* Auxiliary info specific to a pass. */ 224169689Skan PTR GTY ((skip (""))) aux; 22590075Sobrien 226169689Skan /* Innermost loop containing the block. */ 227169689Skan struct loop * GTY ((skip (""))) loop_father; 22890075Sobrien 229169689Skan /* The dominance and postdominance information node. */ 230169689Skan struct et_node * GTY ((skip (""))) dom[2]; 23118334Speter 232117395Skan /* Previous and next blocks in the chain. */ 233169689Skan struct basic_block_def *prev_bb; 234169689Skan struct basic_block_def *next_bb; 235117395Skan 236169689Skan union basic_block_il_dependent { 237169689Skan struct rtl_bb_info * GTY ((tag ("1"))) rtl; 238169689Skan } GTY ((desc ("((%1.flags & BB_RTL) != 0)"))) il; 23990075Sobrien 240169689Skan /* Chain of PHI nodes for this block. */ 241169689Skan tree phi_nodes; 242117395Skan 243169689Skan /* A list of predictions. */ 244169689Skan struct edge_prediction *predictions; 245132718Skan 24690075Sobrien /* Expected number of executions: calculated in profile.c. */ 24790075Sobrien gcov_type count; 24890075Sobrien 249169689Skan /* The index of this block. */ 250169689Skan int index; 251169689Skan 252169689Skan /* The loop depth of this block. */ 253169689Skan int loop_depth; 254169689Skan 25590075Sobrien /* Expected frequency. Normalized to be in range 0 to BB_FREQ_MAX. */ 25690075Sobrien int frequency; 25790075Sobrien 25890075Sobrien /* Various flags. See BB_* below. */ 25990075Sobrien int flags; 260169689Skan}; 261132718Skan 262169689Skanstruct rtl_bb_info GTY(()) 263169689Skan{ 264169689Skan /* The first and last insns of the block. */ 265169689Skan rtx head_; 266169689Skan rtx end_; 26752284Sobrien 268169689Skan /* The registers that are live on entry to this block. */ 269169689Skan bitmap GTY ((skip (""))) global_live_at_start; 270169689Skan 271169689Skan /* The registers that are live on exit from this block. */ 272169689Skan bitmap GTY ((skip (""))) global_live_at_end; 273169689Skan 274169689Skan /* In CFGlayout mode points to insn notes/jumptables to be placed just before 275169689Skan and after the block. */ 276169689Skan rtx header; 277169689Skan rtx footer; 278169689Skan 279169689Skan /* This field is used by the bb-reorder and tracer passes. */ 280169689Skan int visited; 281169689Skan}; 282169689Skan 283169689Skantypedef struct basic_block_def *basic_block; 284169689Skan 285169689SkanDEF_VEC_P(basic_block); 286169689SkanDEF_VEC_ALLOC_P(basic_block,gc); 287169689SkanDEF_VEC_ALLOC_P(basic_block,heap); 288169689Skan 28990075Sobrien#define BB_FREQ_MAX 10000 29090075Sobrien 291169689Skan/* Masks for basic_block.flags. 29290075Sobrien 293169689Skan BB_HOT_PARTITION and BB_COLD_PARTITION should be preserved throughout 294169689Skan the compilation, so they are never cleared. 29552284Sobrien 296169689Skan All other flags may be cleared by clear_bb_flags(). It is generally 297169689Skan a bad idea to rely on any flags being up-to-date. */ 29852284Sobrien 299169689Skanenum bb_flags 300169689Skan{ 301117395Skan 302169689Skan /* Set if insns in BB have are modified. Used for updating liveness info. */ 303169689Skan BB_DIRTY = 1, 304117395Skan 305169689Skan /* Only set on blocks that have just been created by create_bb. */ 306169689Skan BB_NEW = 2, 30790075Sobrien 308169689Skan /* Set by find_unreachable_blocks. Do not rely on this being set in any 309169689Skan pass. */ 310169689Skan BB_REACHABLE = 4, 31190075Sobrien 312169689Skan /* Set for blocks in an irreducible loop by loop analysis. */ 313169689Skan BB_IRREDUCIBLE_LOOP = 8, 31452284Sobrien 315169689Skan /* Set on blocks that may actually not be single-entry single-exit block. */ 316169689Skan BB_SUPERBLOCK = 16, 31752284Sobrien 318169689Skan /* Set on basic blocks that the scheduler should not touch. This is used 319169689Skan by SMS to prevent other schedulers from messing with the loop schedule. */ 320169689Skan BB_DISABLE_SCHEDULE = 32, 32152284Sobrien 322169689Skan /* Set on blocks that should be put in a hot section. */ 323169689Skan BB_HOT_PARTITION = 64, 324169689Skan 325169689Skan /* Set on blocks that should be put in a cold section. */ 326169689Skan BB_COLD_PARTITION = 128, 327169689Skan 328169689Skan /* Set on block that was duplicated. */ 329169689Skan BB_DUPLICATED = 256, 330169689Skan 331169689Skan /* Set on blocks that are in RTL format. */ 332169689Skan BB_RTL = 1024, 333169689Skan 334169689Skan /* Set on blocks that are forwarder blocks. 335169689Skan Only used in cfgcleanup.c. */ 336169689Skan BB_FORWARDER_BLOCK = 2048, 337169689Skan 338169689Skan /* Set on blocks that cannot be threaded through. 339169689Skan Only used in cfgcleanup.c. */ 340169689Skan BB_NONTHREADABLE_BLOCK = 4096 341169689Skan}; 342169689Skan 343169689Skan/* Dummy flag for convenience in the hot/cold partitioning code. */ 344169689Skan#define BB_UNPARTITIONED 0 345169689Skan 346169689Skan/* Partitions, to be used when partitioning hot and cold basic blocks into 347169689Skan separate sections. */ 348169689Skan#define BB_PARTITION(bb) ((bb)->flags & (BB_HOT_PARTITION|BB_COLD_PARTITION)) 349169689Skan#define BB_SET_PARTITION(bb, part) do { \ 350169689Skan basic_block bb_ = (bb); \ 351169689Skan bb_->flags = ((bb_->flags & ~(BB_HOT_PARTITION|BB_COLD_PARTITION)) \ 352169689Skan | (part)); \ 353169689Skan} while (0) 354169689Skan 355169689Skan#define BB_COPY_PARTITION(dstbb, srcbb) \ 356169689Skan BB_SET_PARTITION (dstbb, BB_PARTITION (srcbb)) 357169689Skan 358169689Skan/* A structure to group all the per-function control flow graph data. 359169689Skan The x_* prefixing is necessary because otherwise references to the 360169689Skan fields of this struct are interpreted as the defines for backward 361169689Skan source compatibility following the definition of this struct. */ 362169689Skanstruct control_flow_graph GTY(()) 363169689Skan{ 364169689Skan /* Block pointers for the exit and entry of a function. 365169689Skan These are always the head and tail of the basic block list. */ 366169689Skan basic_block x_entry_block_ptr; 367169689Skan basic_block x_exit_block_ptr; 368169689Skan 369169689Skan /* Index by basic block number, get basic block struct info. */ 370169689Skan VEC(basic_block,gc) *x_basic_block_info; 371169689Skan 372169689Skan /* Number of basic blocks in this flow graph. */ 373169689Skan int x_n_basic_blocks; 374169689Skan 375169689Skan /* Number of edges in this flow graph. */ 376169689Skan int x_n_edges; 377169689Skan 378169689Skan /* The first free basic block number. */ 379169689Skan int x_last_basic_block; 380169689Skan 381169689Skan /* Mapping of labels to their associated blocks. At present 382169689Skan only used for the tree CFG. */ 383169689Skan VEC(basic_block,gc) *x_label_to_block_map; 384169689Skan 385169689Skan enum profile_status { 386169689Skan PROFILE_ABSENT, 387169689Skan PROFILE_GUESSED, 388169689Skan PROFILE_READ 389169689Skan } x_profile_status; 390169689Skan}; 391169689Skan 392169689Skan/* Defines for accessing the fields of the CFG structure for function FN. */ 393169689Skan#define ENTRY_BLOCK_PTR_FOR_FUNCTION(FN) ((FN)->cfg->x_entry_block_ptr) 394169689Skan#define EXIT_BLOCK_PTR_FOR_FUNCTION(FN) ((FN)->cfg->x_exit_block_ptr) 395169689Skan#define basic_block_info_for_function(FN) ((FN)->cfg->x_basic_block_info) 396169689Skan#define n_basic_blocks_for_function(FN) ((FN)->cfg->x_n_basic_blocks) 397169689Skan#define n_edges_for_function(FN) ((FN)->cfg->x_n_edges) 398169689Skan#define last_basic_block_for_function(FN) ((FN)->cfg->x_last_basic_block) 399169689Skan#define label_to_block_map_for_function(FN) ((FN)->cfg->x_label_to_block_map) 400169689Skan 401169689Skan#define BASIC_BLOCK_FOR_FUNCTION(FN,N) \ 402169689Skan (VEC_index (basic_block, basic_block_info_for_function(FN), (N))) 403169689Skan 404169689Skan/* Defines for textual backward source compatibility. */ 405169689Skan#define ENTRY_BLOCK_PTR (cfun->cfg->x_entry_block_ptr) 406169689Skan#define EXIT_BLOCK_PTR (cfun->cfg->x_exit_block_ptr) 407169689Skan#define basic_block_info (cfun->cfg->x_basic_block_info) 408169689Skan#define n_basic_blocks (cfun->cfg->x_n_basic_blocks) 409169689Skan#define n_edges (cfun->cfg->x_n_edges) 410169689Skan#define last_basic_block (cfun->cfg->x_last_basic_block) 411169689Skan#define label_to_block_map (cfun->cfg->x_label_to_block_map) 412169689Skan#define profile_status (cfun->cfg->x_profile_status) 413169689Skan 414169689Skan#define BASIC_BLOCK(N) (VEC_index (basic_block, basic_block_info, (N))) 415169689Skan#define SET_BASIC_BLOCK(N,BB) (VEC_replace (basic_block, basic_block_info, (N), (BB))) 416169689Skan 417117395Skan/* For iterating over basic blocks. */ 418117395Skan#define FOR_BB_BETWEEN(BB, FROM, TO, DIR) \ 419117395Skan for (BB = FROM; BB != TO; BB = BB->DIR) 420117395Skan 421169689Skan#define FOR_EACH_BB_FN(BB, FN) \ 422169689Skan FOR_BB_BETWEEN (BB, (FN)->cfg->x_entry_block_ptr->next_bb, (FN)->cfg->x_exit_block_ptr, next_bb) 423117395Skan 424169689Skan#define FOR_EACH_BB(BB) FOR_EACH_BB_FN (BB, cfun) 425117395Skan 426169689Skan#define FOR_EACH_BB_REVERSE_FN(BB, FN) \ 427169689Skan FOR_BB_BETWEEN (BB, (FN)->cfg->x_exit_block_ptr->prev_bb, (FN)->cfg->x_entry_block_ptr, prev_bb) 428169689Skan 429169689Skan#define FOR_EACH_BB_REVERSE(BB) FOR_EACH_BB_REVERSE_FN(BB, cfun) 430169689Skan 431169689Skan/* For iterating over insns in basic block. */ 432169689Skan#define FOR_BB_INSNS(BB, INSN) \ 433169689Skan for ((INSN) = BB_HEAD (BB); \ 434169689Skan (INSN) && (INSN) != NEXT_INSN (BB_END (BB)); \ 435169689Skan (INSN) = NEXT_INSN (INSN)) 436169689Skan 437169689Skan#define FOR_BB_INSNS_REVERSE(BB, INSN) \ 438169689Skan for ((INSN) = BB_END (BB); \ 439169689Skan (INSN) && (INSN) != PREV_INSN (BB_HEAD (BB)); \ 440169689Skan (INSN) = PREV_INSN (INSN)) 441169689Skan 442117395Skan/* Cycles through _all_ basic blocks, even the fake ones (entry and 443117395Skan exit block). */ 444117395Skan 445117395Skan#define FOR_ALL_BB(BB) \ 446117395Skan for (BB = ENTRY_BLOCK_PTR; BB; BB = BB->next_bb) 447117395Skan 448169689Skan#define FOR_ALL_BB_FN(BB, FN) \ 449169689Skan for (BB = ENTRY_BLOCK_PTR_FOR_FUNCTION (FN); BB; BB = BB->next_bb) 45050397Sobrien 451169689Skanextern bitmap_obstack reg_obstack; 45250397Sobrien 45318334Speter/* Indexed by n, gives number of basic block that (REG n) is used in. 45418334Speter If the value is REG_BLOCK_GLOBAL (-2), 45518334Speter it means (REG n) is used in more than one basic block. 45618334Speter REG_BLOCK_UNKNOWN (-1) means it hasn't been seen yet so we don't know. 45718334Speter This information remains valid for the rest of the compilation 45818334Speter of the current function; it is used to control register allocation. */ 45918334Speter 46018334Speter#define REG_BLOCK_UNKNOWN -1 46118334Speter#define REG_BLOCK_GLOBAL -2 46250397Sobrien 463169689Skan#define REG_BASIC_BLOCK(N) \ 464169689Skan (VEC_index (reg_info_p, reg_n_info, N)->basic_block) 46550397Sobrien 46650397Sobrien/* Stuff for recording basic block info. */ 46750397Sobrien 468169689Skan#define BB_HEAD(B) (B)->il.rtl->head_ 469169689Skan#define BB_END(B) (B)->il.rtl->end_ 47050397Sobrien 47150397Sobrien/* Special block numbers [markers] for entry and exit. */ 472169689Skan#define ENTRY_BLOCK (0) 473169689Skan#define EXIT_BLOCK (1) 47450397Sobrien 475169689Skan/* The two blocks that are always in the cfg. */ 476169689Skan#define NUM_FIXED_BLOCKS (2) 47790075Sobrien 47852284Sobrien 47952284Sobrien#define BLOCK_NUM(INSN) (BLOCK_FOR_INSN (INSN)->index + 0) 480117395Skan#define set_block_for_insn(INSN, BB) (BLOCK_FOR_INSN (INSN) = BB) 48150397Sobrien 482132718Skanextern void compute_bb_for_insn (void); 483169689Skanextern unsigned int free_bb_for_insn (void); 484132718Skanextern void update_bb_for_insn (basic_block); 48550397Sobrien 486169689Skanextern void free_basic_block_vars (void); 48750397Sobrien 488132718Skanextern void insert_insn_on_edge (rtx, edge); 489117395Skan 490132718Skanextern void commit_edge_insertions (void); 491132718Skanextern void commit_edge_insertions_watch_calls (void); 492117395Skan 493132718Skanextern void remove_fake_edges (void); 494169689Skanextern void remove_fake_exit_edges (void); 495132718Skanextern void add_noreturn_fake_exit_edges (void); 496132718Skanextern void connect_infinite_loops_to_exit (void); 497132718Skanextern edge unchecked_make_edge (basic_block, basic_block, int); 498169689Skanextern edge cached_make_edge (sbitmap, basic_block, basic_block, int); 499132718Skanextern edge make_edge (basic_block, basic_block, int); 500132718Skanextern edge make_single_succ_edge (basic_block, basic_block, int); 501132718Skanextern void remove_edge (edge); 502132718Skanextern void redirect_edge_succ (edge, basic_block); 503132718Skanextern edge redirect_edge_succ_nodup (edge, basic_block); 504132718Skanextern void redirect_edge_pred (edge, basic_block); 505132718Skanextern basic_block create_basic_block_structure (rtx, rtx, rtx, basic_block); 506132718Skanextern void clear_bb_flags (void); 507169689Skanextern int post_order_compute (int *, bool); 508169689Skanextern int pre_and_rev_post_order_compute (int *, int *, bool); 509132718Skanextern int dfs_enumerate_from (basic_block, int, 510132718Skan bool (*)(basic_block, void *), 511132718Skan basic_block *, int, void *); 512169689Skanextern void compute_dominance_frontiers (bitmap *); 513169689Skanextern void dump_bb_info (basic_block, bool, bool, int, const char *, FILE *); 514132718Skanextern void dump_edge_info (FILE *, edge, int); 515169689Skanextern void brief_dump_cfg (FILE *); 516132718Skanextern void clear_edges (void); 517132718Skanextern rtx first_insn_after_basic_block_note (basic_block); 518169689Skanextern void scale_bbs_frequencies_int (basic_block *, int, int, int); 519169689Skanextern void scale_bbs_frequencies_gcov_type (basic_block *, int, gcov_type, 520169689Skan gcov_type); 52150397Sobrien 522117395Skan/* Structure to group all of the information to process IF-THEN and 523117395Skan IF-THEN-ELSE blocks for the conditional execution support. This 524117395Skan needs to be in a public file in case the IFCVT macros call 525117395Skan functions passing the ce_if_block data structure. */ 526117395Skan 527117395Skantypedef struct ce_if_block 528117395Skan{ 529117395Skan basic_block test_bb; /* First test block. */ 530117395Skan basic_block then_bb; /* THEN block. */ 531117395Skan basic_block else_bb; /* ELSE block or NULL. */ 532117395Skan basic_block join_bb; /* Join THEN/ELSE blocks. */ 533117395Skan basic_block last_test_bb; /* Last bb to hold && or || tests. */ 534117395Skan int num_multiple_test_blocks; /* # of && and || basic blocks. */ 535117395Skan int num_and_and_blocks; /* # of && blocks. */ 536117395Skan int num_or_or_blocks; /* # of || blocks. */ 537117395Skan int num_multiple_test_insns; /* # of insns in && and || blocks. */ 538117395Skan int and_and_p; /* Complex test is &&. */ 539117395Skan int num_then_insns; /* # of insns in THEN block. */ 540117395Skan int num_else_insns; /* # of insns in ELSE block. */ 541117395Skan int pass; /* Pass number. */ 542117395Skan 543117395Skan#ifdef IFCVT_EXTRA_FIELDS 544117395Skan IFCVT_EXTRA_FIELDS /* Any machine dependent fields. */ 545117395Skan#endif 546117395Skan 547117395Skan} ce_if_block_t; 548117395Skan 54990075Sobrien/* This structure maintains an edge list vector. */ 55090075Sobrienstruct edge_list 55190075Sobrien{ 55290075Sobrien int num_blocks; 55390075Sobrien int num_edges; 55490075Sobrien edge *index_to_edge; 55590075Sobrien}; 55690075Sobrien 557169689Skan/* The base value for branch probability notes and edge probabilities. */ 558169689Skan#define REG_BR_PROB_BASE 10000 559169689Skan 56090075Sobrien/* This is the value which indicates no edge is present. */ 56190075Sobrien#define EDGE_INDEX_NO_EDGE -1 56290075Sobrien 56390075Sobrien/* EDGE_INDEX returns an integer index for an edge, or EDGE_INDEX_NO_EDGE 56490075Sobrien if there is no edge between the 2 basic blocks. */ 56590075Sobrien#define EDGE_INDEX(el, pred, succ) (find_edge_index ((el), (pred), (succ))) 56690075Sobrien 56790075Sobrien/* INDEX_EDGE_PRED_BB and INDEX_EDGE_SUCC_BB return a pointer to the basic 56890075Sobrien block which is either the pred or succ end of the indexed edge. */ 56990075Sobrien#define INDEX_EDGE_PRED_BB(el, index) ((el)->index_to_edge[(index)]->src) 57090075Sobrien#define INDEX_EDGE_SUCC_BB(el, index) ((el)->index_to_edge[(index)]->dest) 57190075Sobrien 57290075Sobrien/* INDEX_EDGE returns a pointer to the edge. */ 57390075Sobrien#define INDEX_EDGE(el, index) ((el)->index_to_edge[(index)]) 57490075Sobrien 57590075Sobrien/* Number of edges in the compressed edge list. */ 57690075Sobrien#define NUM_EDGES(el) ((el)->num_edges) 57790075Sobrien 57890075Sobrien/* BB is assumed to contain conditional jump. Return the fallthru edge. */ 579169689Skan#define FALLTHRU_EDGE(bb) (EDGE_SUCC ((bb), 0)->flags & EDGE_FALLTHRU \ 580169689Skan ? EDGE_SUCC ((bb), 0) : EDGE_SUCC ((bb), 1)) 58190075Sobrien 58290075Sobrien/* BB is assumed to contain conditional jump. Return the branch edge. */ 583169689Skan#define BRANCH_EDGE(bb) (EDGE_SUCC ((bb), 0)->flags & EDGE_FALLTHRU \ 584169689Skan ? EDGE_SUCC ((bb), 1) : EDGE_SUCC ((bb), 0)) 58590075Sobrien 58690075Sobrien/* Return expected execution frequency of the edge E. */ 58790075Sobrien#define EDGE_FREQUENCY(e) (((e)->src->frequency \ 58890075Sobrien * (e)->probability \ 58990075Sobrien + REG_BR_PROB_BASE / 2) \ 59090075Sobrien / REG_BR_PROB_BASE) 59190075Sobrien 59290075Sobrien/* Return nonzero if edge is critical. */ 593169689Skan#define EDGE_CRITICAL_P(e) (EDGE_COUNT ((e)->src->succs) >= 2 \ 594169689Skan && EDGE_COUNT ((e)->dest->preds) >= 2) 59590075Sobrien 596169689Skan#define EDGE_COUNT(ev) VEC_length (edge, (ev)) 597169689Skan#define EDGE_I(ev,i) VEC_index (edge, (ev), (i)) 598169689Skan#define EDGE_PRED(bb,i) VEC_index (edge, (bb)->preds, (i)) 599169689Skan#define EDGE_SUCC(bb,i) VEC_index (edge, (bb)->succs, (i)) 600169689Skan 601169689Skan/* Returns true if BB has precisely one successor. */ 602169689Skan 603169689Skanstatic inline bool 604169689Skansingle_succ_p (basic_block bb) 605169689Skan{ 606169689Skan return EDGE_COUNT (bb->succs) == 1; 607169689Skan} 608169689Skan 609169689Skan/* Returns true if BB has precisely one predecessor. */ 610169689Skan 611169689Skanstatic inline bool 612169689Skansingle_pred_p (basic_block bb) 613169689Skan{ 614169689Skan return EDGE_COUNT (bb->preds) == 1; 615169689Skan} 616169689Skan 617169689Skan/* Returns the single successor edge of basic block BB. Aborts if 618169689Skan BB does not have exactly one successor. */ 619169689Skan 620169689Skanstatic inline edge 621169689Skansingle_succ_edge (basic_block bb) 622169689Skan{ 623169689Skan gcc_assert (single_succ_p (bb)); 624169689Skan return EDGE_SUCC (bb, 0); 625169689Skan} 626169689Skan 627169689Skan/* Returns the single predecessor edge of basic block BB. Aborts 628169689Skan if BB does not have exactly one predecessor. */ 629169689Skan 630169689Skanstatic inline edge 631169689Skansingle_pred_edge (basic_block bb) 632169689Skan{ 633169689Skan gcc_assert (single_pred_p (bb)); 634169689Skan return EDGE_PRED (bb, 0); 635169689Skan} 636169689Skan 637169689Skan/* Returns the single successor block of basic block BB. Aborts 638169689Skan if BB does not have exactly one successor. */ 639169689Skan 640169689Skanstatic inline basic_block 641169689Skansingle_succ (basic_block bb) 642169689Skan{ 643169689Skan return single_succ_edge (bb)->dest; 644169689Skan} 645169689Skan 646169689Skan/* Returns the single predecessor block of basic block BB. Aborts 647169689Skan if BB does not have exactly one predecessor.*/ 648169689Skan 649169689Skanstatic inline basic_block 650169689Skansingle_pred (basic_block bb) 651169689Skan{ 652169689Skan return single_pred_edge (bb)->src; 653169689Skan} 654169689Skan 655169689Skan/* Iterator object for edges. */ 656169689Skan 657169689Skantypedef struct { 658169689Skan unsigned index; 659169689Skan VEC(edge,gc) **container; 660169689Skan} edge_iterator; 661169689Skan 662169689Skanstatic inline VEC(edge,gc) * 663169689Skanei_container (edge_iterator i) 664169689Skan{ 665169689Skan gcc_assert (i.container); 666169689Skan return *i.container; 667169689Skan} 668169689Skan 669169689Skan#define ei_start(iter) ei_start_1 (&(iter)) 670169689Skan#define ei_last(iter) ei_last_1 (&(iter)) 671169689Skan 672169689Skan/* Return an iterator pointing to the start of an edge vector. */ 673169689Skanstatic inline edge_iterator 674169689Skanei_start_1 (VEC(edge,gc) **ev) 675169689Skan{ 676169689Skan edge_iterator i; 677169689Skan 678169689Skan i.index = 0; 679169689Skan i.container = ev; 680169689Skan 681169689Skan return i; 682169689Skan} 683169689Skan 684169689Skan/* Return an iterator pointing to the last element of an edge 685169689Skan vector. */ 686169689Skanstatic inline edge_iterator 687169689Skanei_last_1 (VEC(edge,gc) **ev) 688169689Skan{ 689169689Skan edge_iterator i; 690169689Skan 691169689Skan i.index = EDGE_COUNT (*ev) - 1; 692169689Skan i.container = ev; 693169689Skan 694169689Skan return i; 695169689Skan} 696169689Skan 697169689Skan/* Is the iterator `i' at the end of the sequence? */ 698169689Skanstatic inline bool 699169689Skanei_end_p (edge_iterator i) 700169689Skan{ 701169689Skan return (i.index == EDGE_COUNT (ei_container (i))); 702169689Skan} 703169689Skan 704169689Skan/* Is the iterator `i' at one position before the end of the 705169689Skan sequence? */ 706169689Skanstatic inline bool 707169689Skanei_one_before_end_p (edge_iterator i) 708169689Skan{ 709169689Skan return (i.index + 1 == EDGE_COUNT (ei_container (i))); 710169689Skan} 711169689Skan 712169689Skan/* Advance the iterator to the next element. */ 713169689Skanstatic inline void 714169689Skanei_next (edge_iterator *i) 715169689Skan{ 716169689Skan gcc_assert (i->index < EDGE_COUNT (ei_container (*i))); 717169689Skan i->index++; 718169689Skan} 719169689Skan 720169689Skan/* Move the iterator to the previous element. */ 721169689Skanstatic inline void 722169689Skanei_prev (edge_iterator *i) 723169689Skan{ 724169689Skan gcc_assert (i->index > 0); 725169689Skan i->index--; 726169689Skan} 727169689Skan 728169689Skan/* Return the edge pointed to by the iterator `i'. */ 729169689Skanstatic inline edge 730169689Skanei_edge (edge_iterator i) 731169689Skan{ 732169689Skan return EDGE_I (ei_container (i), i.index); 733169689Skan} 734169689Skan 735169689Skan/* Return an edge pointed to by the iterator. Do it safely so that 736169689Skan NULL is returned when the iterator is pointing at the end of the 737169689Skan sequence. */ 738169689Skanstatic inline edge 739169689Skanei_safe_edge (edge_iterator i) 740169689Skan{ 741169689Skan return !ei_end_p (i) ? ei_edge (i) : NULL; 742169689Skan} 743169689Skan 744169689Skan/* Return 1 if we should continue to iterate. Return 0 otherwise. 745169689Skan *Edge P is set to the next edge if we are to continue to iterate 746169689Skan and NULL otherwise. */ 747169689Skan 748169689Skanstatic inline bool 749169689Skanei_cond (edge_iterator ei, edge *p) 750169689Skan{ 751169689Skan if (!ei_end_p (ei)) 752169689Skan { 753169689Skan *p = ei_edge (ei); 754169689Skan return 1; 755169689Skan } 756169689Skan else 757169689Skan { 758169689Skan *p = NULL; 759169689Skan return 0; 760169689Skan } 761169689Skan} 762169689Skan 763169689Skan/* This macro serves as a convenient way to iterate each edge in a 764169689Skan vector of predecessor or successor edges. It must not be used when 765169689Skan an element might be removed during the traversal, otherwise 766169689Skan elements will be missed. Instead, use a for-loop like that shown 767169689Skan in the following pseudo-code: 768169689Skan 769169689Skan FOR (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ) 770169689Skan { 771169689Skan IF (e != taken_edge) 772169689Skan remove_edge (e); 773169689Skan ELSE 774169689Skan ei_next (&ei); 775169689Skan } 776169689Skan*/ 777169689Skan 778169689Skan#define FOR_EACH_EDGE(EDGE,ITER,EDGE_VEC) \ 779169689Skan for ((ITER) = ei_start ((EDGE_VEC)); \ 780169689Skan ei_cond ((ITER), &(EDGE)); \ 781169689Skan ei_next (&(ITER))) 782169689Skan 783132718Skanstruct edge_list * create_edge_list (void); 784132718Skanvoid free_edge_list (struct edge_list *); 785132718Skanvoid print_edge_list (FILE *, struct edge_list *); 786132718Skanvoid verify_edge_list (FILE *, struct edge_list *); 787132718Skanint find_edge_index (struct edge_list *, basic_block, basic_block); 788169689Skanedge find_edge (basic_block, basic_block); 78990075Sobrien 79090075Sobrien 79190075Sobrienenum update_life_extent 79290075Sobrien{ 79390075Sobrien UPDATE_LIFE_LOCAL = 0, 79490075Sobrien UPDATE_LIFE_GLOBAL = 1, 79590075Sobrien UPDATE_LIFE_GLOBAL_RM_NOTES = 2 79690075Sobrien}; 79790075Sobrien 79890075Sobrien/* Flags for life_analysis and update_life_info. */ 79990075Sobrien 80090075Sobrien#define PROP_DEATH_NOTES 1 /* Create DEAD and UNUSED notes. */ 80190075Sobrien#define PROP_LOG_LINKS 2 /* Create LOG_LINKS. */ 80290075Sobrien#define PROP_REG_INFO 4 /* Update regs_ever_live et al. */ 80390075Sobrien#define PROP_KILL_DEAD_CODE 8 /* Remove dead code. */ 80490075Sobrien#define PROP_SCAN_DEAD_CODE 16 /* Scan for dead code. */ 80590075Sobrien#define PROP_ALLOW_CFG_CHANGES 32 /* Allow the CFG to be changed 80690075Sobrien by dead code removal. */ 80790075Sobrien#define PROP_AUTOINC 64 /* Create autoinc mem references. */ 808169689Skan#define PROP_SCAN_DEAD_STORES 128 /* Scan for dead code. */ 809169689Skan#define PROP_ASM_SCAN 256 /* Internal flag used within flow.c 810132718Skan to flag analysis of asms. */ 811169689Skan#define PROP_DEAD_INSN 1024 /* Internal flag used within flow.c 812169689Skan to flag analysis of dead insn. */ 813169689Skan#define PROP_POST_REGSTACK 2048 /* We run after reg-stack and need 814169689Skan to preserve REG_DEAD notes for 815169689Skan stack regs. */ 816117395Skan#define PROP_FINAL (PROP_DEATH_NOTES | PROP_LOG_LINKS \ 817117395Skan | PROP_REG_INFO | PROP_KILL_DEAD_CODE \ 818117395Skan | PROP_SCAN_DEAD_CODE | PROP_AUTOINC \ 819117395Skan | PROP_ALLOW_CFG_CHANGES \ 820117395Skan | PROP_SCAN_DEAD_STORES) 821132718Skan#define PROP_POSTRELOAD (PROP_DEATH_NOTES \ 822132718Skan | PROP_KILL_DEAD_CODE \ 823169689Skan | PROP_SCAN_DEAD_CODE \ 824132718Skan | PROP_SCAN_DEAD_STORES) 82590075Sobrien 826132718Skan#define CLEANUP_EXPENSIVE 1 /* Do relatively expensive optimizations 82790075Sobrien except for edge forwarding */ 82890075Sobrien#define CLEANUP_CROSSJUMP 2 /* Do crossjumping. */ 82990075Sobrien#define CLEANUP_POST_REGSTACK 4 /* We run after reg-stack and need 83090075Sobrien to care REG_DEAD notes. */ 831169689Skan#define CLEANUP_UPDATE_LIFE 8 /* Keep life information up to date. */ 832169689Skan#define CLEANUP_THREADING 16 /* Do jump threading. */ 833169689Skan#define CLEANUP_NO_INSN_DEL 32 /* Do not try to delete trivially dead 834117395Skan insns. */ 835169689Skan#define CLEANUP_CFGLAYOUT 64 /* Do cleanup in cfglayout mode. */ 836169689Skan#define CLEANUP_LOG_LINKS 128 /* Update log links. */ 837169689Skan 838169689Skan/* The following are ORed in on top of the CLEANUP* flags in calls to 839169689Skan struct_equiv_block_eq. */ 840169689Skan#define STRUCT_EQUIV_START 256 /* Initializes the search range. */ 841169689Skan#define STRUCT_EQUIV_RERUN 512 /* Rerun to find register use in 842169689Skan found equivalence. */ 843169689Skan#define STRUCT_EQUIV_FINAL 1024 /* Make any changes necessary to get 844169689Skan actual equivalence. */ 845169689Skan#define STRUCT_EQUIV_NEED_FULL_BLOCK 2048 /* struct_equiv_block_eq is required 846169689Skan to match only full blocks */ 847169689Skan#define STRUCT_EQUIV_MATCH_JUMPS 4096 /* Also include the jumps at the end of the block in the comparison. */ 848169689Skan 849169689Skanextern void life_analysis (int); 850132718Skanextern int update_life_info (sbitmap, enum update_life_extent, int); 851132718Skanextern int update_life_info_in_dirty_blocks (enum update_life_extent, int); 852132718Skanextern int count_or_remove_death_notes (sbitmap, int); 853132718Skanextern int propagate_block (basic_block, regset, regset, regset, int); 85490075Sobrien 85590075Sobrienstruct propagate_block_info; 856132718Skanextern rtx propagate_one_insn (struct propagate_block_info *, rtx); 85790075Sobrienextern struct propagate_block_info *init_propagate_block_info 858132718Skan (basic_block, regset, regset, regset, int); 859132718Skanextern void free_propagate_block_info (struct propagate_block_info *); 86090075Sobrien 86152284Sobrien/* In lcm.c */ 862169689Skanextern struct edge_list *pre_edge_lcm (int, sbitmap *, sbitmap *, 863132718Skan sbitmap *, sbitmap *, sbitmap **, 864132718Skan sbitmap **); 865169689Skanextern struct edge_list *pre_edge_rev_lcm (int, sbitmap *, 866132718Skan sbitmap *, sbitmap *, 867132718Skan sbitmap *, sbitmap **, 868132718Skan sbitmap **); 869132718Skanextern void compute_available (sbitmap *, sbitmap *, sbitmap *, sbitmap *); 87090075Sobrien 87190075Sobrien/* In predict.c */ 872132718Skanextern void expected_value_to_br_prob (void); 873132718Skanextern bool maybe_hot_bb_p (basic_block); 874132718Skanextern bool probably_cold_bb_p (basic_block); 875132718Skanextern bool probably_never_executed_bb_p (basic_block); 876169689Skanextern bool tree_predicted_by_p (basic_block, enum br_predictor); 877169689Skanextern bool rtl_predicted_by_p (basic_block, enum br_predictor); 878169689Skanextern void tree_predict_edge (edge, enum br_predictor, int); 879169689Skanextern void rtl_predict_edge (edge, enum br_predictor, int); 880169689Skanextern void predict_edge_def (edge, enum br_predictor, enum prediction); 881169689Skanextern void guess_outgoing_edge_probabilities (basic_block); 882169689Skanextern void remove_predictions_associated_with_edge (edge); 883169689Skanextern bool edge_probability_reliable_p (edge); 884169689Skanextern bool br_prob_note_reliable_p (rtx); 88590075Sobrien 88690075Sobrien/* In flow.c */ 887132718Skanextern void init_flow (void); 888132718Skanextern void debug_bb (basic_block); 889132718Skanextern basic_block debug_bb_n (int); 890132718Skanextern void dump_regset (regset, FILE *); 891132718Skanextern void debug_regset (regset); 892132718Skanextern void allocate_reg_life_data (void); 893132718Skanextern void expunge_block (basic_block); 894132718Skanextern void link_block (basic_block, basic_block); 895132718Skanextern void unlink_block (basic_block); 896132718Skanextern void compact_blocks (void); 897132718Skanextern basic_block alloc_block (void); 898132718Skanextern void find_unreachable_blocks (void); 899169689Skanextern int delete_noop_moves (void); 900132718Skanextern basic_block force_nonfallthru (edge); 901132718Skanextern rtx block_label (basic_block); 902132718Skanextern bool forwarder_block_p (basic_block); 903169689Skanextern bool purge_all_dead_edges (void); 904132718Skanextern bool purge_dead_edges (basic_block); 905132718Skanextern void find_many_sub_basic_blocks (sbitmap); 906169689Skanextern void rtl_make_eh_edge (sbitmap, basic_block, rtx); 907132718Skanextern bool can_fallthru (basic_block, basic_block); 908169689Skanextern bool could_fall_through (basic_block, basic_block); 909132718Skanextern void flow_nodes_print (const char *, const sbitmap, FILE *); 910132718Skanextern void flow_edge_list_print (const char *, const edge *, int, FILE *); 911132718Skanextern void alloc_aux_for_block (basic_block, int); 912132718Skanextern void alloc_aux_for_blocks (int); 913132718Skanextern void clear_aux_for_blocks (void); 914132718Skanextern void free_aux_for_blocks (void); 915132718Skanextern void alloc_aux_for_edge (edge, int); 916132718Skanextern void alloc_aux_for_edges (int); 917132718Skanextern void clear_aux_for_edges (void); 918132718Skanextern void free_aux_for_edges (void); 919169689Skanextern void find_basic_blocks (rtx); 920169689Skanextern bool cleanup_cfg (int); 921169689Skanextern bool delete_unreachable_blocks (void); 922169689Skanextern bool merge_seq_blocks (void); 92390075Sobrien 92490075Sobrientypedef struct conflict_graph_def *conflict_graph; 92590075Sobrien 92690075Sobrien/* Callback function when enumerating conflicts. The arguments are 92790075Sobrien the smaller and larger regno in the conflict. Returns zero if 928117395Skan enumeration is to continue, nonzero to halt enumeration. */ 929132718Skantypedef int (*conflict_graph_enum_fn) (int, int, void *); 93090075Sobrien 93190075Sobrien 93290075Sobrien/* Prototypes of operations on conflict graphs. */ 93390075Sobrien 93490075Sobrienextern conflict_graph conflict_graph_new 935132718Skan (int); 936132718Skanextern void conflict_graph_delete (conflict_graph); 937132718Skanextern int conflict_graph_add (conflict_graph, int, int); 938132718Skanextern int conflict_graph_conflict_p (conflict_graph, int, int); 939132718Skanextern void conflict_graph_enum (conflict_graph, int, conflict_graph_enum_fn, 940132718Skan void *); 941132718Skanextern void conflict_graph_merge_regs (conflict_graph, int, int); 942132718Skanextern void conflict_graph_print (conflict_graph, FILE*); 943132718Skanextern bool mark_dfs_back_edges (void); 944132718Skanextern void set_edge_can_fallthru_flag (void); 945132718Skanextern void update_br_prob_note (basic_block); 946132718Skanextern void fixup_abnormal_edges (void); 947132718Skanextern bool inside_basic_block_p (rtx); 948132718Skanextern bool control_flow_insn_p (rtx); 949169689Skanextern rtx get_last_bb_insn (basic_block); 95090075Sobrien 951132718Skan/* In bb-reorder.c */ 952132718Skanextern void reorder_basic_blocks (unsigned int); 953132718Skan 95490075Sobrien/* In dominance.c */ 95590075Sobrien 95690075Sobrienenum cdi_direction 95790075Sobrien{ 95890075Sobrien CDI_DOMINATORS, 95990075Sobrien CDI_POST_DOMINATORS 96090075Sobrien}; 96190075Sobrien 962132718Skanenum dom_state 963132718Skan{ 964132718Skan DOM_NONE, /* Not computed at all. */ 965132718Skan DOM_NO_FAST_QUERY, /* The data is OK, but the fast query data are not usable. */ 966132718Skan DOM_OK /* Everything is ok. */ 967132718Skan}; 968132718Skan 969132718Skanextern enum dom_state dom_computed[2]; 970132718Skan 971169689Skanextern bool dom_info_available_p (enum cdi_direction); 972132718Skanextern void calculate_dominance_info (enum cdi_direction); 973132718Skanextern void free_dominance_info (enum cdi_direction); 974132718Skanextern basic_block nearest_common_dominator (enum cdi_direction, 975132718Skan basic_block, basic_block); 976169689Skanextern basic_block nearest_common_dominator_for_set (enum cdi_direction, 977169689Skan bitmap); 978132718Skanextern void set_immediate_dominator (enum cdi_direction, basic_block, 979132718Skan basic_block); 980132718Skanextern basic_block get_immediate_dominator (enum cdi_direction, basic_block); 981132718Skanextern bool dominated_by_p (enum cdi_direction, basic_block, basic_block); 982132718Skanextern int get_dominated_by (enum cdi_direction, basic_block, basic_block **); 983169689Skanextern unsigned get_dominated_by_region (enum cdi_direction, basic_block *, 984169689Skan unsigned, basic_block *); 985132718Skanextern void add_to_dominance_info (enum cdi_direction, basic_block); 986132718Skanextern void delete_from_dominance_info (enum cdi_direction, basic_block); 987132718Skanbasic_block recount_dominator (enum cdi_direction, basic_block); 988132718Skanextern void redirect_immediate_dominators (enum cdi_direction, basic_block, 989132718Skan basic_block); 990132718Skanextern void iterate_fix_dominators (enum cdi_direction, basic_block *, int); 991132718Skanextern void verify_dominators (enum cdi_direction); 992132718Skanextern basic_block first_dom_son (enum cdi_direction, basic_block); 993132718Skanextern basic_block next_dom_son (enum cdi_direction, basic_block); 994169689Skanunsigned bb_dom_dfs_in (enum cdi_direction, basic_block); 995169689Skanunsigned bb_dom_dfs_out (enum cdi_direction, basic_block); 996132718Skan 997169689Skanextern edge try_redirect_by_replacing_jump (edge, basic_block, bool); 998169689Skanextern void break_superblocks (void); 999169689Skanextern void check_bb_profile (basic_block, FILE *); 1000169689Skanextern void update_bb_profile_for_threading (basic_block, int, gcov_type, edge); 1001169689Skanextern void init_rtl_bb_info (basic_block); 1002169689Skan 1003169689Skanextern void initialize_original_copy_tables (void); 1004169689Skanextern void free_original_copy_tables (void); 1005169689Skanextern void set_bb_original (basic_block, basic_block); 1006169689Skanextern basic_block get_bb_original (basic_block); 1007169689Skanextern void set_bb_copy (basic_block, basic_block); 1008169689Skanextern basic_block get_bb_copy (basic_block); 1009169689Skan 1010169689Skanextern rtx insert_insn_end_bb_new (rtx, basic_block); 1011169689Skan 1012132718Skan#include "cfghooks.h" 1013132718Skan 1014169689Skan/* In struct-equiv.c */ 1015169689Skan 1016169689Skan/* Constants used to size arrays in struct equiv_info (currently only one). 1017169689Skan When these limits are exceeded, struct_equiv returns zero. 1018169689Skan The maximum number of pseudo registers that are different in the two blocks, 1019169689Skan but appear in equivalent places and are dead at the end (or where one of 1020169689Skan a pair is dead at the end). */ 1021169689Skan#define STRUCT_EQUIV_MAX_LOCAL 16 1022169689Skan/* The maximum number of references to an input register that struct_equiv 1023169689Skan can handle. */ 1024169689Skan 1025169689Skan/* Structure used to track state during struct_equiv that can be rolled 1026169689Skan back when we find we can't match an insn, or if we want to match part 1027169689Skan of it in a different way. 1028169689Skan This information pertains to the pair of partial blocks that has been 1029169689Skan matched so far. Since this pair is structurally equivalent, this is 1030169689Skan conceptually just one partial block expressed in two potentially 1031169689Skan different ways. */ 1032169689Skanstruct struct_equiv_checkpoint 1033169689Skan{ 1034169689Skan int ninsns; /* Insns are matched so far. */ 1035169689Skan int local_count; /* Number of block-local registers. */ 1036169689Skan int input_count; /* Number of inputs to the block. */ 1037169689Skan 1038169689Skan /* X_START and Y_START are the first insns (in insn stream order) 1039169689Skan of the partial blocks that have been considered for matching so far. 1040169689Skan Since we are scanning backwards, they are also the instructions that 1041169689Skan are currently considered - or the last ones that have been considered - 1042169689Skan for matching (Unless we tracked back to these because a preceding 1043169689Skan instruction failed to match). */ 1044169689Skan rtx x_start, y_start; 1045169689Skan 1046169689Skan /* INPUT_VALID indicates if we have actually set up X_INPUT / Y_INPUT 1047169689Skan during the current pass; we keep X_INPUT / Y_INPUT around between passes 1048169689Skan so that we can match REG_EQUAL / REG_EQUIV notes referring to these. */ 1049169689Skan bool input_valid; 1050169689Skan 1051169689Skan /* Some information would be expensive to exactly checkpoint, so we 1052169689Skan merely increment VERSION any time information about local 1053169689Skan registers, inputs and/or register liveness changes. When backtracking, 1054169689Skan it is decremented for changes that can be undone, and if a discrepancy 1055169689Skan remains, NEED_RERUN in the relevant struct equiv_info is set to indicate 1056169689Skan that a new pass should be made over the entire block match to get 1057169689Skan accurate register information. */ 1058169689Skan int version; 1059169689Skan}; 1060169689Skan 1061169689Skan/* A struct equiv_info is used to pass information to struct_equiv and 1062169689Skan to gather state while two basic blocks are checked for structural 1063169689Skan equivalence. */ 1064169689Skan 1065169689Skanstruct equiv_info 1066169689Skan{ 1067169689Skan /* Fields set up by the caller to struct_equiv_block_eq */ 1068169689Skan 1069169689Skan basic_block x_block, y_block; /* The two blocks being matched. */ 1070169689Skan 1071169689Skan /* MODE carries the mode bits from cleanup_cfg if we are called from 1072169689Skan try_crossjump_to_edge, and additionally it carries the 1073169689Skan STRUCT_EQUIV_* bits described above. */ 1074169689Skan int mode; 1075169689Skan 1076169689Skan /* INPUT_COST is the cost that adding an extra input to the matched blocks 1077169689Skan is supposed to have, and is taken into account when considering if the 1078169689Skan matched sequence should be extended backwards. input_cost < 0 means 1079169689Skan don't accept any inputs at all. */ 1080169689Skan int input_cost; 1081169689Skan 1082169689Skan 1083169689Skan /* Fields to track state inside of struct_equiv_block_eq. Some of these 1084169689Skan are also outputs. */ 1085169689Skan 1086169689Skan /* X_INPUT and Y_INPUT are used by struct_equiv to record a register that 1087169689Skan is used as an input parameter, i.e. where different registers are used 1088169689Skan as sources. This is only used for a register that is live at the end 1089169689Skan of the blocks, or in some identical code at the end of the blocks; 1090169689Skan Inputs that are dead at the end go into X_LOCAL / Y_LOCAL. */ 1091169689Skan rtx x_input, y_input; 1092169689Skan /* When a previous pass has identified a valid input, INPUT_REG is set 1093169689Skan by struct_equiv_block_eq, and it is henceforth replaced in X_BLOCK 1094169689Skan for the input. */ 1095169689Skan rtx input_reg; 1096169689Skan 1097169689Skan /* COMMON_LIVE keeps track of the registers which are currently live 1098169689Skan (as we scan backwards from the end) and have the same numbers in both 1099169689Skan blocks. N.B. a register that is in common_live is unsuitable to become 1100169689Skan a local reg. */ 1101169689Skan regset common_live; 1102169689Skan /* Likewise, X_LOCAL_LIVE / Y_LOCAL_LIVE keep track of registers that are 1103169689Skan local to one of the blocks; these registers must not be accepted as 1104169689Skan identical when encountered in both blocks. */ 1105169689Skan regset x_local_live, y_local_live; 1106169689Skan 1107169689Skan /* EQUIV_USED indicates for which insns a REG_EQUAL or REG_EQUIV note is 1108169689Skan being used, to avoid having to backtrack in the next pass, so that we 1109169689Skan get accurate life info for this insn then. For each such insn, 1110169689Skan the bit with the number corresponding to the CUR.NINSNS value at the 1111169689Skan time of scanning is set. */ 1112169689Skan bitmap equiv_used; 1113169689Skan 1114169689Skan /* Current state that can be saved & restored easily. */ 1115169689Skan struct struct_equiv_checkpoint cur; 1116169689Skan /* BEST_MATCH is used to store the best match so far, weighing the 1117169689Skan cost of matched insns COSTS_N_INSNS (CUR.NINSNS) against the cost 1118169689Skan CUR.INPUT_COUNT * INPUT_COST of setting up the inputs. */ 1119169689Skan struct struct_equiv_checkpoint best_match; 1120169689Skan /* If a checkpoint restore failed, or an input conflict newly arises, 1121169689Skan NEED_RERUN is set. This has to be tested by the caller to re-run 1122169689Skan the comparison if the match appears otherwise sound. The state kept in 1123169689Skan x_start, y_start, equiv_used and check_input_conflict ensures that 1124169689Skan we won't loop indefinitely. */ 1125169689Skan bool need_rerun; 1126169689Skan /* If there is indication of an input conflict at the end, 1127169689Skan CHECK_INPUT_CONFLICT is set so that we'll check for input conflicts 1128169689Skan for each insn in the next pass. This is needed so that we won't discard 1129169689Skan a partial match if there is a longer match that has to be abandoned due 1130169689Skan to an input conflict. */ 1131169689Skan bool check_input_conflict; 1132169689Skan /* HAD_INPUT_CONFLICT is set if CHECK_INPUT_CONFLICT was already set and we 1133169689Skan have passed a point where there were multiple dying inputs. This helps 1134169689Skan us decide if we should set check_input_conflict for the next pass. */ 1135169689Skan bool had_input_conflict; 1136169689Skan 1137169689Skan /* LIVE_UPDATE controls if we want to change any life info at all. We 1138169689Skan set it to false during REG_EQUAL / REG_EUQIV note comparison of the final 1139169689Skan pass so that we don't introduce new registers just for the note; if we 1140169689Skan can't match the notes without the current register information, we drop 1141169689Skan them. */ 1142169689Skan bool live_update; 1143169689Skan 1144169689Skan /* X_LOCAL and Y_LOCAL are used to gather register numbers of register pairs 1145169689Skan that are local to X_BLOCK and Y_BLOCK, with CUR.LOCAL_COUNT being the index 1146169689Skan to the next free entry. */ 1147169689Skan rtx x_local[STRUCT_EQUIV_MAX_LOCAL], y_local[STRUCT_EQUIV_MAX_LOCAL]; 1148169689Skan /* LOCAL_RVALUE is nonzero if the corresponding X_LOCAL / Y_LOCAL entry 1149169689Skan was a source operand (including STRICT_LOW_PART) for the last invocation 1150169689Skan of struct_equiv mentioning it, zero if it was a destination-only operand. 1151169689Skan Since we are scanning backwards, this means the register is input/local 1152169689Skan for the (partial) block scanned so far. */ 1153169689Skan bool local_rvalue[STRUCT_EQUIV_MAX_LOCAL]; 1154169689Skan 1155169689Skan 1156169689Skan /* Additional fields that are computed for the convenience of the caller. */ 1157169689Skan 1158169689Skan /* DYING_INPUTS is set to the number of local registers that turn out 1159169689Skan to be inputs to the (possibly partial) block. */ 1160169689Skan int dying_inputs; 1161169689Skan /* X_END and Y_END are the last insns in X_BLOCK and Y_BLOCK, respectively, 1162169689Skan that are being compared. A final jump insn will not be included. */ 1163169689Skan rtx x_end, y_end; 1164169689Skan 1165169689Skan /* If we are matching tablejumps, X_LABEL in X_BLOCK corresponds to 1166169689Skan Y_LABEL in Y_BLOCK. */ 1167169689Skan rtx x_label, y_label; 1168169689Skan 1169169689Skan}; 1170169689Skan 1171169689Skanextern bool insns_match_p (rtx, rtx, struct equiv_info *); 1172169689Skanextern int struct_equiv_block_eq (int, struct equiv_info *); 1173169689Skanextern bool struct_equiv_init (int, struct equiv_info *); 1174169689Skanextern bool rtx_equiv_p (rtx *, rtx, int, struct equiv_info *); 1175169689Skan 1176169689Skan/* In cfgrtl.c */ 1177169689Skanextern bool condjump_equiv_p (struct equiv_info *, bool); 1178169689Skan 1179169689Skan/* Return true when one of the predecessor edges of BB is marked with EDGE_EH. */ 1180169689Skanstatic inline bool bb_has_eh_pred (basic_block bb) 1181169689Skan{ 1182169689Skan edge e; 1183169689Skan edge_iterator ei; 1184169689Skan 1185169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 1186169689Skan { 1187169689Skan if (e->flags & EDGE_EH) 1188169689Skan return true; 1189169689Skan } 1190169689Skan return false; 1191169689Skan} 1192169689Skan 119390075Sobrien#endif /* GCC_BASIC_BLOCK_H */ 1194