You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA. */
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA. */
#ifndef GCC_BASIC_BLOCK_H
#define GCC_BASIC_BLOCK_H
#include "hard-reg-set.h"
#include "predict.h"
#include "vec.h"
-#include "errors.h"
+#include "function.h"
/* Head of register set linked list. */
typedef bitmap_head regset_head;
/* Instructions queued on the edge. */
union edge_def_insns {
- rtx GTY ((tag ("0"))) r;
- tree GTY ((tag ("1"))) t;
- } GTY ((desc ("ir_type ()"))) insns;
+ tree GTY ((tag ("true"))) t;
+ rtx GTY ((tag ("false"))) r;
+ } GTY ((desc ("current_ir_type () == IR_GIMPLE"))) insns;
/* Auxiliary info specific to a pass. */
PTR GTY ((skip (""))) aux;
};
typedef struct edge_def *edge;
-DEF_VEC_GC_P(edge);
+DEF_VEC_P(edge);
+DEF_VEC_ALLOC_P(edge,gc);
+DEF_VEC_ALLOC_P(edge,heap);
#define EDGE_FALLTHRU 1 /* 'Straight line' flow */
#define EDGE_ABNORMAL 2 /* Strange flow, like computed
/* Declared in cfgloop.h. */
struct loop;
-struct loops;
/* Declared in tree-flow.h. */
-struct bb_ann_d;
+struct edge_prediction;
+struct rtl_bb_info;
/* A basic block is a sequence of instructions with only entry and
only one exit. If any one of the instructions are executed, they
/* Basic block information indexed by block number. */
struct basic_block_def GTY((chain_next ("%h.next_bb"), chain_prev ("%h.prev_bb")))
{
- /* The first and last insns of the block. */
- rtx head_;
- rtx end_;
-
/* Pointers to the first and last trees of the block. */
tree stmt_list;
/* The edges into and out of the block. */
- VEC(edge) *preds;
- VEC(edge) *succs;
-
- /* The registers that are live on entry to this block. */
- bitmap GTY ((skip (""))) global_live_at_start;
-
- /* The registers that are live on exit from this block. */
- bitmap GTY ((skip (""))) global_live_at_end;
+ VEC(edge,gc) *preds;
+ VEC(edge,gc) *succs;
/* Auxiliary info specific to a pass. */
PTR GTY ((skip (""))) aux;
struct basic_block_def *prev_bb;
struct basic_block_def *next_bb;
- /* The data used by basic block copying and reordering functions. */
- struct reorder_block_def * GTY ((skip (""))) rbi;
+ union basic_block_il_dependent {
+ struct rtl_bb_info * GTY ((tag ("1"))) rtl;
+ } GTY ((desc ("((%1.flags & BB_RTL) != 0)"))) il;
- /* Annotations used at the tree level. */
- struct bb_ann_d *tree_annotations;
+ /* Chain of PHI nodes for this block. */
+ tree phi_nodes;
+
+ /* A list of predictions. */
+ struct edge_prediction *predictions;
/* Expected number of executions: calculated in profile.c. */
gcov_type count;
int flags;
};
-typedef struct basic_block_def *basic_block;
+struct rtl_bb_info GTY(())
+{
+ /* The first and last insns of the block. */
+ rtx head_;
+ rtx end_;
-/* Structure to hold information about the blocks during reordering and
- copying. */
+ /* The registers that are live on entry to this block. */
+ bitmap GTY ((skip (""))) global_live_at_start;
-typedef struct reorder_block_def
-{
+ /* The registers that are live on exit from this block. */
+ bitmap GTY ((skip (""))) global_live_at_end;
+
+ /* In CFGlayout mode points to insn notes/jumptables to be placed just before
+ and after the block. */
rtx header;
rtx footer;
- basic_block next;
- basic_block original;
- /* Used by loop copying. */
- basic_block copy;
- int duplicated;
- int copy_number;
-
- /* These fields are used by bb-reorder pass. */
+
+ /* This field is used by the bb-reorder and tracer passes. */
int visited;
-} *reorder_block_def_p;
+};
+
+typedef struct basic_block_def *basic_block;
+
+DEF_VEC_P(basic_block);
+DEF_VEC_ALLOC_P(basic_block,gc);
+DEF_VEC_ALLOC_P(basic_block,heap);
#define BB_FREQ_MAX 10000
/* Masks for basic_block.flags.
- BB_VISITED should not be used by passes, it is used internally by
- dfs_enumerate_from.
-
BB_HOT_PARTITION and BB_COLD_PARTITION should be preserved throughout
the compilation, so they are never cleared.
All other flags may be cleared by clear_bb_flags(). It is generally
a bad idea to rely on any flags being up-to-date. */
-/* Set if insns in BB have are modified. Used for updating liveness info. */
-#define BB_DIRTY 1
+enum bb_flags
+{
+
+ /* Set if insns in BB have are modified. Used for updating liveness info. */
+ BB_DIRTY = 1,
+
+ /* Only set on blocks that have just been created by create_bb. */
+ BB_NEW = 2,
+
+ /* Set by find_unreachable_blocks. Do not rely on this being set in any
+ pass. */
+ BB_REACHABLE = 4,
-/* Only set on blocks that have just been created by create_bb. */
-#define BB_NEW 2
+ /* Set for blocks in an irreducible loop by loop analysis. */
+ BB_IRREDUCIBLE_LOOP = 8,
-/* Set by find_unreachable_blocks. Do not rely on this being set in any
- pass. */
-#define BB_REACHABLE 4
+ /* Set on blocks that may actually not be single-entry single-exit block. */
+ BB_SUPERBLOCK = 16,
-/* Used by dfs_enumerate_from to keep track of visited basic blocks. */
-#define BB_VISITED 8
+ /* Set on basic blocks that the scheduler should not touch. This is used
+ by SMS to prevent other schedulers from messing with the loop schedule. */
+ BB_DISABLE_SCHEDULE = 32,
-/* Set for blocks in an irreducible loop by loop analysis. */
-#define BB_IRREDUCIBLE_LOOP 16
+ /* Set on blocks that should be put in a hot section. */
+ BB_HOT_PARTITION = 64,
-/* Set on blocks that may actually not be single-entry single-exit block. */
-#define BB_SUPERBLOCK 32
+ /* Set on blocks that should be put in a cold section. */
+ BB_COLD_PARTITION = 128,
-/* Set on basic blocks that the scheduler should not touch. This is used
- by SMS to prevent other schedulers from messing with the loop schedule. */
-#define BB_DISABLE_SCHEDULE 64
+ /* Set on block that was duplicated. */
+ BB_DUPLICATED = 256,
-/* Set on blocks that should be put in a hot section. */
-#define BB_HOT_PARTITION 128
+ /* Set on blocks that are in RTL format. */
+ BB_RTL = 1024,
-/* Set on blocks that should be put in a cold section. */
-#define BB_COLD_PARTITION 256
+ /* Set on blocks that are forwarder blocks.
+ Only used in cfgcleanup.c. */
+ BB_FORWARDER_BLOCK = 2048,
+
+ /* Set on blocks that cannot be threaded through.
+ Only used in cfgcleanup.c. */
+ BB_NONTHREADABLE_BLOCK = 4096
+};
/* Dummy flag for convenience in the hot/cold partitioning code. */
#define BB_UNPARTITIONED 0
#define BB_COPY_PARTITION(dstbb, srcbb) \
BB_SET_PARTITION (dstbb, BB_PARTITION (srcbb))
-/* Number of basic blocks in the current function. */
-
-extern int n_basic_blocks;
-
-/* First free basic block number. */
+/* A structure to group all the per-function control flow graph data.
+ The x_* prefixing is necessary because otherwise references to the
+ fields of this struct are interpreted as the defines for backward
+ source compatibility following the definition of this struct. */
+struct control_flow_graph GTY(())
+{
+ /* Block pointers for the exit and entry of a function.
+ These are always the head and tail of the basic block list. */
+ basic_block x_entry_block_ptr;
+ basic_block x_exit_block_ptr;
-extern int last_basic_block;
+ /* Index by basic block number, get basic block struct info. */
+ VEC(basic_block,gc) *x_basic_block_info;
-/* Number of edges in the current function. */
+ /* Number of basic blocks in this flow graph. */
+ int x_n_basic_blocks;
-extern int n_edges;
+ /* Number of edges in this flow graph. */
+ int x_n_edges;
-/* TRUE if we should re-run loop discovery after threading jumps, FALSE
- otherwise. */
-extern bool rediscover_loops_after_threading;
+ /* The first free basic block number. */
+ int x_last_basic_block;
-/* Signalize the status of profile information in the CFG. */
-extern enum profile_status
-{
- PROFILE_ABSENT,
- PROFILE_GUESSED,
- PROFILE_READ
-} profile_status;
+ /* Mapping of labels to their associated blocks. At present
+ only used for the tree CFG. */
+ VEC(basic_block,gc) *x_label_to_block_map;
-/* Index by basic block number, get basic block struct info. */
-
-extern GTY(()) varray_type basic_block_info;
+ enum profile_status {
+ PROFILE_ABSENT,
+ PROFILE_GUESSED,
+ PROFILE_READ
+ } x_profile_status;
+};
-#define BASIC_BLOCK(N) (VARRAY_BB (basic_block_info, (N)))
+/* Defines for accessing the fields of the CFG structure for function FN. */
+#define ENTRY_BLOCK_PTR_FOR_FUNCTION(FN) ((FN)->cfg->x_entry_block_ptr)
+#define EXIT_BLOCK_PTR_FOR_FUNCTION(FN) ((FN)->cfg->x_exit_block_ptr)
+#define basic_block_info_for_function(FN) ((FN)->cfg->x_basic_block_info)
+#define n_basic_blocks_for_function(FN) ((FN)->cfg->x_n_basic_blocks)
+#define n_edges_for_function(FN) ((FN)->cfg->x_n_edges)
+#define last_basic_block_for_function(FN) ((FN)->cfg->x_last_basic_block)
+#define label_to_block_map_for_function(FN) ((FN)->cfg->x_label_to_block_map)
+
+#define BASIC_BLOCK_FOR_FUNCTION(FN,N) \
+ (VEC_index (basic_block, basic_block_info_for_function(FN), (N)))
+
+/* Defines for textual backward source compatibility. */
+#define ENTRY_BLOCK_PTR (cfun->cfg->x_entry_block_ptr)
+#define EXIT_BLOCK_PTR (cfun->cfg->x_exit_block_ptr)
+#define basic_block_info (cfun->cfg->x_basic_block_info)
+#define n_basic_blocks (cfun->cfg->x_n_basic_blocks)
+#define n_edges (cfun->cfg->x_n_edges)
+#define last_basic_block (cfun->cfg->x_last_basic_block)
+#define label_to_block_map (cfun->cfg->x_label_to_block_map)
+#define profile_status (cfun->cfg->x_profile_status)
+
+#define BASIC_BLOCK(N) (VEC_index (basic_block, basic_block_info, (N)))
+#define SET_BASIC_BLOCK(N,BB) (VEC_replace (basic_block, basic_block_info, (N), (BB)))
/* For iterating over basic blocks. */
#define FOR_BB_BETWEEN(BB, FROM, TO, DIR) \
for (BB = FROM; BB != TO; BB = BB->DIR)
-#define FOR_EACH_BB(BB) \
- FOR_BB_BETWEEN (BB, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR, next_bb)
+#define FOR_EACH_BB_FN(BB, FN) \
+ FOR_BB_BETWEEN (BB, (FN)->cfg->x_entry_block_ptr->next_bb, (FN)->cfg->x_exit_block_ptr, next_bb)
+
+#define FOR_EACH_BB(BB) FOR_EACH_BB_FN (BB, cfun)
-#define FOR_EACH_BB_REVERSE(BB) \
- FOR_BB_BETWEEN (BB, EXIT_BLOCK_PTR->prev_bb, ENTRY_BLOCK_PTR, prev_bb)
+#define FOR_EACH_BB_REVERSE_FN(BB, FN) \
+ FOR_BB_BETWEEN (BB, (FN)->cfg->x_exit_block_ptr->prev_bb, (FN)->cfg->x_entry_block_ptr, prev_bb)
+
+#define FOR_EACH_BB_REVERSE(BB) FOR_EACH_BB_REVERSE_FN(BB, cfun)
/* For iterating over insns in basic block. */
#define FOR_BB_INSNS(BB, INSN) \
for ((INSN) = BB_HEAD (BB); \
- (INSN) != NEXT_INSN (BB_END (BB)); \
+ (INSN) && (INSN) != NEXT_INSN (BB_END (BB)); \
(INSN) = NEXT_INSN (INSN))
#define FOR_BB_INSNS_REVERSE(BB, INSN) \
for ((INSN) = BB_END (BB); \
- (INSN) != PREV_INSN (BB_HEAD (BB)); \
+ (INSN) && (INSN) != PREV_INSN (BB_HEAD (BB)); \
(INSN) = PREV_INSN (INSN))
/* Cycles through _all_ basic blocks, even the fake ones (entry and
#define FOR_ALL_BB(BB) \
for (BB = ENTRY_BLOCK_PTR; BB; BB = BB->next_bb)
-/* Special labels found during CFG build. */
-
-extern GTY(()) rtx label_value_list;
+#define FOR_ALL_BB_FN(BB, FN) \
+ for (BB = ENTRY_BLOCK_PTR_FOR_FUNCTION (FN); BB; BB = BB->next_bb)
extern bitmap_obstack reg_obstack;
#define REG_BLOCK_UNKNOWN -1
#define REG_BLOCK_GLOBAL -2
-#define REG_BASIC_BLOCK(N) (VARRAY_REG (reg_n_info, N)->basic_block)
+#define REG_BASIC_BLOCK(N) \
+ (VEC_index (reg_info_p, reg_n_info, N)->basic_block)
\f
/* Stuff for recording basic block info. */
-#define BB_HEAD(B) (B)->head_
-#define BB_END(B) (B)->end_
+#define BB_HEAD(B) (B)->il.rtl->head_
+#define BB_END(B) (B)->il.rtl->end_
/* Special block numbers [markers] for entry and exit. */
-#define ENTRY_BLOCK (-1)
-#define EXIT_BLOCK (-2)
+#define ENTRY_BLOCK (0)
+#define EXIT_BLOCK (1)
-/* Special block number not valid for any block. */
-#define INVALID_BLOCK (-3)
+/* The two blocks that are always in the cfg. */
+#define NUM_FIXED_BLOCKS (2)
-/* Similarly, block pointers for the edge list. */
-extern GTY(()) basic_block ENTRY_BLOCK_PTR;
-extern GTY(()) basic_block EXIT_BLOCK_PTR;
#define BLOCK_NUM(INSN) (BLOCK_FOR_INSN (INSN)->index + 0)
#define set_block_for_insn(INSN, BB) (BLOCK_FOR_INSN (INSN) = BB)
extern void compute_bb_for_insn (void);
-extern void free_bb_for_insn (void);
+extern unsigned int free_bb_for_insn (void);
extern void update_bb_for_insn (basic_block);
extern void free_basic_block_vars (void);
extern void insert_insn_on_edge (rtx, edge);
-bool safe_insert_insn_on_edge (rtx, edge);
+basic_block split_edge_and_insert (edge, rtx);
extern void commit_edge_insertions (void);
-extern void commit_edge_insertions_watch_calls (void);
extern void remove_fake_edges (void);
extern void remove_fake_exit_edges (void);
extern void add_noreturn_fake_exit_edges (void);
extern void connect_infinite_loops_to_exit (void);
extern edge unchecked_make_edge (basic_block, basic_block, int);
-extern edge cached_make_edge (sbitmap *, basic_block, basic_block, int);
+extern edge cached_make_edge (sbitmap, basic_block, basic_block, int);
extern edge make_edge (basic_block, basic_block, int);
extern edge make_single_succ_edge (basic_block, basic_block, int);
extern void remove_edge (edge);
extern void redirect_edge_pred (edge, basic_block);
extern basic_block create_basic_block_structure (rtx, rtx, rtx, basic_block);
extern void clear_bb_flags (void);
-extern void flow_reverse_top_sort_order_compute (int *);
-extern int flow_depth_first_order_compute (int *, int *);
+extern int post_order_compute (int *, bool);
+extern int pre_and_rev_post_order_compute (int *, int *, bool);
extern int dfs_enumerate_from (basic_block, int,
bool (*)(basic_block, void *),
basic_block *, int, void *);
extern void compute_dominance_frontiers (bitmap *);
+extern void dump_bb_info (basic_block, bool, bool, int, const char *, FILE *);
extern void dump_edge_info (FILE *, edge, int);
extern void brief_dump_cfg (FILE *);
extern void clear_edges (void);
extern rtx first_insn_after_basic_block_note (basic_block);
+extern void scale_bbs_frequencies_int (basic_block *, int, int, int);
+extern void scale_bbs_frequencies_gcov_type (basic_block *, int, gcov_type,
+ gcov_type);
/* Structure to group all of the information to process IF-THEN and
IF-THEN-ELSE blocks for the conditional execution support. This
edge *index_to_edge;
};
+/* The base value for branch probability notes and edge probabilities. */
+#define REG_BR_PROB_BASE 10000
+
/* This is the value which indicates no edge is present. */
#define EDGE_INDEX_NO_EDGE -1
#define EDGE_PRED(bb,i) VEC_index (edge, (bb)->preds, (i))
#define EDGE_SUCC(bb,i) VEC_index (edge, (bb)->succs, (i))
+/* Returns true if BB has precisely one successor. */
+
+static inline bool
+single_succ_p (basic_block bb)
+{
+ return EDGE_COUNT (bb->succs) == 1;
+}
+
+/* Returns true if BB has precisely one predecessor. */
+
+static inline bool
+single_pred_p (basic_block bb)
+{
+ return EDGE_COUNT (bb->preds) == 1;
+}
+
+/* Returns the single successor edge of basic block BB. Aborts if
+ BB does not have exactly one successor. */
+
+static inline edge
+single_succ_edge (basic_block bb)
+{
+ gcc_assert (single_succ_p (bb));
+ return EDGE_SUCC (bb, 0);
+}
+
+/* Returns the single predecessor edge of basic block BB. Aborts
+ if BB does not have exactly one predecessor. */
+
+static inline edge
+single_pred_edge (basic_block bb)
+{
+ gcc_assert (single_pred_p (bb));
+ return EDGE_PRED (bb, 0);
+}
+
+/* Returns the single successor block of basic block BB. Aborts
+ if BB does not have exactly one successor. */
+
+static inline basic_block
+single_succ (basic_block bb)
+{
+ return single_succ_edge (bb)->dest;
+}
+
+/* Returns the single predecessor block of basic block BB. Aborts
+ if BB does not have exactly one predecessor.*/
+
+static inline basic_block
+single_pred (basic_block bb)
+{
+ return single_pred_edge (bb)->src;
+}
+
/* Iterator object for edges. */
typedef struct {
unsigned index;
- VEC(edge) **container;
+ VEC(edge,gc) **container;
} edge_iterator;
-static inline VEC(edge) *
+static inline VEC(edge,gc) *
ei_container (edge_iterator i)
{
gcc_assert (i.container);
/* Return an iterator pointing to the start of an edge vector. */
static inline edge_iterator
-ei_start_1 (VEC(edge) **ev)
+ei_start_1 (VEC(edge,gc) **ev)
{
edge_iterator i;
/* Return an iterator pointing to the last element of an edge
vector. */
static inline edge_iterator
-ei_last_1 (VEC(edge) **ev)
+ei_last_1 (VEC(edge,gc) **ev)
{
edge_iterator i;
return !ei_end_p (i) ? ei_edge (i) : NULL;
}
+/* Return 1 if we should continue to iterate. Return 0 otherwise.
+ *Edge P is set to the next edge if we are to continue to iterate
+ and NULL otherwise. */
+
+static inline bool
+ei_cond (edge_iterator ei, edge *p)
+{
+ if (!ei_end_p (ei))
+ {
+ *p = ei_edge (ei);
+ return 1;
+ }
+ else
+ {
+ *p = NULL;
+ return 0;
+ }
+}
+
/* This macro serves as a convenient way to iterate each edge in a
vector of predecessor or successor edges. It must not be used when
an element might be removed during the traversal, otherwise
elements will be missed. Instead, use a for-loop like that shown
in the following pseudo-code:
-
+
FOR (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
{
IF (e != taken_edge)
}
*/
-#define FOR_EACH_EDGE(EDGE,ITER,EDGE_VEC) \
- for ((EDGE) = NULL, (ITER) = ei_start ((EDGE_VEC)); \
- ((EDGE) = ei_safe_edge ((ITER))); \
+#define FOR_EACH_EDGE(EDGE,ITER,EDGE_VEC) \
+ for ((ITER) = ei_start ((EDGE_VEC)); \
+ ei_cond ((ITER), &(EDGE)); \
ei_next (&(ITER)))
struct edge_list * create_edge_list (void);
#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_EQUAL_NOTES 128 /* Take into account REG_EQUAL notes. */
-#define PROP_SCAN_DEAD_STORES 256 /* Scan for dead code. */
-#define PROP_ASM_SCAN 512 /* Internal flag used within flow.c
+#define PROP_SCAN_DEAD_STORES 128 /* Scan for dead code. */
+#define PROP_ASM_SCAN 256 /* Internal flag used within flow.c
to flag analysis of asms. */
+#define PROP_DEAD_INSN 1024 /* Internal flag used within flow.c
+ to flag analysis of dead insn. */
+#define PROP_POST_REGSTACK 2048 /* We run after reg-stack and need
+ to preserve REG_DEAD notes for
+ stack regs. */
#define PROP_FINAL (PROP_DEATH_NOTES | PROP_LOG_LINKS \
| PROP_REG_INFO | PROP_KILL_DEAD_CODE \
| PROP_SCAN_DEAD_CODE | PROP_AUTOINC \
#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_LOOP 8 /* Take care to preserve syntactic loop
- notes. */
-#define CLEANUP_UPDATE_LIFE 16 /* Keep life information up to date. */
-#define CLEANUP_THREADING 32 /* Do jump threading. */
-#define CLEANUP_NO_INSN_DEL 64 /* Do not try to delete trivially dead
+#define CLEANUP_UPDATE_LIFE 8 /* Keep life information up to date. */
+#define CLEANUP_THREADING 16 /* Do jump threading. */
+#define CLEANUP_NO_INSN_DEL 32 /* Do not try to delete trivially dead
insns. */
-#define CLEANUP_CFGLAYOUT 128 /* Do cleanup in cfglayout mode. */
-#define CLEANUP_LOG_LINKS 256 /* Update log links. */
-
-extern void life_analysis (FILE *, int);
+#define CLEANUP_CFGLAYOUT 64 /* Do cleanup in cfglayout mode. */
+#define CLEANUP_LOG_LINKS 128 /* Update log links. */
+
+/* The following are ORed in on top of the CLEANUP* flags in calls to
+ struct_equiv_block_eq. */
+#define STRUCT_EQUIV_START 256 /* Initializes the search range. */
+#define STRUCT_EQUIV_RERUN 512 /* Rerun to find register use in
+ found equivalence. */
+#define STRUCT_EQUIV_FINAL 1024 /* Make any changes necessary to get
+ actual equivalence. */
+#define STRUCT_EQUIV_NEED_FULL_BLOCK 2048 /* struct_equiv_block_eq is required
+ to match only full blocks */
+#define STRUCT_EQUIV_MATCH_JUMPS 4096 /* Also include the jumps at the end of the block in the comparison. */
+
+extern void life_analysis (int);
extern int update_life_info (sbitmap, enum update_life_extent, int);
extern int update_life_info_in_dirty_blocks (enum update_life_extent, int);
extern int count_or_remove_death_notes (sbitmap, int);
extern void free_propagate_block_info (struct propagate_block_info *);
/* In lcm.c */
-extern struct edge_list *pre_edge_lcm (FILE *, int, sbitmap *, sbitmap *,
+extern struct edge_list *pre_edge_lcm (int, sbitmap *, sbitmap *,
sbitmap *, sbitmap *, sbitmap **,
sbitmap **);
-extern struct edge_list *pre_edge_rev_lcm (FILE *, int, sbitmap *,
+extern struct edge_list *pre_edge_rev_lcm (int, sbitmap *,
sbitmap *, sbitmap *,
sbitmap *, sbitmap **,
sbitmap **);
extern void compute_available (sbitmap *, sbitmap *, sbitmap *, sbitmap *);
-extern int optimize_mode_switching (FILE *);
/* In predict.c */
-extern void estimate_probability (struct loops *);
-extern void expected_value_to_br_prob (void);
extern bool maybe_hot_bb_p (basic_block);
extern bool probably_cold_bb_p (basic_block);
extern bool probably_never_executed_bb_p (basic_block);
extern void rtl_predict_edge (edge, enum br_predictor, int);
extern void predict_edge_def (edge, enum br_predictor, enum prediction);
extern void guess_outgoing_edge_probabilities (basic_block);
+extern void remove_predictions_associated_with_edge (edge);
+extern bool edge_probability_reliable_p (edge);
+extern bool br_prob_note_reliable_p (rtx);
/* In flow.c */
extern void init_flow (void);
extern basic_block force_nonfallthru (edge);
extern rtx block_label (basic_block);
extern bool forwarder_block_p (basic_block);
-extern bool purge_all_dead_edges (int);
+extern bool purge_all_dead_edges (void);
extern bool purge_dead_edges (basic_block);
-extern void find_sub_basic_blocks (basic_block);
extern void find_many_sub_basic_blocks (sbitmap);
-extern void rtl_make_eh_edge (sbitmap *, basic_block, rtx);
+extern void rtl_make_eh_edge (sbitmap, basic_block, rtx);
extern bool can_fallthru (basic_block, basic_block);
extern bool could_fall_through (basic_block, basic_block);
extern void flow_nodes_print (const char *, const sbitmap, FILE *);
extern bool delete_unreachable_blocks (void);
extern bool merge_seq_blocks (void);
-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, nonzero to halt enumeration. */
-typedef int (*conflict_graph_enum_fn) (int, int, void *);
-
-
-/* Prototypes of operations on conflict graphs. */
-
-extern conflict_graph conflict_graph_new
- (int);
-extern void conflict_graph_delete (conflict_graph);
-extern int conflict_graph_add (conflict_graph, int, int);
-extern int conflict_graph_conflict_p (conflict_graph, int, int);
-extern void conflict_graph_enum (conflict_graph, int, conflict_graph_enum_fn,
- void *);
-extern void conflict_graph_merge_regs (conflict_graph, int, int);
-extern void conflict_graph_print (conflict_graph, FILE*);
extern bool mark_dfs_back_edges (void);
extern void set_edge_can_fallthru_flag (void);
extern void update_br_prob_note (basic_block);
extern void fixup_abnormal_edges (void);
extern bool inside_basic_block_p (rtx);
extern bool control_flow_insn_p (rtx);
+extern rtx get_last_bb_insn (basic_block);
/* In bb-reorder.c */
-extern void reorder_basic_blocks (unsigned int);
-extern void duplicate_computed_gotos (void);
-extern void partition_hot_cold_basic_blocks (void);
-
-/* In cfg.c */
-extern void alloc_rbi_pool (void);
-extern void initialize_bb_rbi (basic_block bb);
-extern void free_rbi_pool (void);
+extern void reorder_basic_blocks (void);
/* In dominance.c */
extern void free_dominance_info (enum cdi_direction);
extern basic_block nearest_common_dominator (enum cdi_direction,
basic_block, basic_block);
+extern basic_block nearest_common_dominator_for_set (enum cdi_direction,
+ bitmap);
extern void set_immediate_dominator (enum cdi_direction, basic_block,
basic_block);
extern basic_block get_immediate_dominator (enum cdi_direction, basic_block);
extern void verify_dominators (enum cdi_direction);
extern basic_block first_dom_son (enum cdi_direction, basic_block);
extern basic_block next_dom_son (enum cdi_direction, basic_block);
+unsigned bb_dom_dfs_in (enum cdi_direction, basic_block);
+unsigned bb_dom_dfs_out (enum cdi_direction, basic_block);
+
extern edge try_redirect_by_replacing_jump (edge, basic_block, bool);
extern void break_superblocks (void);
+extern void relink_block_chain (bool);
extern void check_bb_profile (basic_block, FILE *);
extern void update_bb_profile_for_threading (basic_block, int, gcov_type, edge);
+extern void init_rtl_bb_info (basic_block);
+
+extern void initialize_original_copy_tables (void);
+extern void free_original_copy_tables (void);
+extern void set_bb_original (basic_block, basic_block);
+extern basic_block get_bb_original (basic_block);
+extern void set_bb_copy (basic_block, basic_block);
+extern basic_block get_bb_copy (basic_block);
+
+extern rtx insert_insn_end_bb_new (rtx, basic_block);
#include "cfghooks.h"
+/* In struct-equiv.c */
+
+/* Constants used to size arrays in struct equiv_info (currently only one).
+ When these limits are exceeded, struct_equiv returns zero.
+ The maximum number of pseudo registers that are different in the two blocks,
+ but appear in equivalent places and are dead at the end (or where one of
+ a pair is dead at the end). */
+#define STRUCT_EQUIV_MAX_LOCAL 16
+/* The maximum number of references to an input register that struct_equiv
+ can handle. */
+
+/* Structure used to track state during struct_equiv that can be rolled
+ back when we find we can't match an insn, or if we want to match part
+ of it in a different way.
+ This information pertains to the pair of partial blocks that has been
+ matched so far. Since this pair is structurally equivalent, this is
+ conceptually just one partial block expressed in two potentially
+ different ways. */
+struct struct_equiv_checkpoint
+{
+ int ninsns; /* Insns are matched so far. */
+ int local_count; /* Number of block-local registers. */
+ int input_count; /* Number of inputs to the block. */
+
+ /* X_START and Y_START are the first insns (in insn stream order)
+ of the partial blocks that have been considered for matching so far.
+ Since we are scanning backwards, they are also the instructions that
+ are currently considered - or the last ones that have been considered -
+ for matching (Unless we tracked back to these because a preceding
+ instruction failed to match). */
+ rtx x_start, y_start;
+
+ /* INPUT_VALID indicates if we have actually set up X_INPUT / Y_INPUT
+ during the current pass; we keep X_INPUT / Y_INPUT around between passes
+ so that we can match REG_EQUAL / REG_EQUIV notes referring to these. */
+ bool input_valid;
+
+ /* Some information would be expensive to exactly checkpoint, so we
+ merely increment VERSION any time information about local
+ registers, inputs and/or register liveness changes. When backtracking,
+ it is decremented for changes that can be undone, and if a discrepancy
+ remains, NEED_RERUN in the relevant struct equiv_info is set to indicate
+ that a new pass should be made over the entire block match to get
+ accurate register information. */
+ int version;
+};
+
+/* A struct equiv_info is used to pass information to struct_equiv and
+ to gather state while two basic blocks are checked for structural
+ equivalence. */
+
+struct equiv_info
+{
+ /* Fields set up by the caller to struct_equiv_block_eq */
+
+ basic_block x_block, y_block; /* The two blocks being matched. */
+
+ /* MODE carries the mode bits from cleanup_cfg if we are called from
+ try_crossjump_to_edge, and additionally it carries the
+ STRUCT_EQUIV_* bits described above. */
+ int mode;
+
+ /* INPUT_COST is the cost that adding an extra input to the matched blocks
+ is supposed to have, and is taken into account when considering if the
+ matched sequence should be extended backwards. input_cost < 0 means
+ don't accept any inputs at all. */
+ int input_cost;
+
+
+ /* Fields to track state inside of struct_equiv_block_eq. Some of these
+ are also outputs. */
+
+ /* X_INPUT and Y_INPUT are used by struct_equiv to record a register that
+ is used as an input parameter, i.e. where different registers are used
+ as sources. This is only used for a register that is live at the end
+ of the blocks, or in some identical code at the end of the blocks;
+ Inputs that are dead at the end go into X_LOCAL / Y_LOCAL. */
+ rtx x_input, y_input;
+ /* When a previous pass has identified a valid input, INPUT_REG is set
+ by struct_equiv_block_eq, and it is henceforth replaced in X_BLOCK
+ for the input. */
+ rtx input_reg;
+
+ /* COMMON_LIVE keeps track of the registers which are currently live
+ (as we scan backwards from the end) and have the same numbers in both
+ blocks. N.B. a register that is in common_live is unsuitable to become
+ a local reg. */
+ regset common_live;
+ /* Likewise, X_LOCAL_LIVE / Y_LOCAL_LIVE keep track of registers that are
+ local to one of the blocks; these registers must not be accepted as
+ identical when encountered in both blocks. */
+ regset x_local_live, y_local_live;
+
+ /* EQUIV_USED indicates for which insns a REG_EQUAL or REG_EQUIV note is
+ being used, to avoid having to backtrack in the next pass, so that we
+ get accurate life info for this insn then. For each such insn,
+ the bit with the number corresponding to the CUR.NINSNS value at the
+ time of scanning is set. */
+ bitmap equiv_used;
+
+ /* Current state that can be saved & restored easily. */
+ struct struct_equiv_checkpoint cur;
+ /* BEST_MATCH is used to store the best match so far, weighing the
+ cost of matched insns COSTS_N_INSNS (CUR.NINSNS) against the cost
+ CUR.INPUT_COUNT * INPUT_COST of setting up the inputs. */
+ struct struct_equiv_checkpoint best_match;
+ /* If a checkpoint restore failed, or an input conflict newly arises,
+ NEED_RERUN is set. This has to be tested by the caller to re-run
+ the comparison if the match appears otherwise sound. The state kept in
+ x_start, y_start, equiv_used and check_input_conflict ensures that
+ we won't loop indefinitely. */
+ bool need_rerun;
+ /* If there is indication of an input conflict at the end,
+ CHECK_INPUT_CONFLICT is set so that we'll check for input conflicts
+ for each insn in the next pass. This is needed so that we won't discard
+ a partial match if there is a longer match that has to be abandoned due
+ to an input conflict. */
+ bool check_input_conflict;
+ /* HAD_INPUT_CONFLICT is set if CHECK_INPUT_CONFLICT was already set and we
+ have passed a point where there were multiple dying inputs. This helps
+ us decide if we should set check_input_conflict for the next pass. */
+ bool had_input_conflict;
+
+ /* LIVE_UPDATE controls if we want to change any life info at all. We
+ set it to false during REG_EQUAL / REG_EUQIV note comparison of the final
+ pass so that we don't introduce new registers just for the note; if we
+ can't match the notes without the current register information, we drop
+ them. */
+ bool live_update;
+
+ /* X_LOCAL and Y_LOCAL are used to gather register numbers of register pairs
+ that are local to X_BLOCK and Y_BLOCK, with CUR.LOCAL_COUNT being the index
+ to the next free entry. */
+ rtx x_local[STRUCT_EQUIV_MAX_LOCAL], y_local[STRUCT_EQUIV_MAX_LOCAL];
+ /* LOCAL_RVALUE is nonzero if the corresponding X_LOCAL / Y_LOCAL entry
+ was a source operand (including STRICT_LOW_PART) for the last invocation
+ of struct_equiv mentioning it, zero if it was a destination-only operand.
+ Since we are scanning backwards, this means the register is input/local
+ for the (partial) block scanned so far. */
+ bool local_rvalue[STRUCT_EQUIV_MAX_LOCAL];
+
+
+ /* Additional fields that are computed for the convenience of the caller. */
+
+ /* DYING_INPUTS is set to the number of local registers that turn out
+ to be inputs to the (possibly partial) block. */
+ int dying_inputs;
+ /* X_END and Y_END are the last insns in X_BLOCK and Y_BLOCK, respectively,
+ that are being compared. A final jump insn will not be included. */
+ rtx x_end, y_end;
+
+ /* If we are matching tablejumps, X_LABEL in X_BLOCK corresponds to
+ Y_LABEL in Y_BLOCK. */
+ rtx x_label, y_label;
+
+};
+
+extern bool insns_match_p (rtx, rtx, struct equiv_info *);
+extern int struct_equiv_block_eq (int, struct equiv_info *);
+extern bool struct_equiv_init (int, struct equiv_info *);
+extern bool rtx_equiv_p (rtx *, rtx, int, struct equiv_info *);
+
+/* In cfgrtl.c */
+extern bool condjump_equiv_p (struct equiv_info *, bool);
+
+/* Return true when one of the predecessor edges of BB is marked with EDGE_EH. */
+static inline bool bb_has_eh_pred (basic_block bb)
+{
+ edge e;
+ edge_iterator ei;
+
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ {
+ if (e->flags & EDGE_EH)
+ return true;
+ }
+ return false;
+}
+
#endif /* GCC_BASIC_BLOCK_H */