/* Define control and data flow tables, and regsets.
- Copyright (C) 1987, 1997, 1998, 1999, 2000 Free Software Foundation, Inc.
+ Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
This file is part of GNU CC.
the Free Software Foundation, 59 Temple Place - Suite 330,
Boston, MA 02111-1307, USA. */
-#ifndef _BASIC_BLOCK_H
-#define _BASIC_BLOCK_H 1
+#ifndef GCC_BASIC_BLOCK_H
+#define GCC_BASIC_BLOCK_H
#include "bitmap.h"
#include "sbitmap.h"
#include "varray.h"
#include "partition.h"
+#ifndef TREE_CODE
+union tree_node;
+#define tree union tree_node *
+#endif
+
/* Head of register set linked list. */
typedef bitmap_head regset_head;
/* A pointer to a regset_head. */
#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
/* Grow any tables needed when the number of registers is calculated
or extended. For the linked list allocation, nothing needs to
be done, other than zero the statistics on the first allocation. */
-#define MAX_REGNO_REG_SET(NUM_REGS, NEW_P, RENUMBER_P)
+#define MAX_REGNO_REG_SET(NUM_REGS, NEW_P, RENUMBER_P)
+
+/* Type we use to hold basic block counters. Should be at least 64bit. */
+typedef HOST_WIDEST_INT gcov_type;
/* Control flow edge information. */
typedef struct edge_def {
int flags; /* see EDGE_* below */
int probability; /* biased by REG_BR_PROB_BASE */
+ gcov_type count; /* Expected number of executions calculated
+ in profile.c */
} *edge;
#define EDGE_FALLTHRU 1
#define EDGE_ABNORMAL_CALL 8
#define EDGE_EH 16
#define EDGE_FAKE 32
+#define EDGE_DFS_BACK 64
+
+#define EDGE_COMPLEX (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_EH)
+
+
+/* A basic block is a sequence of instructions with only entry and
+ only one exit. If any one of the instructions are executed, they
+ will all be executed, and in sequence from first to last.
+ There may be COND_EXEC instructions in the basic block. The
+ COND_EXEC *instructions* will be executed -- but if the condition
+ is false the conditionally executed *expressions* will of course
+ not be executed. We don't consider the conditionally executed
+ expression (which might have side-effects) to be in a separate
+ basic block because the program counter will always be at the same
+ location after the COND_EXEC instruction, regardless of whether the
+ condition is true or not.
+
+ 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 {
/* The first and last insns of the block. */
rtx head, end;
+ /* The first and last trees of the block. */
+ tree head_tree;
+ tree end_tree;
+
/* The edges into and out of the block. */
edge pred, succ;
- /* 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. */
+ /* Liveness info. */
+
+ /* The registers that are modified within this in block. */
regset local_set;
+ /* The registers that are conditionally modified within this block.
+ In other words, registers that are set only as part of a
+ COND_EXEC. */
+ regset cond_local_set;
+ /* The registers that are live on entry to this block.
+
+ 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 global_live_at_start;
+ /* The registers that are live on exit from this block. */
regset global_live_at_end;
/* Auxiliary info specific to a pass. */
/* 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. */
+ gcov_type count;
+
+ /* Expected frequency. Normalized to be in range 0 to BB_FREQ_MAX. */
+ int frequency;
} *basic_block;
+#define BB_FREQ_MAX 10000
+
/* Number of basic blocks in the current function. */
extern int n_basic_blocks;
#define BLOCK_HEAD(B) (BASIC_BLOCK (B)->head)
#define BLOCK_END(B) (BASIC_BLOCK (B)->end)
+#define BLOCK_HEAD_TREE(B) (BASIC_BLOCK (B)->head_tree)
+#define BLOCK_END_TREE(B) (BASIC_BLOCK (B)->end_tree)
+
/* Special block numbers [markers] for entry and exit. */
#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])
#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_succ_nodup 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));
+extern int flow_depth_first_order_compute PARAMS ((int *, int *));
+extern void dump_edge_info PARAMS ((FILE *, edge, int));
+extern void clear_edges PARAMS ((void));
+extern void mark_critical_edges PARAMS ((void));
+extern rtx first_insn_after_basic_block_note PARAMS ((basic_block));
/* Structure to hold information for each natural loop. */
struct loop
{
+ /* Index into loops array. */
int num;
/* Basic block of loop header. */
/* 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;
/* 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;
/* 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
struct loop *array;
/* Pointer to root of loop heirachy tree. */
- struct loop *tree;
+ struct loop *tree_root;
/* Information derived from the CFG. */
struct cfg
/* 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
+struct edge_list
{
int num_blocks;
int num_edges;
/* Number of edges in the compressed edge list. */
#define NUM_EDGES(el) ((el)->num_edges)
+/* BB is assumed to contain conditional jump. Return the fallthru edge. */
+#define FALLTHRU_EDGE(bb) ((bb)->succ->flags & EDGE_FALLTHRU \
+ ? (bb)->succ : (bb)->succ->succ_next)
+
+/* BB is assumed to contain conditional jump. Return the branch edge. */
+#define BRANCH_EDGE(bb) ((bb)->succ->flags & EDGE_FALLTHRU \
+ ? (bb)->succ->succ_next : (bb)->succ)
+
+/* Return expected execution frequency of the edge E. */
+#define EDGE_FREQUENCY(e) (((e)->src->frequency \
+ * (e)->probability \
+ + REG_BR_PROB_BASE / 2) \
+ / REG_BR_PROB_BASE)
+
struct edge_list * create_edge_list PARAMS ((void));
void free_edge_list PARAMS ((struct edge_list *));
void print_edge_list PARAMS ((FILE *, struct edge_list *));
void verify_edge_list PARAMS ((FILE *, struct edge_list *));
-int find_edge_index PARAMS ((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
{
#define PROP_REG_INFO 4 /* Update regs_ever_live et al. */
#define PROP_KILL_DEAD_CODE 8 /* Remove dead code. */
#define PROP_SCAN_DEAD_CODE 16 /* Scan for dead code. */
-#define PROP_AUTOINC 32 /* Create autoinc mem references. */
-#define PROP_FINAL 63 /* All of the above. */
-
+#define PROP_ALLOW_CFG_CHANGES 32 /* Allow the CFG to be changed
+ by dead code removal. */
+#define PROP_AUTOINC 64 /* Create autoinc mem references. */
+#define PROP_FINAL 127 /* All of the above. */
+
+#define CLEANUP_EXPENSIVE 1 /* Do relativly expensive optimizations
+ except for edge forwarding */
+#define CLEANUP_CROSSJUMP 2 /* Do crossjumping. */
+#define CLEANUP_POST_REGSTACK 4 /* We run after reg-stack and need
+ to care REG_DEAD notes. */
+#define CLEANUP_PRE_SIBCALL 8 /* Do not get confused by code hidden
+ inside call_placeholders.. */
+#define CLEANUP_PRE_LOOP 16 /* Take care to preserve syntactic loop
+ notes. */
+/* 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 int 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 *,
- sbitmap *, sbitmap *,
+extern struct edge_list *pre_edge_lcm PARAMS ((FILE *, int, sbitmap *,
+ sbitmap *, sbitmap *,
sbitmap *, sbitmap **,
sbitmap **));
extern struct edge_list *pre_edge_rev_lcm PARAMS ((FILE *, int, sbitmap *,
- sbitmap *, sbitmap *,
- sbitmap *, sbitmap **,
+ sbitmap *, sbitmap *,
+ sbitmap *, sbitmap **,
sbitmap **));
extern void compute_available PARAMS ((sbitmap *, sbitmap *,
sbitmap *, sbitmap *));
-extern void optimize_mode_switching PARAMS ((FILE *));
+extern int optimize_mode_switching PARAMS ((FILE *));
/* In emit-rtl.c. */
extern rtx emit_block_insn_after PARAMS ((rtx, rtx, basic_block));
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));
+extern void allocate_bb_life_data PARAMS ((void));
+extern void find_unreachable_blocks PARAMS ((void));
+extern void delete_noop_moves PARAMS ((rtx));
+extern rtx last_loop_beg_note PARAMS ((rtx));
+extern basic_block redirect_edge_and_branch_force PARAMS ((edge, basic_block));
+extern bool redirect_edge_and_branch PARAMS ((edge, basic_block));
+extern rtx block_label PARAMS ((basic_block));
+extern bool forwarder_block_p PARAMS ((basic_block));
+extern void purge_all_dead_edges PARAMS ((void));
+extern void purge_dead_edges PARAMS ((basic_block));
+extern void find_sub_basic_blocks PARAMS ((basic_block));
+
/* 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
/* Prototypes of operations on conflict graphs. */
-extern conflict_graph conflict_graph_new
+extern conflict_graph conflict_graph_new
PARAMS ((int));
extern void conflict_graph_delete PARAMS ((conflict_graph));
-extern int conflict_graph_add PARAMS ((conflict_graph,
+extern int conflict_graph_add PARAMS ((conflict_graph,
int, int));
-extern int conflict_graph_conflict_p PARAMS ((conflict_graph,
+extern int conflict_graph_conflict_p PARAMS ((conflict_graph,
int, int));
-extern void conflict_graph_enum PARAMS ((conflict_graph, int,
- conflict_graph_enum_fn,
+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
+extern conflict_graph conflict_graph_compute
PARAMS ((regset,
partition));
+extern bool mark_dfs_back_edges PARAMS ((void));
-/* In ssa.c */
-extern void convert_to_ssa PARAMS ((void));
-extern void convert_from_ssa PARAMS ((void));
-typedef int (*successor_phi_fn) PARAMS ((rtx, int, int, void *));
-extern int for_each_successor_phi PARAMS ((basic_block bb,
- successor_phi_fn,
- void *));
-extern int in_ssa_form;
+/* 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 */
+#endif /* GCC_BASIC_BLOCK_H */
OSDN Git Service
