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

/* Natural loop functions
   Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005
   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, 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301, USA.  */

#ifndef GCC_CFGLOOP_H
#define GCC_CFGLOOP_H

#include "basic-block.h"
/* For rtx_code.  */
#include "rtl.h"

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

/* The structure describing a bound on number of iterations of a loop.  */

struct nb_iter_bound
{
  /* The statement STMT is executed at most ...  */
  tree stmt;

  /* ... BOUND + 1 times (BOUND must be an unsigned constant).
     The + 1 is added for the following reasons:

     a) 0 would otherwise be unused, while we would need to care more about
        overflows (as MAX + 1 is sometimes produced as the estimate on number
	of executions of STMT).
     b) it is consistent with the result of number_of_iterations_exit.  */
  double_int bound;

  /* True if the statement will cause the loop to be leaved the (at most) 
     BOUND + 1-st time it is executed, that is, all the statements after it
     are executed at most BOUND times.  */
  bool is_exit;

  /* True if the bound is "realistic" -- i.e., most likely the loop really has
     number of iterations close to the bound.  Exact bounds (if the number of
     iterations of a loop is a constant) and bounds derived from the size of
     data accessed in the loop are considered realistic.  */
  bool realistic;

  /* The next bound in the list.  */
  struct nb_iter_bound *next;
};

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

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

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

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

  /* Number of blocks contained within the loop.  */
  unsigned num_nodes;

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

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

  /* The probable number of times the loop is executed at runtime.
     This is an INTEGER_CST or an expression containing symbolic
     names.  Don't access this field directly:
     number_of_iterations_in_loop computes and caches the computed
     information in this field.  */
  tree nb_iterations;

  /* An integer estimation of the number of iterations.  Estimate_state
     describes what is the state of the estimation.  */
  enum
    {
      /* Estimate was not computed yet.  */
      EST_NOT_COMPUTED,
      /* Estimate was computed, but we could derive no useful bound.  */
      EST_NOT_AVAILABLE,
      /* Estimate is ready.  */
      EST_AVAILABLE
    } estimate_state;
  double_int estimated_nb_iterations;

  /* Upper bound on number of iterations of a loop.  */
  struct nb_iter_bound *bounds;

  /* If not NULL, loop has just single exit edge stored here (edges to the
     EXIT_BLOCK_PTR do not count.  */
  edge single_exit;

  /* True when the loop does not carry data dependences, and
     consequently the iterations can be executed in any order.  False
     when the loop carries data dependences, or when the property is
     not decidable.  */
  bool parallel_p;
};

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

#define LOOPS_NORMAL (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES \
		      | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)

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

  /* State of loops.  */
  int state;

  /* We store just pointers to loops here.  
     Note that a loop in this array may actually be NULL, if the loop
     has been removed and the entire loops structure has not been
     recomputed since that time.  */
  struct loop **parray;

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

  /* Information derived from the CFG.  */
  struct cfg
  {
    /* 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;
};

/* The loop tree currently optimized.  */

extern struct loops *current_loops;

/* Loop recognition.  */
extern int flow_loops_find (struct loops *);
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 void flow_loop_free (struct loop *);
int flow_loop_nodes_find (basic_block, struct loop *);
void fix_loop_structure (struct loops *, bitmap changed_bbs);
void mark_irreducible_loops (struct loops *);
void mark_single_exit_loops (struct loops *);

/* Loop data structure 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_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 *);
struct loop *superloop_at_depth (struct loop *, unsigned);
extern unsigned tree_num_loop_insns (struct loop *);
extern int num_loop_insns (struct loop *);
extern int average_num_loop_insns (struct loop *);
extern unsigned get_loop_level (const struct loop *);
extern bool loop_exit_edge_p (const struct loop *, edge);
extern void mark_loop_exit_edges (struct loops *);

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

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_tree (struct loops *, struct loop *);

extern basic_block loop_split_edge_with (edge, rtx);
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 just_once_each_iteration_p (const struct loop *, basic_block);
extern unsigned expected_loop_iterations (const struct loop *);
extern rtx doloop_condition_get (rtx);

/* 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.  */
#define DLTHE_RECORD_COPY_NUMBER 2	/* Record copy number in the aux
					   field of newly create BB.  */
#define DLTHE_FLAG_COMPLETTE_PEEL 4	/* Update frequencies expecting
					   a complete peeling.  */

extern struct loop * duplicate_loop (struct loops *, struct loop *,
				     struct loop *);
extern bool 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, edge, edge, bool);
struct loop * loop_version (struct loops *, struct loop *, void *,
			    basic_block *, bool);
extern bool remove_path (struct loops *, edge);

/* Induction variable analysis.  */

/* The description of induction variable.  The things are a bit complicated
   due to need to handle subregs and extends.  The value of the object described
   by it can be obtained as follows (all computations are done in extend_mode):

   Value in i-th iteration is
     delta + mult * extend_{extend_mode} (subreg_{mode} (base + i * step)).

   If first_special is true, the value in the first iteration is
     delta + mult * base

   If extend = UNKNOWN, first_special must be false, delta 0, mult 1 and value is
     subreg_{mode} (base + i * step)

   The get_iv_value function can be used to obtain these expressions.

   ??? Add a third mode field that would specify the mode in that inner
   computation is done, which would enable it to be different from the
   outer one?  */

struct rtx_iv
{
  /* Its base and step (mode of base and step is supposed to be extend_mode,
     see the description above).  */
  rtx base, step;

  /* The type of extend applied to it (SIGN_EXTEND, ZERO_EXTEND or UNKNOWN).  */
  enum rtx_code extend;

  /* Operations applied in the extended mode.  */
  rtx delta, mult;

  /* The mode it is extended to.  */
  enum machine_mode extend_mode;

  /* The mode the variable iterates in.  */
  enum machine_mode mode;

  /* Whether the first iteration needs to be handled specially.  */
  unsigned first_special : 1;
};

/* The description of an exit from the loop and of the number of iterations
   till we take the exit.  */

struct niter_desc
{
  /* The edge out of the loop.  */
  edge out_edge;

  /* The other edge leading from the condition.  */
  edge in_edge;

  /* True if we are able to say anything about number of iterations of the
     loop.  */
  bool simple_p;

  /* True if the loop iterates the constant number of times.  */
  bool const_iter;

  /* Number of iterations if constant.  */
  unsigned HOST_WIDEST_INT niter;

  /* Upper bound on the number of iterations.  */
  unsigned HOST_WIDEST_INT niter_max;

  /* Assumptions under that the rest of the information is valid.  */
  rtx assumptions;

  /* Assumptions under that the loop ends before reaching the latch,
     even if value of niter_expr says otherwise.  */
  rtx noloop_assumptions;

  /* Condition under that the loop is infinite.  */
  rtx infinite;

  /* Whether the comparison is signed.  */
  bool signed_p;

  /* The mode in that niter_expr should be computed.  */
  enum machine_mode mode;

  /* The number of iterations of the loop.  */
  rtx niter_expr;
};

extern void iv_analysis_loop_init (struct loop *);
extern bool iv_analyze (rtx, rtx, struct rtx_iv *);
extern bool iv_analyze_result (rtx, rtx, struct rtx_iv *);
extern bool iv_analyze_expr (rtx, rtx, enum machine_mode, struct rtx_iv *);
extern rtx get_iv_value (struct rtx_iv *, rtx);
extern bool biv_p (rtx, rtx);
extern void find_simple_exit (struct loop *, struct niter_desc *);
extern void iv_analysis_done (void);
extern struct df *iv_current_loop_df (void);

extern struct niter_desc *get_simple_loop_desc (struct loop *loop);
extern void free_simple_loop_desc (struct loop *loop);

static inline struct niter_desc *
simple_loop_desc (struct loop *loop)
{
  return (struct niter_desc *) loop->aux;
}

/* The properties of the target.  */

extern unsigned target_avail_regs;	/* Number of available registers.  */
extern unsigned target_res_regs;	/* Number of reserved registers.  */
extern unsigned target_small_cost;	/* The cost for register when there
					   is a free one.  */
extern unsigned target_pres_cost;	/* The cost for register when there are
					   not too many free ones.  */
extern unsigned target_spill_cost;	/* The cost for register when we need
					   to spill.  */

/* Register pressure estimation for induction variable optimizations & loop
   invariant motion.  */
extern unsigned global_cost_for_size (unsigned, unsigned, unsigned);
extern void init_set_costs (void);

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

/* 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);
extern void doloop_optimize_loops (struct loops *);
extern void move_loop_invariants (struct loops *);

#endif /* GCC_CFGLOOP_H */
Commit	Line	Data
3d436d2a	1	/* Natural loop functions
613c5cd0	2	Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005
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
366ccddb KC	19	Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
366ccddb KC	20	02110-1301, USA. */
3d436d2a	21
59587b18 JQ	22	#ifndef GCC_CFGLOOP_H
	23	#define GCC_CFGLOOP_H
	24
	25	#include "basic-block.h"
	26	/* For rtx_code. */
	27	#include "rtl.h"
	28
3d436d2a ZD	29	/* Structure to hold decision about unrolling/peeling. */
	30	enum lpt_dec
	31	{
	32	LPT_NONE,
	33	LPT_PEEL_COMPLETELY,
	34	LPT_PEEL_SIMPLE,
	35	LPT_UNROLL_CONSTANT,
	36	LPT_UNROLL_RUNTIME,
	37	LPT_UNROLL_STUPID
	38	};
	39
	40	struct lpt_decision
	41	{
	42	enum lpt_dec decision;
	43	unsigned times;
	44	};
	45
86df10e3 SP	46	/* The structure describing a bound on number of iterations of a loop. */
	47
	48	struct nb_iter_bound
	49	{
946e1bc7 ZD	50	/* The statement STMT is executed at most ... */
	51	tree stmt;
	52
	53	/* ... BOUND + 1 times (BOUND must be an unsigned constant).
	54	The + 1 is added for the following reasons:
	55
	56	a) 0 would otherwise be unused, while we would need to care more about
	57	overflows (as MAX + 1 is sometimes produced as the estimate on number
	58	of executions of STMT).
	59	b) it is consistent with the result of number_of_iterations_exit. */
	60	double_int bound;
	61
	62	/* True if the statement will cause the loop to be leaved the (at most)
	63	BOUND + 1-st time it is executed, that is, all the statements after it
	64	are executed at most BOUND times. */
	65	bool is_exit;
	66
	67	/* True if the bound is "realistic" -- i.e., most likely the loop really has
	68	number of iterations close to the bound. Exact bounds (if the number of
	69	iterations of a loop is a constant) and bounds derived from the size of
	70	data accessed in the loop are considered realistic. */
	71	bool realistic;
	72
	73	/* The next bound in the list. */
86df10e3	74	struct nb_iter_bound *next;
86df10e3 SP	75	};
86df10e3 SP	76
3d436d2a ZD	77	/* Structure to hold information for each natural loop. */
	78	struct loop
	79	{
	80	/* Index into loops array. */
	81	int num;
	82
	83	/* Basic block of loop header. */
	84	basic_block header;
	85
	86	/* Basic block of loop latch. */
	87	basic_block latch;
	88
3d436d2a ZD	89	/* For loop unrolling/peeling decision. */
	90	struct lpt_decision lpt_decision;
	91
3d436d2a ZD	92	/* Number of loop insns. */
	93	unsigned ninsns;
	94
	95	/* Average number of executed insns per iteration. */
	96	unsigned av_ninsns;
	97
3d436d2a ZD	98	/* Number of blocks contained within the loop. */
	99	unsigned num_nodes;
	100
3d436d2a ZD	101	/* The loop nesting depth. */
	102	int depth;
	103
	104	/* Superloops of the loop. */
	105	struct loop **pred;
	106
	107	/* The height of the loop (enclosed loop levels) within the loop
	108	hierarchy tree. */
	109	int level;
	110
	111	/* The outer (parent) loop or NULL if outermost loop. */
	112	struct loop *outer;
	113
	114	/* The first inner (child) loop or NULL if innermost loop. */
	115	struct loop *inner;
	116
	117	/* Link to the next (sibling) loop. */
	118	struct loop *next;
	119
	120	/* Loop that is copy of this loop. */
	121	struct loop *copy;
	122
3d436d2a ZD	123	/* Auxiliary info specific to a pass. */
	124	void *aux;
	125
9baba81b SP	126	/* The probable number of times the loop is executed at runtime.
	127	This is an INTEGER_CST or an expression containing symbolic
	128	names. Don't access this field directly:
	129	number_of_iterations_in_loop computes and caches the computed
	130	information in this field. */
	131	tree nb_iterations;
	132
946e1bc7 ZD	133	/* An integer estimation of the number of iterations. Estimate_state
	134	describes what is the state of the estimation. */
	135	enum
	136	{
	137	/* Estimate was not computed yet. */
	138	EST_NOT_COMPUTED,
	139	/* Estimate was computed, but we could derive no useful bound. */
	140	EST_NOT_AVAILABLE,
	141	/* Estimate is ready. */
	142	EST_AVAILABLE
	143	} estimate_state;
	144	double_int estimated_nb_iterations;
86df10e3	145
e9eb809d ZD	146	/* Upper bound on number of iterations of a loop. */
e9eb809d ZD	147	struct nb_iter_bound *bounds;
82b85a85 ZD	148
	149	/* If not NULL, loop has just single exit edge stored here (edges to the
	150	EXIT_BLOCK_PTR do not count. */
	151	edge single_exit;
86df10e3 SP	152
	153	/* True when the loop does not carry data dependences, and
	154	consequently the iterations can be executed in any order. False
	155	when the loop carries data dependences, or when the property is
	156	not decidable. */
	157	bool parallel_p;
3d436d2a ZD	158	};
	159
	160	/* Flags for state of loop structure. */
	161	enum
	162	{
	163	LOOPS_HAVE_PREHEADERS = 1,
	164	LOOPS_HAVE_SIMPLE_LATCHES = 2,
82b85a85 ZD	165	LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS = 4,
82b85a85 ZD	166	LOOPS_HAVE_MARKED_SINGLE_EXITS = 8
3d436d2a ZD	167	};
3d436d2a ZD	168
d78f3f78 ZD	169	#define LOOPS_NORMAL (LOOPS_HAVE_PREHEADERS \| LOOPS_HAVE_SIMPLE_LATCHES \
	170	\| LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
	171
3d436d2a ZD	172	/* Structure to hold CFG information about natural loops within a function. */
	173	struct loops
	174	{
	175	/* Number of natural loops in the function. */
	176	unsigned num;
	177
0162f155 RG	178	/* State of loops. */
0162f155 RG	179	int state;
3d436d2a	180
0162f155	181	/* We store just pointers to loops here.
43a613f7 DB	182	Note that a loop in this array may actually be NULL, if the loop
	183	has been removed and the entire loops structure has not been
	184	recomputed since that time. */
3d436d2a ZD	185	struct loop **parray;
	186
	187	/* Pointer to root of loop hierarchy tree. */
	188	struct loop *tree_root;
	189
	190	/* Information derived from the CFG. */
	191	struct cfg
	192	{
3d436d2a ZD	193	/* The ordering of the basic blocks in a depth first search. */
	194	int *dfs_order;
	195
	196	/* The reverse completion ordering of the basic blocks found in a
	197	depth first search. */
	198	int *rc_order;
	199	} cfg;
	200
	201	/* Headers shared by multiple loops that should be merged. */
	202	sbitmap shared_headers;
3d436d2a ZD	203	};
3d436d2a ZD	204
9baba81b SP	205	/* The loop tree currently optimized. */
	206
	207	extern struct loops *current_loops;
	208
3d436d2a	209	/* Loop recognition. */
70388d94	210	extern int flow_loops_find (struct loops *);
d329e058 AJ	211	extern void flow_loops_free (struct loops *);
	212	extern void flow_loops_dump (const struct loops , FILE ,
	213	void ()(const struct loop , FILE *, int), int);
	214	extern void flow_loop_dump (const struct loop , FILE ,
	215	void ()(const struct loop , FILE *, int), int);
d329e058	216	extern void flow_loop_free (struct loop *);
2b271002 ZD	217	int flow_loop_nodes_find (basic_block, struct loop *);
2b271002 ZD	218	void fix_loop_structure (struct loops *, bitmap changed_bbs);
d329e058	219	void mark_irreducible_loops (struct loops *);
82b85a85	220	void mark_single_exit_loops (struct loops *);
3d436d2a	221
4d6922ee	222	/* Loop data structure manipulation/querying. */
d329e058 AJ	223	extern void flow_loop_tree_node_add (struct loop , struct loop );
d329e058 AJ	224	extern void flow_loop_tree_node_remove (struct loop *);
d329e058 AJ	225	extern bool flow_loop_nested_p (const struct loop , const struct loop );
	226	extern bool flow_bb_inside_loop_p (const struct loop *, const basic_block);
	227	extern struct loop * find_common_loop (struct loop , struct loop );
a7e5372d	228	struct loop superloop_at_depth (struct loop , unsigned);
82b85a85	229	extern unsigned tree_num_loop_insns (struct loop *);
d329e058 AJ	230	extern int num_loop_insns (struct loop *);
d329e058 AJ	231	extern int average_num_loop_insns (struct loop *);
689ba89d	232	extern unsigned get_loop_level (const struct loop *);
70388d94 ZD	233	extern bool loop_exit_edge_p (const struct loop *, edge);
70388d94 ZD	234	extern void mark_loop_exit_edges (struct loops *);
3d436d2a ZD	235
3d436d2a ZD	236	/* Loops & cfg manipulation. */
d329e058	237	extern basic_block get_loop_body (const struct loop );
50654f6c	238	extern basic_block get_loop_body_in_dom_order (const struct loop );
40923b20	239	extern basic_block get_loop_body_in_bfs_order (const struct loop );
d329e058	240	extern edge get_loop_exit_edges (const struct loop , unsigned *);
50654f6c	241	extern unsigned num_loop_branches (const struct loop *);
3d436d2a	242
d329e058 AJ	243	extern edge loop_preheader_edge (const struct loop *);
d329e058 AJ	244	extern edge loop_latch_edge (const struct loop *);
3d436d2a	245
d329e058 AJ	246	extern void add_bb_to_loop (basic_block, struct loop *);
d329e058 AJ	247	extern void remove_bb_from_loops (basic_block);
3d436d2a	248
d329e058	249	extern void cancel_loop_tree (struct loops , struct loop );
3d436d2a	250
d47cc544	251	extern basic_block loop_split_edge_with (edge, rtx);
d329e058	252	extern int fix_loop_placement (struct loop *);
3d436d2a ZD	253
	254	enum
	255	{
bc35512f	256	CP_SIMPLE_PREHEADERS = 1
3d436d2a ZD	257	};
3d436d2a ZD	258
d329e058 AJ	259	extern void create_preheaders (struct loops *, int);
d329e058 AJ	260	extern void force_single_succ_latches (struct loops *);
3d436d2a	261
d329e058	262	extern void verify_loop_structure (struct loops *);
3d436d2a ZD	263
3d436d2a ZD	264	/* Loop analysis. */
6c878b23	265	extern bool just_once_each_iteration_p (const struct loop *, basic_block);
d329e058	266	extern unsigned expected_loop_iterations (const struct loop *);
75c70254	267	extern rtx doloop_condition_get (rtx);
617b465c ZD	268
617b465c ZD	269	/* Loop manipulation. */
d329e058	270	extern bool can_duplicate_loop_p (struct loop *loop);
617b465c ZD	271
	272	#define DLTHE_FLAG_UPDATE_FREQ 1 /* Update frequencies in
	273	duplicate_loop_to_header_edge. */
7f7b1718 JH	274	#define DLTHE_RECORD_COPY_NUMBER 2 /* Record copy number in the aux
7f7b1718 JH	275	field of newly create BB. */
178df94f	276	#define DLTHE_FLAG_COMPLETTE_PEEL 4 /* Update frequencies expecting
a4d05547	277	a complete peeling. */
617b465c	278
f67d92e9 DB	279	extern struct loop * duplicate_loop (struct loops , struct loop ,
f67d92e9 DB	280	struct loop *);
1cb7dfc3 MH	281	extern bool duplicate_loop_to_header_edge (struct loop , edge, struct loops ,
	282	unsigned, sbitmap, edge, edge *,
	283	unsigned *, int);
5132abc2 KH	284	extern struct loop loopify (struct loops , edge, edge,
5132abc2 KH	285	basic_block, edge, edge, bool);
1cb7dfc3	286	struct loop * loop_version (struct loops , struct loop , void *,
b9a66240	287	basic_block *, bool);
d329e058	288	extern bool remove_path (struct loops *, edge);
617b465c	289
50654f6c ZD	290	/* Induction variable analysis. */
	291
	292	/* The description of induction variable. The things are a bit complicated
	293	due to need to handle subregs and extends. The value of the object described
	294	by it can be obtained as follows (all computations are done in extend_mode):
	295
	296	Value in i-th iteration is
	297	delta + mult * extend_{extend_mode} (subreg_{mode} (base + i * step)).
	298
	299	If first_special is true, the value in the first iteration is
	300	delta + mult * base
c22cacf3	301
f822d252	302	If extend = UNKNOWN, first_special must be false, delta 0, mult 1 and value is
50654f6c ZD	303	subreg_{mode} (base + i * step)
	304
	305	The get_iv_value function can be used to obtain these expressions.
	306
	307	??? Add a third mode field that would specify the mode in that inner
	308	computation is done, which would enable it to be different from the
	309	outer one? */
	310
	311	struct rtx_iv
	312	{
	313	/* Its base and step (mode of base and step is supposed to be extend_mode,
	314	see the description above). */
	315	rtx base, step;
	316
f822d252	317	/* The type of extend applied to it (SIGN_EXTEND, ZERO_EXTEND or UNKNOWN). */
50654f6c ZD	318	enum rtx_code extend;
	319
	320	/* Operations applied in the extended mode. */
	321	rtx delta, mult;
	322
	323	/* The mode it is extended to. */
	324	enum machine_mode extend_mode;
	325
	326	/* The mode the variable iterates in. */
	327	enum machine_mode mode;
	328
50654f6c ZD	329	/* Whether the first iteration needs to be handled specially. */
	330	unsigned first_special : 1;
	331	};
	332
f2dca510 ZD	333	/* The description of an exit from the loop and of the number of iterations
f2dca510 ZD	334	till we take the exit. */
50654f6c ZD	335
	336	struct niter_desc
	337	{
	338	/* The edge out of the loop. */
	339	edge out_edge;
	340
	341	/* The other edge leading from the condition. */
	342	edge in_edge;
	343
	344	/* True if we are able to say anything about number of iterations of the
	345	loop. */
	346	bool simple_p;
	347
	348	/* True if the loop iterates the constant number of times. */
	349	bool const_iter;
	350
	351	/* Number of iterations if constant. */
	352	unsigned HOST_WIDEST_INT niter;
	353
	354	/* Upper bound on the number of iterations. */
	355	unsigned HOST_WIDEST_INT niter_max;
	356
	357	/* Assumptions under that the rest of the information is valid. */
	358	rtx assumptions;
	359
	360	/* Assumptions under that the loop ends before reaching the latch,
	361	even if value of niter_expr says otherwise. */
	362	rtx noloop_assumptions;
	363
	364	/* Condition under that the loop is infinite. */
	365	rtx infinite;
	366
	367	/* Whether the comparison is signed. */
	368	bool signed_p;
	369
	370	/* The mode in that niter_expr should be computed. */
	371	enum machine_mode mode;
	372
	373	/* The number of iterations of the loop. */
	374	rtx niter_expr;
	375	};
	376
	377	extern void iv_analysis_loop_init (struct loop *);
6d4e0ecc	378	extern bool iv_analyze (rtx, rtx, struct rtx_iv *);
03fd2215 ZD	379	extern bool iv_analyze_result (rtx, rtx, struct rtx_iv *);
03fd2215 ZD	380	extern bool iv_analyze_expr (rtx, rtx, enum machine_mode, struct rtx_iv *);
50654f6c	381	extern rtx get_iv_value (struct rtx_iv *, rtx);
113d659a	382	extern bool biv_p (rtx, rtx);
50654f6c	383	extern void find_simple_exit (struct loop , struct niter_desc );
50654f6c	384	extern void iv_analysis_done (void);
03fd2215	385	extern struct df *iv_current_loop_df (void);
50654f6c ZD	386
	387	extern struct niter_desc get_simple_loop_desc (struct loop loop);
	388	extern void free_simple_loop_desc (struct loop *loop);
	389
	390	static inline struct niter_desc *
	391	simple_loop_desc (struct loop *loop)
	392	{
cceb1885	393	return (struct niter_desc *) loop->aux;
50654f6c ZD	394	}
50654f6c ZD	395
8b11a64c ZD	396	/* The properties of the target. */
	397
	398	extern unsigned target_avail_regs; /* Number of available registers. */
	399	extern unsigned target_res_regs; /* Number of reserved registers. */
	400	extern unsigned target_small_cost; /* The cost for register when there
	401	is a free one. */
	402	extern unsigned target_pres_cost; /* The cost for register when there are
	403	not too many free ones. */
	404	extern unsigned target_spill_cost; /* The cost for register when we need
	405	to spill. */
	406
5e962776 ZD	407	/* Register pressure estimation for induction variable optimizations & loop
	408	invariant motion. */
	409	extern unsigned global_cost_for_size (unsigned, unsigned, unsigned);
	410	extern void init_set_costs (void);
	411
617b465c	412	/* Loop optimizer initialization. */
10d22567 ZD	413	extern struct loops *loop_optimizer_init (unsigned);
10d22567 ZD	414	extern void loop_optimizer_finalize (struct loops *);
617b465c ZD	415
617b465c ZD	416	/* Optimization passes. */
d329e058	417	extern void unswitch_loops (struct loops *);
617b465c	418
b17d5d7c ZD	419	enum
	420	{
	421	UAP_PEEL = 1, /* Enables loop peeling. */
	422	UAP_UNROLL = 2, /* Enables peeling of loops if it seems profitable. */
	423	UAP_UNROLL_ALL = 4 /* Enables peeling of all loops. */
	424	};
	425
d329e058	426	extern void unroll_and_peel_loops (struct loops *, int);
689ba89d	427	extern void doloop_optimize_loops (struct loops *);
5e962776	428	extern void move_loop_invariants (struct loops *);
59587b18 JQ	429
59587b18 JQ	430	#endif /* GCC_CFGLOOP_H */