[gcc.git] / gcc / basic-block.h

/* Define control and data flow tables, and regsets.
   Copyright (C) 1987, 1997, 1998, 1999, 2000 Free Software Foundation, Inc.

This file is part of GNU CC.

GNU CC is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.

GNU CC is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with GNU CC; see the file COPYING.  If not, write to
the Free Software Foundation, 59 Temple Place - Suite 330,
Boston, MA 02111-1307, USA.  */

#ifndef _BASIC_BLOCK_H
#define _BASIC_BLOCK_H 1

#include "bitmap.h"
#include "sbitmap.h"
#include "varray.h"
#include "partition.h"

/* Head of register set linked list.  */
typedef bitmap_head regset_head;
/* A pointer to a regset_head.  */
typedef bitmap regset;

/* Initialize a new regset.  */
#define INIT_REG_SET(HEAD) bitmap_initialize (HEAD)

/* Clear a register set by freeing up the linked list.  */
#define CLEAR_REG_SET(HEAD) bitmap_clear (HEAD)

/* Copy a register set to another register set.  */
#define COPY_REG_SET(TO, FROM) bitmap_copy (TO, FROM)

/* Compare two register sets.  */
#define REG_SET_EQUAL_P(A, B) bitmap_equal_p (A, B)

/* `and' a register set with a second register set.  */
#define AND_REG_SET(TO, FROM) bitmap_operation (TO, TO, FROM, BITMAP_AND)

/* `and' the complement of a register set with a register set.  */
#define AND_COMPL_REG_SET(TO, FROM) \
  bitmap_operation (TO, TO, FROM, BITMAP_AND_COMPL)

/* Inclusive or a register set with a second register set.  */
#define IOR_REG_SET(TO, FROM) bitmap_operation (TO, TO, FROM, BITMAP_IOR)

/* Exclusive or a register set with a second register set.  */
#define XOR_REG_SET(TO, FROM) bitmap_operation (TO, TO, FROM, BITMAP_XOR)

/* Or into TO the register set FROM1 `and'ed with the complement of FROM2.  */
#define IOR_AND_COMPL_REG_SET(TO, FROM1, FROM2) \
  bitmap_ior_and_compl (TO, FROM1, FROM2)

/* Clear a single register in a register set.  */
#define CLEAR_REGNO_REG_SET(HEAD, REG) bitmap_clear_bit (HEAD, REG)

/* Set a single register in a register set.  */
#define SET_REGNO_REG_SET(HEAD, REG) bitmap_set_bit (HEAD, REG)

/* Return true if a register is set in a register set.  */
#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 {									\
  CLEAR_HARD_REG_SET (TO);						\
  reg_set_to_hard_reg_set (&TO, FROM);					\
} while (0)

/* Loop over all registers in REGSET, starting with MIN, setting REGNUM to the
   register number and executing CODE for all registers that are set. */
#define EXECUTE_IF_SET_IN_REG_SET(REGSET, MIN, REGNUM, CODE)		\
  EXECUTE_IF_SET_IN_BITMAP (REGSET, MIN, REGNUM, CODE)

/* Loop over all registers in REGSET1 and REGSET2, starting with MIN, setting
   REGNUM to the register number and executing CODE for all registers that are
   set in the first regset and not set in the second. */
#define EXECUTE_IF_AND_COMPL_IN_REG_SET(REGSET1, REGSET2, MIN, REGNUM, CODE) \
  EXECUTE_IF_AND_COMPL_IN_BITMAP (REGSET1, REGSET2, MIN, REGNUM, CODE)

/* Loop over all registers in REGSET1 and REGSET2, starting with MIN, setting
   REGNUM to the register number and executing CODE for all registers that are
   set in both regsets. */
#define EXECUTE_IF_AND_IN_REG_SET(REGSET1, REGSET2, MIN, REGNUM, CODE) \
  EXECUTE_IF_AND_IN_BITMAP (REGSET1, REGSET2, MIN, REGNUM, CODE)

/* Allocate a register set with oballoc.  */
#define OBSTACK_ALLOC_REG_SET(OBSTACK) BITMAP_OBSTACK_ALLOC (OBSTACK)

/* 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)

/* Do any one-time initializations needed for regsets.  */
#define INIT_ONCE_REG_SET() BITMAP_INIT_ONCE ()

/* 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) 

/* Control flow edge information.  */
typedef struct edge_def {
  /* Links through the predecessor and successor lists.  */
  struct edge_def *pred_next, *succ_next;

  /* The two blocks at the ends of the edge.  */
  struct basic_block_def *src, *dest;

  /* Instructions queued on the edge.  */
  rtx insns;

  /* Auxiliary info specific to a pass.  */
  void *aux;

  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_CRITICAL		2
#define EDGE_ABNORMAL		4
#define EDGE_ABNORMAL_CALL	8
#define EDGE_EH			16
#define EDGE_FAKE		32

#define EDGE_COMPLEX	(EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_EH)


/* Basic block information indexed by block number.  */
typedef struct basic_block_def {
  /* The first and last insns of the block.  */
  rtx head, end;

  /* 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.  */
  regset local_set;
  regset global_live_at_start;
  regset global_live_at_end;

  /* Auxiliary info specific to a pass.  */
  void *aux;

  /* The index of this block.  */
  int index;
  /* The loop depth of this block plus one.  */
  int loop_depth;

  /* The active eh region before head and after end.  */
  int eh_beg, eh_end;

  int count;		/* Expected number of executions: calculated in
                           profile.c */
} *basic_block;

/* Number of basic blocks in the current function.  */

extern int n_basic_blocks;

/* Number of edges in the current function.  */

extern int n_edges;

/* Index by basic block number, get basic block struct info.  */

extern varray_type basic_block_info;

#define BASIC_BLOCK(N)  (VARRAY_BB (basic_block_info, (N)))

/* What registers are live at the setjmp call.  */

extern regset regs_live_at_setjmp;

/* Indexed by n, gives number of basic block that  (REG n) is used in.
   If the value is REG_BLOCK_GLOBAL (-2),
   it means (REG n) is used in more than one basic block.
   REG_BLOCK_UNKNOWN (-1) means it hasn't been seen yet so we don't know.
   This information remains valid for the rest of the compilation
   of the current function; it is used to control register allocation.  */

#define REG_BLOCK_UNKNOWN -1
#define REG_BLOCK_GLOBAL -2

#define REG_BASIC_BLOCK(N) (VARRAY_REG (reg_n_info, N)->basic_block)
\f
/* Stuff for recording basic block info.  */

#define BLOCK_HEAD(B)      (BASIC_BLOCK (B)->head)
#define BLOCK_END(B)       (BASIC_BLOCK (B)->end)

/* Special block numbers [markers] for entry and exit.  */
#define ENTRY_BLOCK (-1)
#define EXIT_BLOCK (-2)

/* 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 EXIT_BLOCK_PTR	(&entry_exit_blocks[1])

extern varray_type basic_block_for_insn;
#define BLOCK_FOR_INSN(INSN)  VARRAY_BB (basic_block_for_insn, INSN_UID (INSN))
#define BLOCK_NUM(INSN)	      (BLOCK_FOR_INSN (INSN)->index + 0)

extern void compute_bb_for_insn		PARAMS ((int));
extern void set_block_for_insn		PARAMS ((rtx, basic_block));
extern void set_block_num		PARAMS ((rtx, int));

extern void free_basic_block_vars	PARAMS ((int));

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 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
{
  int num;

  /* Basic block of loop header.  */
  basic_block header;

  /* Basic block of loop latch.  */
  basic_block latch;

  /* Basic block of loop pre-header or NULL if it does not exist.  */
  basic_block pre_header;

  /* 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 exit the loop.  */
  edge *exits;

  /* Number of edges that exit the loop.  */
  int num_exits;

  /* The loop nesting depth.  */
  int depth;

  /* The height of the loop (enclosed loop levels) within the loop
     hierarchy tree.  */
  int level;

  /* The outer (parent) loop or NULL if outermost loop.  */
  struct loop *outer;

  /* The first inner (child) loop or NULL if innermost loop.  */
  struct loop *inner;

  /* Link to the next (sibling) loop.  */
  struct loop *next;

  /* Non-zero if the loop shares a header with another loop.  */
  int shared;

  /* Non-zero if the loop is invalid (e.g., contains setjmp.).  */
  int invalid;

  /* Auxiliary info specific to a pass.  */
  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;

  /* 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;
};


/* Structure to hold CFG information about natural loops within a function.  */
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;

  /* Pointer to root of loop heirachy tree.  */
  struct loop *tree;

  /* Information derived from the CFG.  */
  struct cfg
  {
    /* The bitmap vector of dominators or NULL if not computed.  */
    sbitmap *dom;

    /* The ordering of the basic blocks in a depth first search.  */
    int *dfs_order;
  } cfg;

  /* Headers shared by multiple loops that should be merged.  */
  sbitmap shared_headers;
};

extern int flow_loops_find PARAMS ((struct loops *));
extern void flow_loops_free PARAMS ((struct loops *));
extern void flow_loops_dump PARAMS ((const struct loops *, FILE *, int));


/* This structure maintains an edge list vector.  */
struct edge_list 
{
  int num_blocks;
  int num_edges;
  edge *index_to_edge;
};

/* This is the value which indicates no edge is present.  */
#define EDGE_INDEX_NO_EDGE	-1

/* EDGE_INDEX returns an integer index for an edge, or EDGE_INDEX_NO_EDGE
   if there is no edge between the 2 basic blocks.  */
#define EDGE_INDEX(el, pred, succ) (find_edge_index ((el), (pred), (succ)))

/* INDEX_EDGE_PRED_BB and INDEX_EDGE_SUCC_BB return a pointer to the basic
   block which is either the pred or succ end of the indexed edge.  */
#define INDEX_EDGE_PRED_BB(el, index)	((el)->index_to_edge[(index)]->src)
#define INDEX_EDGE_SUCC_BB(el, index)	((el)->index_to_edge[(index)]->dest)

/* INDEX_EDGE returns a pointer to the edge.  */
#define INDEX_EDGE(el, index)           ((el)->index_to_edge[(index)])

/* Number of edges in the compressed edge list.  */
#define NUM_EDGES(el)			((el)->num_edges)

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 *, 
						 basic_block, basic_block));

extern void compute_flow_dominators	PARAMS ((sbitmap *, sbitmap *));
extern void compute_immediate_dominators	PARAMS ((int *, sbitmap *));


enum update_life_extent
{
  UPDATE_LIFE_LOCAL = 0,
  UPDATE_LIFE_GLOBAL = 1,
  UPDATE_LIFE_GLOBAL_RM_NOTES = 2
};

/* Flags for life_analysis and update_life_info.  */

#define PROP_DEATH_NOTES	1	/* Create DEAD and UNUSED notes.  */
#define PROP_LOG_LINKS		2	/* Create LOG_LINKS.  */
#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.  */

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, 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, 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 *, 
						 sbitmap *, sbitmap **,
						 sbitmap **));
extern struct edge_list *pre_edge_rev_lcm PARAMS ((FILE *, int, sbitmap *,
						   sbitmap *, sbitmap *, 
						   sbitmap *, 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));
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 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));

/* 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 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;

#endif /* _BASIC_BLOCK_H */
Commit	Line	Data
3245eea0	1	/* Define control and data flow tables, and regsets.
3d994c6b	2	Copyright (C) 1987, 1997, 1998, 1999, 2000 Free Software Foundation, Inc.
3245eea0 CH	3
	4	This file is part of GNU CC.
	5
	6	GNU CC is free software; you can redistribute it and/or modify
	7	it under the terms of the GNU General Public License as published by
	8	the Free Software Foundation; either version 2, or (at your option)
	9	any later version.
	10
	11	GNU CC is distributed in the hope that it will be useful,
	12	but WITHOUT ANY WARRANTY; without even the implied warranty of
	13	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	14	GNU General Public License for more details.
	15
	16	You should have received a copy of the GNU General Public License
	17	along with GNU CC; see the file COPYING. If not, write to
940d9d63 RK	18	the Free Software Foundation, 59 Temple Place - Suite 330,
940d9d63 RK	19	Boston, MA 02111-1307, USA. */
3245eea0	20
4dc9341c MH	21	#ifndef _BASIC_BLOCK_H
4dc9341c MH	22	#define _BASIC_BLOCK_H 1
3245eea0	23
19d18142	24	#include "bitmap.h"
5f6c11d6	25	#include "sbitmap.h"
e881bb1b	26	#include "varray.h"
4e872036	27	#include "partition.h"
19d18142	28
b1dbfa1d BS	29	/* Head of register set linked list. */
	30	typedef bitmap_head regset_head;
	31	/* A pointer to a regset_head. */
	32	typedef bitmap regset;
	33
	34	/* Initialize a new regset. */
	35	#define INIT_REG_SET(HEAD) bitmap_initialize (HEAD)
19d18142 RK	36
	37	/* Clear a register set by freeing up the linked list. */
	38	#define CLEAR_REG_SET(HEAD) bitmap_clear (HEAD)
	39
	40	/* Copy a register set to another register set. */
	41	#define COPY_REG_SET(TO, FROM) bitmap_copy (TO, FROM)
	42
d3a923ee RH	43	/* Compare two register sets. */
	44	#define REG_SET_EQUAL_P(A, B) bitmap_equal_p (A, B)
	45
19d18142 RK	46	/* `and' a register set with a second register set. */
	47	#define AND_REG_SET(TO, FROM) bitmap_operation (TO, TO, FROM, BITMAP_AND)
	48
	49	/* `and' the complement of a register set with a register set. */
	50	#define AND_COMPL_REG_SET(TO, FROM) \
	51	bitmap_operation (TO, TO, FROM, BITMAP_AND_COMPL)
	52
	53	/* Inclusive or a register set with a second register set. */
	54	#define IOR_REG_SET(TO, FROM) bitmap_operation (TO, TO, FROM, BITMAP_IOR)
	55
d3a923ee RH	56	/* Exclusive or a register set with a second register set. */
	57	#define XOR_REG_SET(TO, FROM) bitmap_operation (TO, TO, FROM, BITMAP_XOR)
	58
19d18142 RK	59	/* Or into TO the register set FROM1 `and'ed with the complement of FROM2. */
	60	#define IOR_AND_COMPL_REG_SET(TO, FROM1, FROM2) \
	61	bitmap_ior_and_compl (TO, FROM1, FROM2)
916b1701 MM	62
916b1701 MM	63	/* Clear a single register in a register set. */
19d18142	64	#define CLEAR_REGNO_REG_SET(HEAD, REG) bitmap_clear_bit (HEAD, REG)
916b1701 MM	65
916b1701 MM	66	/* Set a single register in a register set. */
19d18142	67	#define SET_REGNO_REG_SET(HEAD, REG) bitmap_set_bit (HEAD, REG)
916b1701 MM	68
916b1701 MM	69	/* Return true if a register is set in a register set. */
19d18142	70	#define REGNO_REG_SET_P(TO, REG) bitmap_bit_p (TO, REG)
916b1701 MM	71
916b1701 MM	72	/* Copy the hard registers in a register set to the hard register set. */
efc9bd41	73	extern void reg_set_to_hard_reg_set PARAMS ((HARD_REG_SET *, bitmap));
916b1701 MM	74	#define REG_SET_TO_HARD_REG_SET(TO, FROM) \
916b1701 MM	75	do { \
916b1701	76	CLEAR_HARD_REG_SET (TO); \
efc9bd41	77	reg_set_to_hard_reg_set (&TO, FROM); \
916b1701 MM	78	} while (0)
	79
	80	/* Loop over all registers in REGSET, starting with MIN, setting REGNUM to the
	81	register number and executing CODE for all registers that are set. */
	82	#define EXECUTE_IF_SET_IN_REG_SET(REGSET, MIN, REGNUM, CODE) \
19d18142	83	EXECUTE_IF_SET_IN_BITMAP (REGSET, MIN, REGNUM, CODE)
916b1701 MM	84
	85	/* Loop over all registers in REGSET1 and REGSET2, starting with MIN, setting
	86	REGNUM to the register number and executing CODE for all registers that are
	87	set in the first regset and not set in the second. */
	88	#define EXECUTE_IF_AND_COMPL_IN_REG_SET(REGSET1, REGSET2, MIN, REGNUM, CODE) \
19d18142	89	EXECUTE_IF_AND_COMPL_IN_BITMAP (REGSET1, REGSET2, MIN, REGNUM, CODE)
916b1701	90
22fa5b8a MM	91	/* Loop over all registers in REGSET1 and REGSET2, starting with MIN, setting
	92	REGNUM to the register number and executing CODE for all registers that are
	93	set in both regsets. */
	94	#define EXECUTE_IF_AND_IN_REG_SET(REGSET1, REGSET2, MIN, REGNUM, CODE) \
	95	EXECUTE_IF_AND_IN_BITMAP (REGSET1, REGSET2, MIN, REGNUM, CODE)
	96
916b1701	97	/* Allocate a register set with oballoc. */
19d18142	98	#define OBSTACK_ALLOC_REG_SET(OBSTACK) BITMAP_OBSTACK_ALLOC (OBSTACK)
916b1701	99
ee25a7a5 MM	100	/* Initialize a register set. Returns the new register set. */
ee25a7a5 MM	101	#define INITIALIZE_REG_SET(HEAD) bitmap_initialize (&HEAD)
19d18142 RK	102
	103	/* Do any cleanup needed on a regset when it is no longer used. */
	104	#define FREE_REG_SET(REGSET) BITMAP_FREE(REGSET)
	105
	106	/* Do any one-time initializations needed for regsets. */
	107	#define INIT_ONCE_REG_SET() BITMAP_INIT_ONCE ()
	108
	109	/* Grow any tables needed when the number of registers is calculated
	110	or extended. For the linked list allocation, nothing needs to
	111	be done, other than zero the statistics on the first allocation. */
e881bb1b	112	#define MAX_REGNO_REG_SET(NUM_REGS, NEW_P, RENUMBER_P)
916b1701	113
e881bb1b RH	114	/* Control flow edge information. */
	115	typedef struct edge_def {
	116	/* Links through the predecessor and successor lists. */
	117	struct edge_def pred_next, succ_next;
3245eea0	118
e881bb1b RH	119	/* The two blocks at the ends of the edge. */
	120	struct basic_block_def src, dest;
	121
	122	/* Instructions queued on the edge. */
	123	rtx insns;
	124
	125	/* Auxiliary info specific to a pass. */
	126	void *aux;
3245eea0	127
e881bb1b RH	128	int flags; /* see EDGE_* below */
e881bb1b RH	129	int probability; /* biased by REG_BR_PROB_BASE */
51891abe JH	130	int count; /* Expected number of executions calculated
51891abe JH	131	in profile.c */
e881bb1b	132	} *edge;
3245eea0	133
e881bb1b RH	134	#define EDGE_FALLTHRU 1
	135	#define EDGE_CRITICAL 2
	136	#define EDGE_ABNORMAL 4
	137	#define EDGE_ABNORMAL_CALL 8
	138	#define EDGE_EH 16
	139	#define EDGE_FAKE 32
3245eea0	140
65b98a02 JW	141	#define EDGE_COMPLEX (EDGE_ABNORMAL \| EDGE_ABNORMAL_CALL \| EDGE_EH)
65b98a02 JW	142
3245eea0	143
e881bb1b RH	144	/* Basic block information indexed by block number. */
	145	typedef struct basic_block_def {
	146	/* The first and last insns of the block. */
	147	rtx head, end;
3245eea0	148
e881bb1b RH	149	/* The edges into and out of the block. */
e881bb1b RH	150	edge pred, succ;
4d1d8045	151
4e872036 AS	152	/* Liveness info. Note that in SSA form, global_live_at_start does
	153	not reflect the use of regs in phi functions, since the liveness
	154	of these regs may depend on which edge was taken into the block. */
e881bb1b RH	155	regset local_set;
	156	regset global_live_at_start;
	157	regset global_live_at_end;
4d1d8045	158
e881bb1b RH	159	/* Auxiliary info specific to a pass. */
e881bb1b RH	160	void *aux;
3245eea0	161
e881bb1b RH	162	/* The index of this block. */
	163	int index;
	164	/* The loop depth of this block plus one. */
	165	int loop_depth;
336a6399 RH	166
	167	/* The active eh region before head and after end. */
	168	int eh_beg, eh_end;
51891abe	169
f1274741 RK	170	int count; /* Expected number of executions: calculated in
f1274741 RK	171	profile.c */
e881bb1b RH	172	} *basic_block;
	173
	174	/* Number of basic blocks in the current function. */
	175
	176	extern int n_basic_blocks;
	177
d3a923ee RH	178	/* Number of edges in the current function. */
	179
	180	extern int n_edges;
	181
e881bb1b RH	182	/* Index by basic block number, get basic block struct info. */
	183
	184	extern varray_type basic_block_info;
	185
	186	#define BASIC_BLOCK(N) (VARRAY_BB (basic_block_info, (N)))
3245eea0	187
19d18142 RK	188	/* What registers are live at the setjmp call. */
	189
	190	extern regset regs_live_at_setjmp;
	191
3245eea0 CH	192	/* Indexed by n, gives number of basic block that (REG n) is used in.
	193	If the value is REG_BLOCK_GLOBAL (-2),
	194	it means (REG n) is used in more than one basic block.
	195	REG_BLOCK_UNKNOWN (-1) means it hasn't been seen yet so we don't know.
	196	This information remains valid for the rest of the compilation
	197	of the current function; it is used to control register allocation. */
	198
	199	#define REG_BLOCK_UNKNOWN -1
	200	#define REG_BLOCK_GLOBAL -2
b1f21e0a	201
6feacd09	202	#define REG_BASIC_BLOCK(N) (VARRAY_REG (reg_n_info, N)->basic_block)
5ece9746 JL	203	\f
	204	/* Stuff for recording basic block info. */
	205
e881bb1b RH	206	#define BLOCK_HEAD(B) (BASIC_BLOCK (B)->head)
e881bb1b RH	207	#define BLOCK_END(B) (BASIC_BLOCK (B)->end)
5ece9746 JL	208
	209	/* Special block numbers [markers] for entry and exit. */
	210	#define ENTRY_BLOCK (-1)
	211	#define EXIT_BLOCK (-2)
	212
e881bb1b RH	213	/* Similarly, block pointers for the edge list. */
	214	extern struct basic_block_def entry_exit_blocks[2];
	215	#define ENTRY_BLOCK_PTR (&entry_exit_blocks[0])
	216	#define EXIT_BLOCK_PTR (&entry_exit_blocks[1])
	217
e881bb1b RH	218	extern varray_type basic_block_for_insn;
	219	#define BLOCK_FOR_INSN(INSN) VARRAY_BB (basic_block_for_insn, INSN_UID (INSN))
	220	#define BLOCK_NUM(INSN) (BLOCK_FOR_INSN (INSN)->index + 0)
	221
3d994c6b KG	222	extern void compute_bb_for_insn PARAMS ((int));
	223	extern void set_block_for_insn PARAMS ((rtx, basic_block));
	224	extern void set_block_num PARAMS ((rtx, int));
e881bb1b	225
3d994c6b	226	extern void free_basic_block_vars PARAMS ((int));
52becdc0	227
3d994c6b KG	228	extern basic_block split_edge PARAMS ((edge));
	229	extern void insert_insn_on_edge PARAMS ((rtx, edge));
	230	extern void commit_edge_insertions PARAMS ((void));
	231	extern void remove_fake_edges PARAMS ((void));
	232	extern void add_noreturn_fake_exit_edges PARAMS ((void));
69732dcb	233	extern rtx flow_delete_insn PARAMS ((rtx));
3d994c6b	234	extern void flow_delete_insn_chain PARAMS ((rtx, rtx));
69732dcb RH	235	extern void make_edge PARAMS ((sbitmap *, basic_block,
	236	basic_block, int));
	237	extern void remove_edge PARAMS ((edge));
f008a564 RH	238	extern void redirect_edge_succ PARAMS ((edge, basic_block));
f008a564 RH	239	extern void redirect_edge_pred PARAMS ((edge, basic_block));
295ae817	240	extern void create_basic_block PARAMS ((int, rtx, rtx, rtx));
52294521	241	extern int flow_delete_block PARAMS ((basic_block));
dc108b7a RH	242	extern void merge_blocks_nomove PARAMS ((basic_block, basic_block));
	243	extern void tidy_fallthru_edge PARAMS ((edge, basic_block,
	244	basic_block));
4dc9341c MH	245
	246	/* Structure to hold information for each natural loop. */
	247	struct loop
	248	{
	249	int num;
	250
	251	/* Basic block of loop header. */
	252	basic_block header;
	253
	254	/* Basic block of loop latch. */
	255	basic_block latch;
	256
	257	/* Basic block of loop pre-header or NULL if it does not exist. */
	258	basic_block pre_header;
	259
65169dcf JE	260	/* The first block in the loop. This is not necessarily the same as
	261	the loop header. */
	262	basic_block first;
	263
	264	/* The last block in the loop. This is not necessarily the same as
	265	the loop latch. */
	266	basic_block last;
	267
4dc9341c MH	268	/* Bitmap of blocks contained within the loop. */
	269	sbitmap nodes;
	270
	271	/* Number of blocks contained within the loop. */
	272	int num_nodes;
	273
	274	/* Array of edges that exit the loop. */
	275	edge *exits;
	276
	277	/* Number of edges that exit the loop. */
	278	int num_exits;
	279
	280	/* The loop nesting depth. */
	281	int depth;
	282
	283	/* The height of the loop (enclosed loop levels) within the loop
	284	hierarchy tree. */
	285	int level;
	286
	287	/* The outer (parent) loop or NULL if outermost loop. */
	288	struct loop *outer;
	289
	290	/* The first inner (child) loop or NULL if innermost loop. */
	291	struct loop *inner;
	292
	293	/* Link to the next (sibling) loop. */
	294	struct loop *next;
	295
	296	/* Non-zero if the loop shares a header with another loop. */
	297	int shared;
	298
	299	/* Non-zero if the loop is invalid (e.g., contains setjmp.). */
	300	int invalid;
	301
	302	/* Auxiliary info specific to a pass. */
52b38064	303	void *aux;
a2be868f MH	304
	305	/* The following are currently used by loop.c but they are likely to
	306	disappear as loop.c is converted to use the CFG. */
	307
	308	/* Non-zero if the loop has a NOTE_INSN_LOOP_VTOP. */
	309	rtx vtop;
	310
	311	/* Non-zero if the loop has a NOTE_INSN_LOOP_CONT.
	312	A continue statement will generate a branch to NEXT_INSN (cont). */
	313	rtx cont;
	314
	315	/* The dominator of cont. */
	316	rtx cont_dominator;
	317
	318	/* The NOTE_INSN_LOOP_BEG. */
	319	rtx start;
	320
	321	/* The NOTE_INSN_LOOP_END. */
	322	rtx end;
	323
	324	/* For a rotated loop that is entered near the bottom,
	325	this is the label at the top. Otherwise it is zero. */
	326	rtx top;
	327
	328	/* Place in the loop where control enters. */
	329	rtx scan_start;
	330
	331	/* List of all LABEL_REFs which refer to code labels outside the
	332	loop. Used by routines that need to know all loop exits, such as
	333	final_biv_value and final_giv_value.
	334
	335	This does not include loop exits due to return instructions.
	336	This is because all bivs and givs are pseudos, and hence must be
	337	dead after a return, so the presense of a return does not affect
	338	any of the optimizations that use this info. It is simpler to
	339	just not include return instructions on this list. */
	340	rtx exit_labels;
	341
	342	/* The number of LABEL_REFs on exit_labels for this loop and all
	343	loops nested inside it. */
	344	int exit_count;
4dc9341c MH	345	};
	346
	347
	348	/* Structure to hold CFG information about natural loops within a function. */
	349	struct loops
	350	{
	351	/* Number of natural loops in the function. */
	352	int num;
	353
d6181b1b MH	354	/* Maxium nested loop level in the function. */
	355	int levels;
	356
4dc9341c MH	357	/* Array of natural loop descriptors (scanning this array in reverse order
	358	will find the inner loops before their enclosing outer loops). */
	359	struct loop *array;
	360
	361	/* Pointer to root of loop heirachy tree. */
	362	struct loop *tree;
	363
	364	/* Information derived from the CFG. */
	365	struct cfg
	366	{
	367	/* The bitmap vector of dominators or NULL if not computed. */
	368	sbitmap *dom;
	369
	370	/* The ordering of the basic blocks in a depth first search. */
	371	int *dfs_order;
	372	} cfg;
	373
	374	/* Headers shared by multiple loops that should be merged. */
	375	sbitmap shared_headers;
	376	};
	377
3d994c6b KG	378	extern int flow_loops_find PARAMS ((struct loops *));
	379	extern void flow_loops_free PARAMS ((struct loops *));
	380	extern void flow_loops_dump PARAMS ((const struct loops , FILE , int));
4dc9341c MH	381
4dc9341c MH	382
410538ea AM	383	/* This structure maintains an edge list vector. */
	384	struct edge_list
	385	{
	386	int num_blocks;
	387	int num_edges;
	388	edge *index_to_edge;
	389	};
	390
	391	/* This is the value which indicates no edge is present. */
	392	#define EDGE_INDEX_NO_EDGE -1
	393
	394	/* EDGE_INDEX returns an integer index for an edge, or EDGE_INDEX_NO_EDGE
	395	if there is no edge between the 2 basic blocks. */
	396	#define EDGE_INDEX(el, pred, succ) (find_edge_index ((el), (pred), (succ)))
	397
	398	/* INDEX_EDGE_PRED_BB and INDEX_EDGE_SUCC_BB return a pointer to the basic
	399	block which is either the pred or succ end of the indexed edge. */
	400	#define INDEX_EDGE_PRED_BB(el, index) ((el)->index_to_edge[(index)]->src)
	401	#define INDEX_EDGE_SUCC_BB(el, index) ((el)->index_to_edge[(index)]->dest)
	402
	403	/* INDEX_EDGE returns a pointer to the edge. */
	404	#define INDEX_EDGE(el, index) ((el)->index_to_edge[(index)])
	405
	406	/* Number of edges in the compressed edge list. */
	407	#define NUM_EDGES(el) ((el)->num_edges)
	408
3d994c6b KG	409	struct edge_list * create_edge_list PARAMS ((void));
	410	void free_edge_list PARAMS ((struct edge_list *));
	411	void print_edge_list PARAMS ((FILE , struct edge_list ));
	412	void verify_edge_list PARAMS ((FILE , struct edge_list ));
	413	int find_edge_index PARAMS ((struct edge_list *,
	414	basic_block, basic_block));
410538ea	415
3d994c6b KG	416	extern void compute_flow_dominators PARAMS ((sbitmap , sbitmap ));
3d994c6b KG	417	extern void compute_immediate_dominators PARAMS ((int , sbitmap ));
077692c6	418
49c3bb12	419
d3a923ee RH	420	enum update_life_extent
d3a923ee RH	421	{
715e7fbc RH	422	UPDATE_LIFE_LOCAL = 0,
715e7fbc RH	423	UPDATE_LIFE_GLOBAL = 1,
5a425893	424	UPDATE_LIFE_GLOBAL_RM_NOTES = 2
d3a923ee RH	425	};
d3a923ee RH	426
49c3bb12 RH	427	/* Flags for life_analysis and update_life_info. */
	428
	429	#define PROP_DEATH_NOTES 1 /* Create DEAD and UNUSED notes. */
	430	#define PROP_LOG_LINKS 2 /* Create LOG_LINKS. */
	431	#define PROP_REG_INFO 4 /* Update regs_ever_live et al. */
	432	#define PROP_KILL_DEAD_CODE 8 /* Remove dead code. */
	433	#define PROP_SCAN_DEAD_CODE 16 /* Scan for dead code. */
	434	#define PROP_AUTOINC 32 /* Create autoinc mem references. */
	435	#define PROP_FINAL 63 /* All of the above. */
	436
7f8a79ba	437	extern void life_analysis PARAMS ((rtx, FILE *, int));
3d994c6b KG	438	extern void update_life_info PARAMS ((sbitmap, enum update_life_extent,
	439	int));
	440	extern int count_or_remove_death_notes PARAMS ((sbitmap, int));
292f3869 RH	441	extern void propagate_block PARAMS ((basic_block, regset, regset, int));
	442
	443	struct propagate_block_info;
	444	extern rtx propagate_one_insn PARAMS ((struct propagate_block_info *, rtx));
	445	extern struct propagate_block_info *init_propagate_block_info
	446	PARAMS ((basic_block, regset, regset, int));
	447	extern void free_propagate_block_info PARAMS ((struct propagate_block_info *));
d3a923ee	448
077692c6	449	/* In lcm.c */
3d994c6b KG	450	extern struct edge_list pre_edge_lcm PARAMS ((FILE , int, sbitmap *,
	451	sbitmap , sbitmap ,
	452	sbitmap , sbitmap *,
	453	sbitmap **));
	454	extern struct edge_list pre_edge_rev_lcm PARAMS ((FILE , int, sbitmap *,
	455	sbitmap , sbitmap ,
	456	sbitmap , sbitmap *,
	457	sbitmap **));
	458	extern void compute_available PARAMS ((sbitmap , sbitmap ,
	459	sbitmap , sbitmap ));
97d36f45	460	extern int optimize_mode_switching PARAMS ((FILE *));
a05924f9 JH	461
a05924f9 JH	462	/* In emit-rtl.c. */
3d994c6b KG	463	extern rtx emit_block_insn_after PARAMS ((rtx, rtx, basic_block));
3d994c6b KG	464	extern rtx emit_block_insn_before PARAMS ((rtx, rtx, basic_block));
4dc9341c	465
f1ebdfc5 JE	466	/* In predict.c */
f1ebdfc5 JE	467	extern void estimate_probability PARAMS ((struct loops *));
994a57cd	468	extern void expected_value_to_br_prob PARAMS ((void));
f1ebdfc5	469
11bdd2ae SC	470	/* In flow.c */
11bdd2ae SC	471	extern void reorder_basic_blocks PARAMS ((void));
b7ba4d8d ZW	472	extern void dump_bb PARAMS ((basic_block, FILE *));
	473	extern void debug_bb PARAMS ((basic_block));
	474	extern void debug_bb_n PARAMS ((int));
	475	extern void dump_regset PARAMS ((regset, FILE *));
	476	extern void debug_regset PARAMS ((regset));
11bdd2ae	477
5b99e449 JL	478	/* This function is always defined so it can be called from the
	479	debugger, and it is declared extern so we don't get warnings about
	480	it being unused. */
	481	extern void verify_flow_info PARAMS ((void));
	482	extern int flow_loop_outside_edge_p PARAMS ((const struct loop *, edge));
	483
4e872036 AS	484	typedef struct conflict_graph_def *conflict_graph;
	485
	486	/* Callback function when enumerating conflicts. The arguments are
	487	the smaller and larger regno in the conflict. Returns zero if
	488	enumeration is to continue, non-zero to halt enumeration. */
b0340202	489	typedef int (conflict_graph_enum_fn) PARAMS ((int, int, void ));
4e872036 AS	490
	491
	492	/* Prototypes of operations on conflict graphs. */
	493
	494	extern conflict_graph conflict_graph_new
	495	PARAMS ((int));
	496	extern void conflict_graph_delete PARAMS ((conflict_graph));
	497	extern int conflict_graph_add PARAMS ((conflict_graph,
	498	int, int));
	499	extern int conflict_graph_conflict_p PARAMS ((conflict_graph,
	500	int, int));
	501	extern void conflict_graph_enum PARAMS ((conflict_graph, int,
	502	conflict_graph_enum_fn,
	503	void *));
	504	extern void conflict_graph_merge_regs PARAMS ((conflict_graph, int,
	505	int));
	506	extern void conflict_graph_print PARAMS ((conflict_graph, FILE*));
	507	extern conflict_graph conflict_graph_compute
	508	PARAMS ((regset,
	509	partition));
11bdd2ae	510
6308dae9 AS	511	/* In ssa.c */
	512	extern void convert_to_ssa PARAMS ((void));
	513	extern void convert_from_ssa PARAMS ((void));
	514	typedef int (successor_phi_fn) PARAMS ((rtx, int, int, void ));
	515	extern int for_each_successor_phi PARAMS ((basic_block bb,
	516	successor_phi_fn,
	517	void *));
	518	extern int in_ssa_form;
	519
4dc9341c	520	#endif /* _BASIC_BLOCK_H */