/* 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. */
/* 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 */
- int count; /* Expected number of executions calculated
+ gcov_type count; /* Expected number of executions calculated
in profile.c */
} *edge;
#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)
-/* Basic blocks need not start with a label nor end with a jump insn.
+/* 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.
/* 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;
- int count; /* Expected number of executions: calculated in
- profile.c */
+ /* 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)
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 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
/* 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.
+ /* 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;
/* 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
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));
#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. */
-/* Flag number 64 is used internally in flow.c. */
-
+#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_TREE 1 /* Build loop hierarchy tree. */
#define LOOP_PRE_HEADER 2 /* Analyse loop pre-header. */
-#define LOOP_EDGES 4 /* Find entry and exit edges. */
-#define LOOP_EXITS_DOMS 8 /* Find nodes that dom. all exits. */
-#define LOOP_ALL 15 /* All of the above */
+#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,
+extern int propagate_block PARAMS ((basic_block, regset, regset, regset,
int));
struct propagate_block_info;
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 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 dominance.c */
extern void calculate_dominance_info PARAMS ((int *, sbitmap *,
enum cdi_direction));
-#endif /* _BASIC_BLOCK_H */
+#endif /* GCC_BASIC_BLOCK_H */
OSDN Git Service
