#include "bitmap.h"
#include "sbitmap.h"
#include "varray.h"
+#include "partition.h"
/* Head of register set linked list. */
typedef bitmap_head 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
/* 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)
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
#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 {
/* 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;
/* 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. */
#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_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. */
/* 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;
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;
};
/* 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;
/* 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
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_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 *,
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));
/* 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 */
OSDN Git Service
