X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fbasic-block.h;h=f3911c8f518c42d7f8c1836e867509e747fa6018;hb=ed684273f8bf24ead0ae7e3924d242ed5d6f7819;hp=0b732f67425a5288985eba621b58e3125c6088d6;hpb=59423b59a7c71964e1557b7478e2309e18a7b7de;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/basic-block.h b/gcc/basic-block.h index 0b732f67425..f3911c8f518 100644 --- a/gcc/basic-block.h +++ b/gcc/basic-block.h @@ -24,6 +24,7 @@ Boston, MA 02111-1307, USA. */ #include "bitmap.h" #include "sbitmap.h" #include "varray.h" +#include "partition.h" /* Head of register set linked list. */ typedef bitmap_head regset_head; @@ -69,13 +70,11 @@ typedef bitmap regset; #define REGNO_REG_SET_P(TO, REG) bitmap_bit_p (TO, REG) /* Copy the hard registers in a register set to the hard register set. */ +extern void reg_set_to_hard_reg_set PARAMS ((HARD_REG_SET *, bitmap)); #define REG_SET_TO_HARD_REG_SET(TO, FROM) \ do { \ - int i_; \ CLEAR_HARD_REG_SET (TO); \ - for (i_ = 0; i_ < FIRST_PSEUDO_REGISTER; i_++) \ - if (REGNO_REG_SET_P (FROM, i_)) \ - SET_HARD_REG_BIT (TO, i_); \ + reg_set_to_hard_reg_set (&TO, FROM); \ } while (0) /* Loop over all registers in REGSET, starting with MIN, setting REGNUM to the @@ -98,8 +97,8 @@ do { \ /* Allocate a register set with oballoc. */ #define OBSTACK_ALLOC_REG_SET(OBSTACK) BITMAP_OBSTACK_ALLOC (OBSTACK) -/* Allocate a register set with alloca. */ -#define ALLOCA_REG_SET() BITMAP_ALLOCA () +/* Initialize a register set. Returns the new register set. */ +#define INITIALIZE_REG_SET(HEAD) bitmap_initialize (&HEAD) /* Do any cleanup needed on a regset when it is no longer used. */ #define FREE_REG_SET(REGSET) BITMAP_FREE(REGSET) @@ -128,6 +127,8 @@ typedef struct edge_def { int flags; /* see EDGE_* below */ int probability; /* biased by REG_BR_PROB_BASE */ + int count; /* Expected number of executions calculated + in profile.c */ } *edge; #define EDGE_FALLTHRU 1 @@ -137,6 +138,20 @@ typedef struct edge_def { #define EDGE_EH 16 #define EDGE_FAKE 32 +#define EDGE_COMPLEX (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_EH) + + +/* Basic blocks need not start with a label nor end with a jump insn. + For example, a previous basic block may just "conditionally fall" + into the succeeding basic block, and the last basic block need not + end with a jump insn. Block 0 is a descendant of the entry block. + + A basic block beginning with two labels cannot have notes between + the labels. + + Data for jump tables are stored in jump_insns that occur in no + basic block even though these insns can follow or precede insns in + basic blocks. */ /* Basic block information indexed by block number. */ typedef struct basic_block_def { @@ -146,8 +161,11 @@ typedef struct basic_block_def { /* The edges into and out of the block. */ edge pred, succ; - /* Liveness info. */ + /* Liveness info. Note that in SSA form, global_live_at_start does + not reflect the use of regs in phi functions, since the liveness + of these regs may depend on which edge was taken into the block. */ regset local_set; + regset cond_local_set; regset global_live_at_start; regset global_live_at_end; @@ -156,11 +174,12 @@ typedef struct basic_block_def { /* The index of this block. */ int index; - /* The loop depth of this block plus one. */ + + /* The loop depth of this block. */ int loop_depth; - /* The active eh region before head and after end. */ - int eh_beg, eh_end; + /* Expected number of executions: calculated in profile.c. */ + int count; } *basic_block; /* Number of basic blocks in the current function. */ @@ -202,6 +221,9 @@ extern regset regs_live_at_setjmp; #define ENTRY_BLOCK (-1) #define EXIT_BLOCK (-2) +/* Special block number not valid for any block. */ +#define INVALID_BLOCK (-3) + /* Similarly, block pointers for the edge list. */ extern struct basic_block_def entry_exit_blocks[2]; #define ENTRY_BLOCK_PTR (&entry_exit_blocks[0]) @@ -212,22 +234,37 @@ extern varray_type basic_block_for_insn; #define BLOCK_NUM(INSN) (BLOCK_FOR_INSN (INSN)->index + 0) extern void compute_bb_for_insn PARAMS ((int)); +extern void update_bb_for_insn PARAMS ((basic_block)); extern void set_block_for_insn PARAMS ((rtx, basic_block)); -extern void set_block_num PARAMS ((rtx, int)); +extern void set_block_for_new_insns PARAMS ((rtx, basic_block)); extern void free_basic_block_vars PARAMS ((int)); +extern edge split_block PARAMS ((basic_block, rtx)); extern basic_block split_edge PARAMS ((edge)); extern void insert_insn_on_edge PARAMS ((rtx, edge)); extern void commit_edge_insertions PARAMS ((void)); extern void remove_fake_edges PARAMS ((void)); extern void add_noreturn_fake_exit_edges PARAMS ((void)); +extern void connect_infinite_loops_to_exit PARAMS ((void)); +extern int flow_call_edges_add PARAMS ((sbitmap)); +extern rtx flow_delete_insn PARAMS ((rtx)); extern void flow_delete_insn_chain PARAMS ((rtx, rtx)); - +extern void make_edge PARAMS ((sbitmap *, basic_block, + basic_block, int)); +extern void remove_edge PARAMS ((edge)); +extern void redirect_edge_succ PARAMS ((edge, basic_block)); +extern void redirect_edge_pred PARAMS ((edge, basic_block)); +extern void create_basic_block PARAMS ((int, rtx, rtx, rtx)); +extern int flow_delete_block PARAMS ((basic_block)); +extern void merge_blocks_nomove PARAMS ((basic_block, basic_block)); +extern void tidy_fallthru_edge PARAMS ((edge, basic_block, + basic_block)); /* Structure to hold information for each natural loop. */ struct loop { + /* Index into loops array. */ int num; /* Basic block of loop header. */ @@ -239,18 +276,43 @@ struct loop /* Basic block of loop pre-header or NULL if it does not exist. */ basic_block pre_header; + /* Array of edges along the pre-header extended basic block trace. + The source of the first edge is the root node of pre-header + extended basic block, if it exists. */ + edge *pre_header_edges; + + /* Number of edges along the pre_header extended basic block trace. */ + int num_pre_header_edges; + + /* The first block in the loop. This is not necessarily the same as + the loop header. */ + basic_block first; + + /* The last block in the loop. This is not necessarily the same as + the loop latch. */ + basic_block last; + /* Bitmap of blocks contained within the loop. */ sbitmap nodes; /* Number of blocks contained within the loop. */ int num_nodes; + /* Array of edges that enter the loop. */ + edge *entry_edges; + + /* Number of edges that enter the loop. */ + int num_entries; + /* Array of edges that exit the loop. */ - edge *exits; + edge *exit_edges; /* Number of edges that exit the loop. */ int num_exits; + /* Bitmap of blocks that dominate all exits of the loop. */ + sbitmap exits_doms; + /* The loop nesting depth. */ int depth; @@ -274,7 +336,51 @@ struct loop int invalid; /* Auxiliary info specific to a pass. */ - void *info; + void *aux; + + /* The following are currently used by loop.c but they are likely to + disappear as loop.c is converted to use the CFG. */ + + /* Non-zero if the loop has a NOTE_INSN_LOOP_VTOP. */ + rtx vtop; + + /* Non-zero if the loop has a NOTE_INSN_LOOP_CONT. + A continue statement will generate a branch to NEXT_INSN (cont). */ + rtx cont; + + /* The dominator of cont. */ + rtx cont_dominator; + + /* The NOTE_INSN_LOOP_BEG. */ + rtx start; + + /* The NOTE_INSN_LOOP_END. */ + rtx end; + + /* For a rotated loop that is entered near the bottom, + this is the label at the top. Otherwise it is zero. */ + rtx top; + + /* Place in the loop where control enters. */ + rtx scan_start; + + /* The position where to sink insns out of the loop. */ + rtx sink; + + /* List of all LABEL_REFs which refer to code labels outside the + loop. Used by routines that need to know all loop exits, such as + final_biv_value and final_giv_value. + + This does not include loop exits due to return instructions. + This is because all bivs and givs are pseudos, and hence must be + dead after a return, so the presense of a return does not affect + any of the optimizations that use this info. It is simpler to + just not include return instructions on this list. */ + rtx exit_labels; + + /* The number of LABEL_REFs on exit_labels for this loop and all + loops nested inside it. */ + int exit_count; }; @@ -284,6 +390,9 @@ struct loops /* Number of natural loops in the function. */ int num; + /* Maxium nested loop level in the function. */ + int levels; + /* Array of natural loop descriptors (scanning this array in reverse order will find the inner loops before their enclosing outer loops). */ struct loop *array; @@ -299,16 +408,26 @@ struct loops /* The ordering of the basic blocks in a depth first search. */ int *dfs_order; + + /* The reverse completion ordering of the basic blocks found in a + depth first search. */ + int *rc_order; } cfg; /* Headers shared by multiple loops that should be merged. */ sbitmap shared_headers; }; -extern int flow_loops_find PARAMS ((struct loops *)); +extern int flow_loops_find PARAMS ((struct loops *, int flags)); +extern int flow_loops_update PARAMS ((struct loops *, int flags)); extern void flow_loops_free PARAMS ((struct loops *)); -extern void flow_loops_dump PARAMS ((const struct loops *, FILE *, int)); - +extern void flow_loops_dump PARAMS ((const struct loops *, FILE *, + void (*)(const struct loop *, + FILE *, int), int)); +extern void flow_loop_dump PARAMS ((const struct loop *, FILE *, + void (*)(const struct loop *, + FILE *, int), int)); +extern int flow_loop_scan PARAMS ((struct loops *, struct loop *, int)); /* This structure maintains an edge list vector. */ struct edge_list @@ -343,9 +462,6 @@ void verify_edge_list PARAMS ((FILE *, struct edge_list *)); int find_edge_index PARAMS ((struct edge_list *, basic_block, basic_block)); -extern void compute_flow_dominators PARAMS ((sbitmap *, sbitmap *)); -extern void compute_immediate_dominators PARAMS ((int *, sbitmap *)); - enum update_life_extent { @@ -364,9 +480,28 @@ enum update_life_extent #define PROP_AUTOINC 32 /* Create autoinc mem references. */ #define PROP_FINAL 63 /* All of the above. */ +/* Flags for loop discovery. */ + +#define LOOP_TREE 1 /* Build loop hierarchy tree. */ +#define LOOP_PRE_HEADER 2 /* Analyse loop pre-header. */ +#define LOOP_ENTRY_EDGES 4 /* Find entry edges. */ +#define LOOP_EXIT_EDGES 8 /* Find exit edges. */ +#define LOOP_EDGES (LOOP_ENTRY_EDGES | LOOP_EXIT_EDGES) +#define LOOP_EXITS_DOMS 16 /* Find nodes that dom. all exits. */ +#define LOOP_ALL 31 /* All of the above */ + +extern void life_analysis PARAMS ((rtx, FILE *, int)); extern void update_life_info PARAMS ((sbitmap, enum update_life_extent, int)); extern int count_or_remove_death_notes PARAMS ((sbitmap, int)); +extern void propagate_block PARAMS ((basic_block, regset, regset, regset, + int)); + +struct propagate_block_info; +extern rtx propagate_one_insn PARAMS ((struct propagate_block_info *, rtx)); +extern struct propagate_block_info *init_propagate_block_info + PARAMS ((basic_block, regset, regset, regset, int)); +extern void free_propagate_block_info PARAMS ((struct propagate_block_info *)); /* In lcm.c */ extern struct edge_list *pre_edge_lcm PARAMS ((FILE *, int, sbitmap *, @@ -379,6 +514,7 @@ extern struct edge_list *pre_edge_rev_lcm PARAMS ((FILE *, int, sbitmap *, sbitmap **)); extern void compute_available PARAMS ((sbitmap *, sbitmap *, sbitmap *, sbitmap *)); +extern int optimize_mode_switching PARAMS ((FILE *)); /* In emit-rtl.c. */ extern rtx emit_block_insn_after PARAMS ((rtx, rtx, basic_block)); @@ -386,5 +522,60 @@ extern rtx emit_block_insn_before PARAMS ((rtx, rtx, basic_block)); /* In predict.c */ extern void estimate_probability PARAMS ((struct loops *)); +extern void expected_value_to_br_prob PARAMS ((void)); + +/* In flow.c */ +extern void init_flow PARAMS ((void)); +extern void reorder_basic_blocks PARAMS ((void)); +extern void dump_bb PARAMS ((basic_block, FILE *)); +extern void debug_bb PARAMS ((basic_block)); +extern void debug_bb_n PARAMS ((int)); +extern void dump_regset PARAMS ((regset, FILE *)); +extern void debug_regset PARAMS ((regset)); +extern void allocate_reg_life_data PARAMS ((void)); + +/* This function is always defined so it can be called from the + debugger, and it is declared extern so we don't get warnings about + it being unused. */ +extern void verify_flow_info PARAMS ((void)); +extern int flow_loop_outside_edge_p PARAMS ((const struct loop *, edge)); + +typedef struct conflict_graph_def *conflict_graph; + +/* Callback function when enumerating conflicts. The arguments are + the smaller and larger regno in the conflict. Returns zero if + enumeration is to continue, non-zero to halt enumeration. */ +typedef int (*conflict_graph_enum_fn) PARAMS ((int, int, void *)); + + +/* Prototypes of operations on conflict graphs. */ + +extern conflict_graph conflict_graph_new + PARAMS ((int)); +extern void conflict_graph_delete PARAMS ((conflict_graph)); +extern int conflict_graph_add PARAMS ((conflict_graph, + int, int)); +extern int conflict_graph_conflict_p PARAMS ((conflict_graph, + int, int)); +extern void conflict_graph_enum PARAMS ((conflict_graph, int, + conflict_graph_enum_fn, + void *)); +extern void conflict_graph_merge_regs PARAMS ((conflict_graph, int, + int)); +extern void conflict_graph_print PARAMS ((conflict_graph, FILE*)); +extern conflict_graph conflict_graph_compute + PARAMS ((regset, + partition)); + +/* In dominance.c */ + +enum cdi_direction +{ + CDI_DOMINATORS, + CDI_POST_DOMINATORS +}; + +extern void calculate_dominance_info PARAMS ((int *, sbitmap *, + enum cdi_direction)); #endif /* _BASIC_BLOCK_H */