[thirdparty/gcc.git] / gcc / cfgloop.h

/* Natural loop functions
   Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2002, 2003
   Free Software Foundation, Inc.

This file is part of GCC.

GCC 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.

GCC 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 GCC; see the file COPYING.  If not, write to the Free
Software Foundation, 59 Temple Place - Suite 330, Boston, MA
02111-1307, USA.  */

/* Structure to hold decision about unrolling/peeling.  */
enum lpt_dec
{
  LPT_NONE,
  LPT_PEEL_COMPLETELY,
  LPT_PEEL_SIMPLE,
  LPT_UNROLL_CONSTANT,
  LPT_UNROLL_RUNTIME,
  LPT_UNROLL_STUPID
};

struct lpt_decision
{
  enum lpt_dec decision;
  unsigned times;
};

/* Description of loop for simple loop unrolling.  */
struct loop_desc
{
  int postincr;		/* 1 if increment/decrement is done after loop exit condition.  */
  rtx stride;		/* Value added to VAR in each iteration.  */
  rtx var;		/* Loop control variable.  */
  rtx var_alts;		/* List of definitions of its initial value.  */
  rtx lim;		/* Expression var is compared with.  */
  rtx lim_alts;		/* List of definitions of its initial value.  */
  bool const_iter;      /* True if it iterates constant number of times.  */
  unsigned HOST_WIDE_INT niter;
			/* Number of iterations if it is constant.  */
  bool may_be_zero;     /* If we cannot determine that the first iteration will pass.  */
  enum rtx_code cond;	/* Exit condition.  */
  int neg;		/* Set to 1 if loop ends when condition is satisfied.  */
  edge out_edge;	/* The exit edge.  */
  edge in_edge;		/* And the other one.  */
  int n_branches;	/* Number of branches inside the loop.  */
};

/* Structure to hold information for each natural loop.  */
struct loop
{
  /* Index into loops array.  */
  int num;

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

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

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

  /* For loop unrolling/peeling decision.  */
  struct lpt_decision lpt_decision;

  /* Simple loop description.  */
  int simple;
  struct loop_desc desc;
  int has_desc;

  /* Number of loop insns.  */
  unsigned ninsns;

  /* Average number of executed insns per iteration.  */
  unsigned av_ninsns;

  /* Array of edges along the preheader extended basic block trace.
     The source of the first edge is the root node of preheader
     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.  */
  unsigned 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 *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;

  /* Superloops of the loop.  */
  struct loop **pred;

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

  /* Loop that is copy of this loop.  */
  struct loop *copy;

  /* Nonzero 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.  */

  /* Nonzero if the loop has a NOTE_INSN_LOOP_VTOP.  */
  rtx vtop;

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

/* Flags for state of loop structure.  */
enum
{
  LOOPS_HAVE_PREHEADERS = 1,
  LOOPS_HAVE_SIMPLE_LATCHES = 2,
  LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS = 4
};

/* Structure to hold CFG information about natural loops within a function.  */
struct loops
{
  /* Number of natural loops in the function.  */
  unsigned num;

  /* Maximum nested loop level in the function.  */
  unsigned 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 above array is unused in new loop infrastructure and is kept only for
     purposes of the old loop optimizer.  Instead we store just pointers to
     loops here.  */
  struct loop **parray;

  /* Pointer to root of loop hierarchy tree.  */
  struct loop *tree_root;

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

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

  /* State of loops.  */
  int state;
};

/* Flags for loop discovery.  */

#define LOOP_TREE		1	/* Build loop hierarchy tree.  */
#define LOOP_PRE_HEADER		2	/* Analyze loop preheader.  */
#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_ALL	       15	/* All of the above  */

/* Loop recognition.  */
extern int flow_loops_find (struct loops *, int flags);
extern int flow_loops_update (struct loops *, int flags);
extern void flow_loops_free (struct loops *);
extern void flow_loops_dump (const struct loops *, FILE *,
			     void (*)(const struct loop *, FILE *, int), int);
extern void flow_loop_dump (const struct loop *, FILE *,
			    void (*)(const struct loop *, FILE *, int), int);
extern int flow_loop_scan (struct loops *, struct loop *, int);
extern void flow_loop_free (struct loop *);
void mark_irreducible_loops (struct loops *);

/* Loop datastructure manipulation/querying.  */
extern void flow_loop_tree_node_add (struct loop *, struct loop *);
extern void flow_loop_tree_node_remove (struct loop *);
extern bool flow_loop_outside_edge_p (const struct loop *, edge);
extern bool flow_loop_nested_p	(const struct loop *, const struct loop *);
extern bool flow_bb_inside_loop_p (const struct loop *, const basic_block);
extern struct loop * find_common_loop (struct loop *, struct loop *);
extern int num_loop_insns (struct loop *);
extern int average_num_loop_insns (struct loop *);

/* Loops & cfg manipulation.  */
extern basic_block *get_loop_body (const struct loop *);
extern edge *get_loop_exit_edges (const struct loop *, unsigned *);

extern edge loop_preheader_edge (const struct loop *);
extern edge loop_latch_edge (const struct loop *);

extern void add_bb_to_loop (basic_block, struct loop *);
extern void remove_bb_from_loops (basic_block);

extern void cancel_loop (struct loops *, struct loop *);
extern void cancel_loop_tree (struct loops *, struct loop *);

extern basic_block loop_split_edge_with (edge, rtx, struct loops *);
extern int fix_loop_placement (struct loop *);

enum
{
  CP_SIMPLE_PREHEADERS = 1
};

extern void create_preheaders (struct loops *, int);
extern void force_single_succ_latches (struct loops *);

extern void verify_loop_structure (struct loops *);

/* Loop analysis.  */
extern bool simple_loop_p (struct loops *, struct loop *, struct loop_desc *);
extern rtx count_loop_iterations (struct loop_desc *, rtx, rtx);
extern bool just_once_each_iteration_p (struct loops *,struct loop *,
					basic_block);
extern unsigned expected_loop_iterations (const struct loop *);

/* Loop manipulation.  */
extern bool can_duplicate_loop_p (struct loop *loop);

#define DLTHE_FLAG_UPDATE_FREQ	1	/* Update frequencies in
					   duplicate_loop_to_header_edge.  */

extern int duplicate_loop_to_header_edge (struct loop *, edge, struct loops *,
					  unsigned, sbitmap, edge, edge *,
					  unsigned *, int);
extern struct loop *loopify (struct loops *, edge, edge, basic_block);
extern void unloop (struct loops *, struct loop *);
extern bool remove_path (struct loops *, edge);
extern edge split_loop_bb (struct loops *, basic_block, rtx);

/* Loop optimizer initialization.  */
extern struct loops *loop_optimizer_init (FILE *);
extern void loop_optimizer_finalize (struct loops *, FILE *);

/* Optimization passes.  */
extern void unswitch_loops (struct loops *);

enum
{
  UAP_PEEL = 1,		/* Enables loop peeling.  */
  UAP_UNROLL = 2,	/* Enables peeling of loops if it seems profitable.  */
  UAP_UNROLL_ALL = 4	/* Enables peeling of all loops.  */
};

extern void unroll_and_peel_loops (struct loops *, int);
Commit	Line	Data
3d436d2a	1	/* Natural loop functions
ca9398d1	2	Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2002, 2003
3d436d2a ZD	3	Free Software Foundation, Inc.
	4
	5	This file is part of GCC.
	6
	7	GCC is free software; you can redistribute it and/or modify it under
	8	the terms of the GNU General Public License as published by the Free
	9	Software Foundation; either version 2, or (at your option) any later
	10	version.
	11
	12	GCC is distributed in the hope that it will be useful, but WITHOUT ANY
	13	WARRANTY; without even the implied warranty of MERCHANTABILITY or
	14	FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
	15	for more details.
	16
	17	You should have received a copy of the GNU General Public License
	18	along with GCC; see the file COPYING. If not, write to the Free
	19	Software Foundation, 59 Temple Place - Suite 330, Boston, MA
	20	02111-1307, USA. */
	21
	22	/* Structure to hold decision about unrolling/peeling. */
	23	enum lpt_dec
	24	{
	25	LPT_NONE,
	26	LPT_PEEL_COMPLETELY,
	27	LPT_PEEL_SIMPLE,
	28	LPT_UNROLL_CONSTANT,
	29	LPT_UNROLL_RUNTIME,
	30	LPT_UNROLL_STUPID
	31	};
	32
	33	struct lpt_decision
	34	{
	35	enum lpt_dec decision;
	36	unsigned times;
	37	};
	38
	39	/* Description of loop for simple loop unrolling. */
	40	struct loop_desc
	41	{
	42	int postincr; /* 1 if increment/decrement is done after loop exit condition. */
	43	rtx stride; /* Value added to VAR in each iteration. */
	44	rtx var; /* Loop control variable. */
	45	rtx var_alts; /* List of definitions of its initial value. */
	46	rtx lim; /* Expression var is compared with. */
	47	rtx lim_alts; /* List of definitions of its initial value. */
	48	bool const_iter; /* True if it iterates constant number of times. */
	49	unsigned HOST_WIDE_INT niter;
	50	/* Number of iterations if it is constant. */
	51	bool may_be_zero; /* If we cannot determine that the first iteration will pass. */
	52	enum rtx_code cond; /* Exit condition. */
	53	int neg; /* Set to 1 if loop ends when condition is satisfied. */
	54	edge out_edge; /* The exit edge. */
	55	edge in_edge; /* And the other one. */
	56	int n_branches; /* Number of branches inside the loop. */
	57	};
	58
	59	/* Structure to hold information for each natural loop. */
	60	struct loop
	61	{
	62	/* Index into loops array. */
	63	int num;
	64
	65	/* Basic block of loop header. */
	66	basic_block header;
67
68	/* Basic block of loop latch. */
69	basic_block latch;
70
71	/* Basic block of loop preheader or NULL if it does not exist. */
72	basic_block pre_header;
73
74	/* For loop unrolling/peeling decision. */
75	struct lpt_decision lpt_decision;
76
77	/* Simple loop description. */
78	int simple;
79	struct loop_desc desc;
80	int has_desc;
81
82	/* Number of loop insns. */
83	unsigned ninsns;
84
85	/* Average number of executed insns per iteration. */
86	unsigned av_ninsns;
87
88	/* Array of edges along the preheader extended basic block trace.
89	The source of the first edge is the root node of preheader
90	extended basic block, if it exists. */
91	edge *pre_header_edges;
92
93	/* Number of edges along the pre_header extended basic block trace. */
94	int num_pre_header_edges;
95
96	/* The first block in the loop. This is not necessarily the same as
97	the loop header. */
98	basic_block first;
99
100	/* The last block in the loop. This is not necessarily the same as
101	the loop latch. */
102	basic_block last;
103
104	/* Bitmap of blocks contained within the loop. */
105	sbitmap nodes;
106
107	/* Number of blocks contained within the loop. */
108	unsigned num_nodes;
109
110	/* Array of edges that enter the loop. */
111	edge *entry_edges;
112
113	/* Number of edges that enter the loop. */
114	int num_entries;
115
116	/* Array of edges that exit the loop. */
117	edge *exit_edges;
118
119	/* Number of edges that exit the loop. */
120	int num_exits;
121
122	/* Bitmap of blocks that dominate all exits of the loop. */
123	sbitmap exits_doms;
124
125	/* The loop nesting depth. */
126	int depth;
127
128	/* Superloops of the loop. */
129	struct loop **pred;
130
131	/* The height of the loop (enclosed loop levels) within the loop
132	hierarchy tree. */
133	int level;
134
135	/* The outer (parent) loop or NULL if outermost loop. */
136	struct loop *outer;
137
138	/* The first inner (child) loop or NULL if innermost loop. */
139	struct loop *inner;
140
141	/* Link to the next (sibling) loop. */
142	struct loop *next;
143
144	/* Loop that is copy of this loop. */
145	struct loop *copy;
146
6356f892	147	/* Nonzero if the loop is invalid (e.g., contains setjmp.). */
3d436d2a ZD	148	int invalid;
	149
	150	/* Auxiliary info specific to a pass. */
	151	void *aux;
	152
	153	/* The following are currently used by loop.c but they are likely to
	154	disappear as loop.c is converted to use the CFG. */
	155
6356f892	156	/* Nonzero if the loop has a NOTE_INSN_LOOP_VTOP. */
3d436d2a ZD	157	rtx vtop;
3d436d2a ZD	158
6356f892	159	/* Nonzero if the loop has a NOTE_INSN_LOOP_CONT.
3d436d2a ZD	160	A continue statement will generate a branch to NEXT_INSN (cont). */
	161	rtx cont;
	162
	163	/* The dominator of cont. */
	164	rtx cont_dominator;
	165
	166	/* The NOTE_INSN_LOOP_BEG. */
	167	rtx start;
	168
	169	/* The NOTE_INSN_LOOP_END. */
	170	rtx end;
	171
	172	/* For a rotated loop that is entered near the bottom,
	173	this is the label at the top. Otherwise it is zero. */
	174	rtx top;
	175
	176	/* Place in the loop where control enters. */
	177	rtx scan_start;
	178
	179	/* The position where to sink insns out of the loop. */
	180	rtx sink;
	181
	182	/* List of all LABEL_REFs which refer to code labels outside the
	183	loop. Used by routines that need to know all loop exits, such as
	184	final_biv_value and final_giv_value.
	185
	186	This does not include loop exits due to return instructions.
	187	This is because all bivs and givs are pseudos, and hence must be
	188	dead after a return, so the presence of a return does not affect
	189	any of the optimizations that use this info. It is simpler to
	190	just not include return instructions on this list. */
	191	rtx exit_labels;
	192
	193	/* The number of LABEL_REFs on exit_labels for this loop and all
	194	loops nested inside it. */
	195	int exit_count;
	196	};
	197
	198	/* Flags for state of loop structure. */
	199	enum
	200	{
	201	LOOPS_HAVE_PREHEADERS = 1,
	202	LOOPS_HAVE_SIMPLE_LATCHES = 2,
	203	LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS = 4
	204	};
	205
	206	/* Structure to hold CFG information about natural loops within a function. */
	207	struct loops
	208	{
	209	/* Number of natural loops in the function. */
	210	unsigned num;
	211
	212	/* Maximum nested loop level in the function. */
	213	unsigned levels;
	214
	215	/* Array of natural loop descriptors (scanning this array in reverse order
	216	will find the inner loops before their enclosing outer loops). */
	217	struct loop *array;
	218
	219	/* The above array is unused in new loop infrastructure and is kept only for
	220	purposes of the old loop optimizer. Instead we store just pointers to
	221	loops here. */
	222	struct loop **parray;
	223
224	/* Pointer to root of loop hierarchy tree. */
225	struct loop *tree_root;
226
227	/* Information derived from the CFG. */
228	struct cfg
229	{
230	/* The bitmap vector of dominators or NULL if not computed. */
231	dominance_info dom;
232
233	/* The ordering of the basic blocks in a depth first search. */
234	int *dfs_order;
235
236	/* The reverse completion ordering of the basic blocks found in a
237	depth first search. */
238	int *rc_order;
239	} cfg;
240
241	/* Headers shared by multiple loops that should be merged. */
242	sbitmap shared_headers;
243
244	/* State of loops. */
245	int state;
246	};
247
248	/* Flags for loop discovery. */
249
250	#define LOOP_TREE 1 /* Build loop hierarchy tree. */
251	#define LOOP_PRE_HEADER 2 /* Analyze loop preheader. */
252	#define LOOP_ENTRY_EDGES 4 /* Find entry edges. */
253	#define LOOP_EXIT_EDGES 8 /* Find exit edges. */
254	#define LOOP_EDGES (LOOP_ENTRY_EDGES \| LOOP_EXIT_EDGES)
255	#define LOOP_ALL 15 /* All of the above */
256
257	/* Loop recognition. */
d329e058 AJ	258	extern int flow_loops_find (struct loops *, int flags);
	259	extern int flow_loops_update (struct loops *, int flags);
	260	extern void flow_loops_free (struct loops *);
	261	extern void flow_loops_dump (const struct loops , FILE ,
	262	void ()(const struct loop , FILE *, int), int);
	263	extern void flow_loop_dump (const struct loop , FILE ,
	264	void ()(const struct loop , FILE *, int), int);
	265	extern int flow_loop_scan (struct loops , struct loop , int);
	266	extern void flow_loop_free (struct loop *);
	267	void mark_irreducible_loops (struct loops *);
3d436d2a ZD	268
3d436d2a ZD	269	/* Loop datastructure manipulation/querying. */
d329e058 AJ	270	extern void flow_loop_tree_node_add (struct loop , struct loop );
	271	extern void flow_loop_tree_node_remove (struct loop *);
	272	extern bool flow_loop_outside_edge_p (const struct loop *, edge);
	273	extern bool flow_loop_nested_p (const struct loop , const struct loop );
	274	extern bool flow_bb_inside_loop_p (const struct loop *, const basic_block);
	275	extern struct loop * find_common_loop (struct loop , struct loop );
	276	extern int num_loop_insns (struct loop *);
	277	extern int average_num_loop_insns (struct loop *);
3d436d2a ZD	278
3d436d2a ZD	279	/* Loops & cfg manipulation. */
d329e058 AJ	280	extern basic_block get_loop_body (const struct loop );
d329e058 AJ	281	extern edge get_loop_exit_edges (const struct loop , unsigned *);
3d436d2a	282
d329e058 AJ	283	extern edge loop_preheader_edge (const struct loop *);
d329e058 AJ	284	extern edge loop_latch_edge (const struct loop *);
3d436d2a	285
d329e058 AJ	286	extern void add_bb_to_loop (basic_block, struct loop *);
d329e058 AJ	287	extern void remove_bb_from_loops (basic_block);
3d436d2a	288
d329e058 AJ	289	extern void cancel_loop (struct loops , struct loop );
d329e058 AJ	290	extern void cancel_loop_tree (struct loops , struct loop );
3d436d2a	291
d329e058 AJ	292	extern basic_block loop_split_edge_with (edge, rtx, struct loops *);
d329e058 AJ	293	extern int fix_loop_placement (struct loop *);
3d436d2a ZD	294
	295	enum
	296	{
bc35512f	297	CP_SIMPLE_PREHEADERS = 1
3d436d2a ZD	298	};
3d436d2a ZD	299
d329e058 AJ	300	extern void create_preheaders (struct loops *, int);
d329e058 AJ	301	extern void force_single_succ_latches (struct loops *);
3d436d2a	302
d329e058	303	extern void verify_loop_structure (struct loops *);
3d436d2a ZD	304
3d436d2a ZD	305	/* Loop analysis. */
d329e058 AJ	306	extern bool simple_loop_p (struct loops , struct loop , struct loop_desc *);
	307	extern rtx count_loop_iterations (struct loop_desc *, rtx, rtx);
	308	extern bool just_once_each_iteration_p (struct loops ,struct loop ,
	309	basic_block);
	310	extern unsigned expected_loop_iterations (const struct loop *);
617b465c ZD	311
617b465c ZD	312	/* Loop manipulation. */
d329e058	313	extern bool can_duplicate_loop_p (struct loop *loop);
617b465c ZD	314
	315	#define DLTHE_FLAG_UPDATE_FREQ 1 /* Update frequencies in
	316	duplicate_loop_to_header_edge. */
	317
d329e058 AJ	318	extern int duplicate_loop_to_header_edge (struct loop , edge, struct loops ,
	319	unsigned, sbitmap, edge, edge *,
	320	unsigned *, int);
	321	extern struct loop loopify (struct loops , edge, edge, basic_block);
	322	extern void unloop (struct loops , struct loop );
	323	extern bool remove_path (struct loops *, edge);
	324	extern edge split_loop_bb (struct loops *, basic_block, rtx);
617b465c ZD	325
617b465c ZD	326	/* Loop optimizer initialization. */
d329e058 AJ	327	extern struct loops loop_optimizer_init (FILE );
d329e058 AJ	328	extern void loop_optimizer_finalize (struct loops , FILE );
617b465c ZD	329
617b465c ZD	330	/* Optimization passes. */
d329e058	331	extern void unswitch_loops (struct loops *);
617b465c	332
b17d5d7c ZD	333	enum
	334	{
	335	UAP_PEEL = 1, /* Enables loop peeling. */
	336	UAP_UNROLL = 2, /* Enables peeling of loops if it seems profitable. */
	337	UAP_UNROLL_ALL = 4 /* Enables peeling of all loops. */
	338	};
	339
d329e058	340	extern void unroll_and_peel_loops (struct loops *, int);