1/* Natural loop functions
2   Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005
3   Free Software Foundation, Inc.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 2, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING.  If not, write to the Free
19Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
2002110-1301, USA.  */
21
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
29/* Structure to hold decision about unrolling/peeling.  */
30enum 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
40struct lpt_decision
41{
42  enum lpt_dec decision;
43  unsigned times;
44};
45
46/* The structure describing a bound on number of iterations of a loop.  */
47
48struct nb_iter_bound
49{
50  tree bound;		/* The constant expression whose value is an upper
51			   bound on the number of executions of ...  */
52  tree at_stmt;		/* ... this statement during one execution of
53			   a loop.  */
54  struct nb_iter_bound *next;
55			/* The next bound in a list.  */
56};
57
58/* Structure to hold information for each natural loop.  */
59struct loop
60{
61  /* Index into loops array.  */
62  int num;
63
64  /* Basic block of loop header.  */
65  basic_block header;
66
67  /* Basic block of loop latch.  */
68  basic_block latch;
69
70  /* For loop unrolling/peeling decision.  */
71  struct lpt_decision lpt_decision;
72
73  /* Number of loop insns.  */
74  unsigned ninsns;
75
76  /* Average number of executed insns per iteration.  */
77  unsigned av_ninsns;
78
79  /* Number of blocks contained within the loop.  */
80  unsigned num_nodes;
81
82  /* The loop nesting depth.  */
83  int depth;
84
85  /* Superloops of the loop.  */
86  struct loop **pred;
87
88  /* The height of the loop (enclosed loop levels) within the loop
89     hierarchy tree.  */
90  int level;
91
92  /* The outer (parent) loop or NULL if outermost loop.  */
93  struct loop *outer;
94
95  /* The first inner (child) loop or NULL if innermost loop.  */
96  struct loop *inner;
97
98  /* Link to the next (sibling) loop.  */
99  struct loop *next;
100
101  /* Loop that is copy of this loop.  */
102  struct loop *copy;
103
104  /* Auxiliary info specific to a pass.  */
105  void *aux;
106
107  /* The probable number of times the loop is executed at runtime.
108     This is an INTEGER_CST or an expression containing symbolic
109     names.  Don't access this field directly:
110     number_of_iterations_in_loop computes and caches the computed
111     information in this field.  */
112  tree nb_iterations;
113
114  /* An INTEGER_CST estimation of the number of iterations.  NULL_TREE
115     if there is no estimation.  */
116  tree estimated_nb_iterations;
117
118  /* Upper bound on number of iterations of a loop.  */
119  struct nb_iter_bound *bounds;
120
121  /* If not NULL, loop has just single exit edge stored here (edges to the
122     EXIT_BLOCK_PTR do not count.  */
123  edge single_exit;
124
125  /* True when the loop does not carry data dependences, and
126     consequently the iterations can be executed in any order.  False
127     when the loop carries data dependences, or when the property is
128     not decidable.  */
129  bool parallel_p;
130};
131
132/* Flags for state of loop structure.  */
133enum
134{
135  LOOPS_HAVE_PREHEADERS = 1,
136  LOOPS_HAVE_SIMPLE_LATCHES = 2,
137  LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS = 4,
138  LOOPS_HAVE_MARKED_SINGLE_EXITS = 8
139};
140
141#define LOOPS_NORMAL (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES \
142		      | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
143
144/* Structure to hold CFG information about natural loops within a function.  */
145struct loops
146{
147  /* Number of natural loops in the function.  */
148  unsigned num;
149
150  /* State of loops.  */
151  int state;
152
153  /* We store just pointers to loops here.
154     Note that a loop in this array may actually be NULL, if the loop
155     has been removed and the entire loops structure has not been
156     recomputed since that time.  */
157  struct loop **parray;
158
159  /* Pointer to root of loop hierarchy tree.  */
160  struct loop *tree_root;
161
162  /* Information derived from the CFG.  */
163  struct cfg
164  {
165    /* The ordering of the basic blocks in a depth first search.  */
166    int *dfs_order;
167
168    /* The reverse completion ordering of the basic blocks found in a
169       depth first search.  */
170    int *rc_order;
171  } cfg;
172
173  /* Headers shared by multiple loops that should be merged.  */
174  sbitmap shared_headers;
175};
176
177/* The loop tree currently optimized.  */
178
179extern struct loops *current_loops;
180
181/* Loop recognition.  */
182extern int flow_loops_find (struct loops *);
183extern void flow_loops_free (struct loops *);
184extern void flow_loops_dump (const struct loops *, FILE *,
185			     void (*)(const struct loop *, FILE *, int), int);
186extern void flow_loop_dump (const struct loop *, FILE *,
187			    void (*)(const struct loop *, FILE *, int), int);
188extern void flow_loop_free (struct loop *);
189int flow_loop_nodes_find (basic_block, struct loop *);
190void fix_loop_structure (struct loops *, bitmap changed_bbs);
191void mark_irreducible_loops (struct loops *);
192void mark_single_exit_loops (struct loops *);
193
194/* Loop data structure manipulation/querying.  */
195extern void flow_loop_tree_node_add (struct loop *, struct loop *);
196extern void flow_loop_tree_node_remove (struct loop *);
197extern bool flow_loop_nested_p	(const struct loop *, const struct loop *);
198extern bool flow_bb_inside_loop_p (const struct loop *, const basic_block);
199extern struct loop * find_common_loop (struct loop *, struct loop *);
200struct loop *superloop_at_depth (struct loop *, unsigned);
201extern unsigned tree_num_loop_insns (struct loop *);
202extern int num_loop_insns (struct loop *);
203extern int average_num_loop_insns (struct loop *);
204extern unsigned get_loop_level (const struct loop *);
205extern bool loop_exit_edge_p (const struct loop *, edge);
206extern void mark_loop_exit_edges (struct loops *);
207
208/* Loops & cfg manipulation.  */
209extern basic_block *get_loop_body (const struct loop *);
210extern basic_block *get_loop_body_in_dom_order (const struct loop *);
211extern basic_block *get_loop_body_in_bfs_order (const struct loop *);
212extern edge *get_loop_exit_edges (const struct loop *, unsigned *);
213extern unsigned num_loop_branches (const struct loop *);
214
215extern edge loop_preheader_edge (const struct loop *);
216extern edge loop_latch_edge (const struct loop *);
217
218extern void add_bb_to_loop (basic_block, struct loop *);
219extern void remove_bb_from_loops (basic_block);
220
221extern void cancel_loop_tree (struct loops *, struct loop *);
222
223extern basic_block loop_split_edge_with (edge, rtx);
224extern int fix_loop_placement (struct loop *);
225
226enum
227{
228  CP_SIMPLE_PREHEADERS = 1
229};
230
231extern void create_preheaders (struct loops *, int);
232extern void force_single_succ_latches (struct loops *);
233
234extern void verify_loop_structure (struct loops *);
235
236/* Loop analysis.  */
237extern bool just_once_each_iteration_p (const struct loop *, basic_block);
238extern unsigned expected_loop_iterations (const struct loop *);
239extern rtx doloop_condition_get (rtx);
240
241/* Loop manipulation.  */
242extern bool can_duplicate_loop_p (struct loop *loop);
243
244#define DLTHE_FLAG_UPDATE_FREQ	1	/* Update frequencies in
245					   duplicate_loop_to_header_edge.  */
246#define DLTHE_RECORD_COPY_NUMBER 2	/* Record copy number in the aux
247					   field of newly create BB.  */
248#define DLTHE_FLAG_COMPLETTE_PEEL 4	/* Update frequencies expecting
249					   a complete peeling.  */
250
251extern struct loop * duplicate_loop (struct loops *, struct loop *,
252				     struct loop *);
253extern bool duplicate_loop_to_header_edge (struct loop *, edge, struct loops *,
254					   unsigned, sbitmap, edge, edge *,
255					   unsigned *, int);
256extern struct loop *loopify (struct loops *, edge, edge,
257			     basic_block, edge, edge, bool);
258struct loop * loop_version (struct loops *, struct loop *, void *,
259			    basic_block *, bool);
260extern bool remove_path (struct loops *, edge);
261
262/* Induction variable analysis.  */
263
264/* The description of induction variable.  The things are a bit complicated
265   due to need to handle subregs and extends.  The value of the object described
266   by it can be obtained as follows (all computations are done in extend_mode):
267
268   Value in i-th iteration is
269     delta + mult * extend_{extend_mode} (subreg_{mode} (base + i * step)).
270
271   If first_special is true, the value in the first iteration is
272     delta + mult * base
273
274   If extend = UNKNOWN, first_special must be false, delta 0, mult 1 and value is
275     subreg_{mode} (base + i * step)
276
277   The get_iv_value function can be used to obtain these expressions.
278
279   ??? Add a third mode field that would specify the mode in that inner
280   computation is done, which would enable it to be different from the
281   outer one?  */
282
283struct rtx_iv
284{
285  /* Its base and step (mode of base and step is supposed to be extend_mode,
286     see the description above).  */
287  rtx base, step;
288
289  /* The type of extend applied to it (SIGN_EXTEND, ZERO_EXTEND or UNKNOWN).  */
290  enum rtx_code extend;
291
292  /* Operations applied in the extended mode.  */
293  rtx delta, mult;
294
295  /* The mode it is extended to.  */
296  enum machine_mode extend_mode;
297
298  /* The mode the variable iterates in.  */
299  enum machine_mode mode;
300
301  /* Whether the first iteration needs to be handled specially.  */
302  unsigned first_special : 1;
303};
304
305/* The description of an exit from the loop and of the number of iterations
306   till we take the exit.  */
307
308struct niter_desc
309{
310  /* The edge out of the loop.  */
311  edge out_edge;
312
313  /* The other edge leading from the condition.  */
314  edge in_edge;
315
316  /* True if we are able to say anything about number of iterations of the
317     loop.  */
318  bool simple_p;
319
320  /* True if the loop iterates the constant number of times.  */
321  bool const_iter;
322
323  /* Number of iterations if constant.  */
324  unsigned HOST_WIDEST_INT niter;
325
326  /* Upper bound on the number of iterations.  */
327  unsigned HOST_WIDEST_INT niter_max;
328
329  /* Assumptions under that the rest of the information is valid.  */
330  rtx assumptions;
331
332  /* Assumptions under that the loop ends before reaching the latch,
333     even if value of niter_expr says otherwise.  */
334  rtx noloop_assumptions;
335
336  /* Condition under that the loop is infinite.  */
337  rtx infinite;
338
339  /* Whether the comparison is signed.  */
340  bool signed_p;
341
342  /* The mode in that niter_expr should be computed.  */
343  enum machine_mode mode;
344
345  /* The number of iterations of the loop.  */
346  rtx niter_expr;
347};
348
349extern void iv_analysis_loop_init (struct loop *);
350extern bool iv_analyze (rtx, rtx, struct rtx_iv *);
351extern bool iv_analyze_result (rtx, rtx, struct rtx_iv *);
352extern bool iv_analyze_expr (rtx, rtx, enum machine_mode, struct rtx_iv *);
353extern rtx get_iv_value (struct rtx_iv *, rtx);
354extern bool biv_p (rtx, rtx);
355extern void find_simple_exit (struct loop *, struct niter_desc *);
356extern void iv_analysis_done (void);
357extern struct df *iv_current_loop_df (void);
358
359extern struct niter_desc *get_simple_loop_desc (struct loop *loop);
360extern void free_simple_loop_desc (struct loop *loop);
361
362static inline struct niter_desc *
363simple_loop_desc (struct loop *loop)
364{
365  return (struct niter_desc *) loop->aux;
366}
367
368/* The properties of the target.  */
369
370extern unsigned target_avail_regs;	/* Number of available registers.  */
371extern unsigned target_res_regs;	/* Number of reserved registers.  */
372extern unsigned target_small_cost;	/* The cost for register when there
373					   is a free one.  */
374extern unsigned target_pres_cost;	/* The cost for register when there are
375					   not too many free ones.  */
376extern unsigned target_spill_cost;	/* The cost for register when we need
377					   to spill.  */
378
379/* Register pressure estimation for induction variable optimizations & loop
380   invariant motion.  */
381extern unsigned global_cost_for_size (unsigned, unsigned, unsigned);
382extern void init_set_costs (void);
383
384/* Loop optimizer initialization.  */
385extern struct loops *loop_optimizer_init (unsigned);
386extern void loop_optimizer_finalize (struct loops *);
387
388/* Optimization passes.  */
389extern void unswitch_loops (struct loops *);
390
391enum
392{
393  UAP_PEEL = 1,		/* Enables loop peeling.  */
394  UAP_UNROLL = 2,	/* Enables peeling of loops if it seems profitable.  */
395  UAP_UNROLL_ALL = 4	/* Enables peeling of all loops.  */
396};
397
398extern void unroll_and_peel_loops (struct loops *, int);
399extern void doloop_optimize_loops (struct loops *);
400extern void move_loop_invariants (struct loops *);
401extern void record_estimate (struct loop *, tree, tree, tree);
402
403#endif /* GCC_CFGLOOP_H */
404