OSDN Git Service

* Makefile.in (tree-data-ref.o): Add langhooks.h dependency.
[pf3gnuchains/gcc-fork.git] / gcc / cfgloop.h
1 /* Natural loop functions
2    Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005
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, 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-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.  */
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
46 /* The structure describing a bound on number of iterations of a loop.  */
47
48 struct nb_iter_bound
49 {
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.  */
74   struct nb_iter_bound *next;
75 };
76
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
89   /* For loop unrolling/peeling decision.  */
90   struct lpt_decision lpt_decision;
91
92   /* Number of loop insns.  */
93   unsigned ninsns;
94
95   /* Average number of executed insns per iteration.  */
96   unsigned av_ninsns;
97
98   /* Number of blocks contained within the loop.  */
99   unsigned num_nodes;
100
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
123   /* Auxiliary info specific to a pass.  */
124   void *aux;
125
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
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;
145
146   /* Upper bound on number of iterations of a loop.  */
147   struct nb_iter_bound *bounds;
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;
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;
158 };
159
160 /* Flags for state of loop structure.  */
161 enum
162 {
163   LOOPS_HAVE_PREHEADERS = 1,
164   LOOPS_HAVE_SIMPLE_LATCHES = 2,
165   LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS = 4,
166   LOOPS_HAVE_MARKED_SINGLE_EXITS = 8
167 };
168
169 #define LOOPS_NORMAL (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES \
170                       | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
171
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
178   /* State of loops.  */
179   int state;
180
181   /* We store just pointers to loops here.  
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.  */
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   {
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;
203 };
204
205 /* The loop tree currently optimized.  */
206
207 extern struct loops *current_loops;
208
209 /* Loop recognition.  */
210 extern int flow_loops_find (struct loops *);
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);
216 extern void flow_loop_free (struct loop *);
217 int flow_loop_nodes_find (basic_block, struct loop *);
218 void fix_loop_structure (struct loops *, bitmap changed_bbs);
219 void mark_irreducible_loops (struct loops *);
220 void mark_single_exit_loops (struct loops *);
221
222 /* Loop data structure manipulation/querying.  */
223 extern void flow_loop_tree_node_add (struct loop *, struct loop *);
224 extern void flow_loop_tree_node_remove (struct loop *);
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 *);
228 struct loop *superloop_at_depth (struct loop *, unsigned);
229 extern unsigned tree_num_loop_insns (struct loop *);
230 extern int num_loop_insns (struct loop *);
231 extern int average_num_loop_insns (struct loop *);
232 extern unsigned get_loop_level (const struct loop *);
233 extern bool loop_exit_edge_p (const struct loop *, edge);
234 extern void mark_loop_exit_edges (struct loops *);
235
236 /* Loops & cfg manipulation.  */
237 extern basic_block *get_loop_body (const struct loop *);
238 extern basic_block *get_loop_body_in_dom_order (const struct loop *);
239 extern basic_block *get_loop_body_in_bfs_order (const struct loop *);
240 extern edge *get_loop_exit_edges (const struct loop *, unsigned *);
241 extern unsigned num_loop_branches (const struct loop *);
242
243 extern edge loop_preheader_edge (const struct loop *);
244 extern edge loop_latch_edge (const struct loop *);
245
246 extern void add_bb_to_loop (basic_block, struct loop *);
247 extern void remove_bb_from_loops (basic_block);
248
249 extern void cancel_loop_tree (struct loops *, struct loop *);
250
251 extern basic_block loop_split_edge_with (edge, rtx);
252 extern int fix_loop_placement (struct loop *);
253
254 enum
255 {
256   CP_SIMPLE_PREHEADERS = 1
257 };
258
259 extern void create_preheaders (struct loops *, int);
260 extern void force_single_succ_latches (struct loops *);
261
262 extern void verify_loop_structure (struct loops *);
263
264 /* Loop analysis.  */
265 extern bool just_once_each_iteration_p (const struct loop *, basic_block);
266 extern unsigned expected_loop_iterations (const struct loop *);
267 extern rtx doloop_condition_get (rtx);
268
269 /* Loop manipulation.  */
270 extern bool can_duplicate_loop_p (struct loop *loop);
271
272 #define DLTHE_FLAG_UPDATE_FREQ  1       /* Update frequencies in
273                                            duplicate_loop_to_header_edge.  */
274 #define DLTHE_RECORD_COPY_NUMBER 2      /* Record copy number in the aux
275                                            field of newly create BB.  */
276 #define DLTHE_FLAG_COMPLETTE_PEEL 4     /* Update frequencies expecting
277                                            a complete peeling.  */
278
279 extern struct loop * duplicate_loop (struct loops *, struct loop *,
280                                      struct loop *);
281 extern bool duplicate_loop_to_header_edge (struct loop *, edge, struct loops *,
282                                            unsigned, sbitmap, edge, edge *,
283                                            unsigned *, int);
284 extern struct loop *loopify (struct loops *, edge, edge,
285                              basic_block, edge, edge, bool);
286 struct loop * loop_version (struct loops *, struct loop *, void *,
287                             basic_block *, bool);
288 extern bool remove_path (struct loops *, edge);
289
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
301
302    If extend = UNKNOWN, first_special must be false, delta 0, mult 1 and value is
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
317   /* The type of extend applied to it (SIGN_EXTEND, ZERO_EXTEND or UNKNOWN).  */
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
329   /* Whether the first iteration needs to be handled specially.  */
330   unsigned first_special : 1;
331 };
332
333 /* The description of an exit from the loop and of the number of iterations
334    till we take the exit.  */
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 *);
378 extern bool iv_analyze (rtx, rtx, struct rtx_iv *);
379 extern bool iv_analyze_result (rtx, rtx, struct rtx_iv *);
380 extern bool iv_analyze_expr (rtx, rtx, enum machine_mode, struct rtx_iv *);
381 extern rtx get_iv_value (struct rtx_iv *, rtx);
382 extern bool biv_p (rtx, rtx);
383 extern void find_simple_exit (struct loop *, struct niter_desc *);
384 extern void iv_analysis_done (void);
385 extern struct df *iv_current_loop_df (void);
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 {
393   return (struct niter_desc *) loop->aux;
394 }
395
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
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
412 /* Loop optimizer initialization.  */
413 extern struct loops *loop_optimizer_init (unsigned);
414 extern void loop_optimizer_finalize (struct loops *);
415
416 /* Optimization passes.  */
417 extern void unswitch_loops (struct loops *);
418
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
426 extern void unroll_and_peel_loops (struct loops *, int);
427 extern void doloop_optimize_loops (struct loops *);
428 extern void move_loop_invariants (struct loops *);
429
430 #endif /* GCC_CFGLOOP_H */