]>
Commit | Line | Data |
---|---|---|
3d436d2a | 1 | /* Natural loop functions |
aa335b76 | 2 | Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004 |
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 | ||
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 | ||
3d436d2a ZD |
46 | /* Structure to hold information for each natural loop. */ |
47 | struct loop | |
48 | { | |
49 | /* Index into loops array. */ | |
50 | int num; | |
51 | ||
52 | /* Basic block of loop header. */ | |
53 | basic_block header; | |
54 | ||
55 | /* Basic block of loop latch. */ | |
56 | basic_block latch; | |
57 | ||
58 | /* Basic block of loop preheader or NULL if it does not exist. */ | |
59 | basic_block pre_header; | |
60 | ||
61 | /* For loop unrolling/peeling decision. */ | |
62 | struct lpt_decision lpt_decision; | |
63 | ||
3d436d2a ZD |
64 | /* Number of loop insns. */ |
65 | unsigned ninsns; | |
66 | ||
67 | /* Average number of executed insns per iteration. */ | |
68 | unsigned av_ninsns; | |
69 | ||
70 | /* Array of edges along the preheader extended basic block trace. | |
71 | The source of the first edge is the root node of preheader | |
72 | extended basic block, if it exists. */ | |
73 | edge *pre_header_edges; | |
74 | ||
75 | /* Number of edges along the pre_header extended basic block trace. */ | |
76 | int num_pre_header_edges; | |
77 | ||
78 | /* The first block in the loop. This is not necessarily the same as | |
79 | the loop header. */ | |
80 | basic_block first; | |
81 | ||
82 | /* The last block in the loop. This is not necessarily the same as | |
83 | the loop latch. */ | |
84 | basic_block last; | |
85 | ||
86 | /* Bitmap of blocks contained within the loop. */ | |
87 | sbitmap nodes; | |
88 | ||
89 | /* Number of blocks contained within the loop. */ | |
90 | unsigned num_nodes; | |
91 | ||
92 | /* Array of edges that enter the loop. */ | |
93 | edge *entry_edges; | |
94 | ||
95 | /* Number of edges that enter the loop. */ | |
96 | int num_entries; | |
97 | ||
98 | /* Array of edges that exit the loop. */ | |
99 | edge *exit_edges; | |
100 | ||
101 | /* Number of edges that exit the loop. */ | |
102 | int num_exits; | |
103 | ||
104 | /* Bitmap of blocks that dominate all exits of the loop. */ | |
105 | sbitmap exits_doms; | |
106 | ||
107 | /* The loop nesting depth. */ | |
108 | int depth; | |
109 | ||
110 | /* Superloops of the loop. */ | |
111 | struct loop **pred; | |
112 | ||
113 | /* The height of the loop (enclosed loop levels) within the loop | |
114 | hierarchy tree. */ | |
115 | int level; | |
116 | ||
117 | /* The outer (parent) loop or NULL if outermost loop. */ | |
118 | struct loop *outer; | |
119 | ||
120 | /* The first inner (child) loop or NULL if innermost loop. */ | |
121 | struct loop *inner; | |
122 | ||
123 | /* Link to the next (sibling) loop. */ | |
124 | struct loop *next; | |
125 | ||
126 | /* Loop that is copy of this loop. */ | |
127 | struct loop *copy; | |
128 | ||
6356f892 | 129 | /* Nonzero if the loop is invalid (e.g., contains setjmp.). */ |
3d436d2a ZD |
130 | int invalid; |
131 | ||
132 | /* Auxiliary info specific to a pass. */ | |
133 | void *aux; | |
134 | ||
135 | /* The following are currently used by loop.c but they are likely to | |
136 | disappear as loop.c is converted to use the CFG. */ | |
137 | ||
6356f892 | 138 | /* Nonzero if the loop has a NOTE_INSN_LOOP_VTOP. */ |
3d436d2a ZD |
139 | rtx vtop; |
140 | ||
6356f892 | 141 | /* Nonzero if the loop has a NOTE_INSN_LOOP_CONT. |
3d436d2a ZD |
142 | A continue statement will generate a branch to NEXT_INSN (cont). */ |
143 | rtx cont; | |
144 | ||
145 | /* The dominator of cont. */ | |
146 | rtx cont_dominator; | |
147 | ||
148 | /* The NOTE_INSN_LOOP_BEG. */ | |
149 | rtx start; | |
150 | ||
151 | /* The NOTE_INSN_LOOP_END. */ | |
152 | rtx end; | |
153 | ||
154 | /* For a rotated loop that is entered near the bottom, | |
155 | this is the label at the top. Otherwise it is zero. */ | |
156 | rtx top; | |
157 | ||
158 | /* Place in the loop where control enters. */ | |
159 | rtx scan_start; | |
160 | ||
161 | /* The position where to sink insns out of the loop. */ | |
162 | rtx sink; | |
163 | ||
164 | /* List of all LABEL_REFs which refer to code labels outside the | |
165 | loop. Used by routines that need to know all loop exits, such as | |
166 | final_biv_value and final_giv_value. | |
167 | ||
168 | This does not include loop exits due to return instructions. | |
169 | This is because all bivs and givs are pseudos, and hence must be | |
170 | dead after a return, so the presence of a return does not affect | |
171 | any of the optimizations that use this info. It is simpler to | |
172 | just not include return instructions on this list. */ | |
173 | rtx exit_labels; | |
174 | ||
175 | /* The number of LABEL_REFs on exit_labels for this loop and all | |
176 | loops nested inside it. */ | |
177 | int exit_count; | |
e9eb809d ZD |
178 | |
179 | /* Upper bound on number of iterations of a loop. */ | |
180 | struct nb_iter_bound *bounds; | |
3d436d2a ZD |
181 | }; |
182 | ||
183 | /* Flags for state of loop structure. */ | |
184 | enum | |
185 | { | |
186 | LOOPS_HAVE_PREHEADERS = 1, | |
187 | LOOPS_HAVE_SIMPLE_LATCHES = 2, | |
188 | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS = 4 | |
189 | }; | |
190 | ||
191 | /* Structure to hold CFG information about natural loops within a function. */ | |
192 | struct loops | |
193 | { | |
194 | /* Number of natural loops in the function. */ | |
195 | unsigned num; | |
196 | ||
197 | /* Maximum nested loop level in the function. */ | |
198 | unsigned levels; | |
199 | ||
200 | /* Array of natural loop descriptors (scanning this array in reverse order | |
201 | will find the inner loops before their enclosing outer loops). */ | |
202 | struct loop *array; | |
203 | ||
204 | /* The above array is unused in new loop infrastructure and is kept only for | |
205 | purposes of the old loop optimizer. Instead we store just pointers to | |
206 | loops here. */ | |
207 | struct loop **parray; | |
208 | ||
209 | /* Pointer to root of loop hierarchy tree. */ | |
210 | struct loop *tree_root; | |
211 | ||
212 | /* Information derived from the CFG. */ | |
213 | struct cfg | |
214 | { | |
3d436d2a ZD |
215 | /* The ordering of the basic blocks in a depth first search. */ |
216 | int *dfs_order; | |
217 | ||
218 | /* The reverse completion ordering of the basic blocks found in a | |
219 | depth first search. */ | |
220 | int *rc_order; | |
221 | } cfg; | |
222 | ||
223 | /* Headers shared by multiple loops that should be merged. */ | |
224 | sbitmap shared_headers; | |
225 | ||
226 | /* State of loops. */ | |
227 | int state; | |
228 | }; | |
229 | ||
230 | /* Flags for loop discovery. */ | |
231 | ||
232 | #define LOOP_TREE 1 /* Build loop hierarchy tree. */ | |
233 | #define LOOP_PRE_HEADER 2 /* Analyze loop preheader. */ | |
234 | #define LOOP_ENTRY_EDGES 4 /* Find entry edges. */ | |
235 | #define LOOP_EXIT_EDGES 8 /* Find exit edges. */ | |
236 | #define LOOP_EDGES (LOOP_ENTRY_EDGES | LOOP_EXIT_EDGES) | |
237 | #define LOOP_ALL 15 /* All of the above */ | |
238 | ||
239 | /* Loop recognition. */ | |
d329e058 AJ |
240 | extern int flow_loops_find (struct loops *, int flags); |
241 | extern int flow_loops_update (struct loops *, int flags); | |
242 | extern void flow_loops_free (struct loops *); | |
243 | extern void flow_loops_dump (const struct loops *, FILE *, | |
244 | void (*)(const struct loop *, FILE *, int), int); | |
245 | extern void flow_loop_dump (const struct loop *, FILE *, | |
246 | void (*)(const struct loop *, FILE *, int), int); | |
d47cc544 | 247 | extern int flow_loop_scan (struct loop *, int); |
d329e058 AJ |
248 | extern void flow_loop_free (struct loop *); |
249 | void mark_irreducible_loops (struct loops *); | |
6de9cd9a | 250 | extern void create_loop_notes (void); |
3d436d2a | 251 | |
4d6922ee | 252 | /* Loop data structure manipulation/querying. */ |
d329e058 AJ |
253 | extern void flow_loop_tree_node_add (struct loop *, struct loop *); |
254 | extern void flow_loop_tree_node_remove (struct loop *); | |
255 | extern bool flow_loop_outside_edge_p (const struct loop *, edge); | |
256 | extern bool flow_loop_nested_p (const struct loop *, const struct loop *); | |
257 | extern bool flow_bb_inside_loop_p (const struct loop *, const basic_block); | |
258 | extern struct loop * find_common_loop (struct loop *, struct loop *); | |
a7e5372d | 259 | struct loop *superloop_at_depth (struct loop *, unsigned); |
d329e058 AJ |
260 | extern int num_loop_insns (struct loop *); |
261 | extern int average_num_loop_insns (struct loop *); | |
689ba89d | 262 | extern unsigned get_loop_level (const struct loop *); |
3d436d2a ZD |
263 | |
264 | /* Loops & cfg manipulation. */ | |
d329e058 | 265 | extern basic_block *get_loop_body (const struct loop *); |
50654f6c | 266 | extern basic_block *get_loop_body_in_dom_order (const struct loop *); |
d329e058 | 267 | extern edge *get_loop_exit_edges (const struct loop *, unsigned *); |
50654f6c | 268 | extern unsigned num_loop_branches (const struct loop *); |
3d436d2a | 269 | |
d329e058 AJ |
270 | extern edge loop_preheader_edge (const struct loop *); |
271 | extern edge loop_latch_edge (const struct loop *); | |
3d436d2a | 272 | |
d329e058 AJ |
273 | extern void add_bb_to_loop (basic_block, struct loop *); |
274 | extern void remove_bb_from_loops (basic_block); | |
3d436d2a | 275 | |
d329e058 AJ |
276 | extern void cancel_loop (struct loops *, struct loop *); |
277 | extern void cancel_loop_tree (struct loops *, struct loop *); | |
3d436d2a | 278 | |
d47cc544 | 279 | extern basic_block loop_split_edge_with (edge, rtx); |
d329e058 | 280 | extern int fix_loop_placement (struct loop *); |
3d436d2a ZD |
281 | |
282 | enum | |
283 | { | |
bc35512f | 284 | CP_SIMPLE_PREHEADERS = 1 |
3d436d2a ZD |
285 | }; |
286 | ||
d329e058 AJ |
287 | extern void create_preheaders (struct loops *, int); |
288 | extern void force_single_succ_latches (struct loops *); | |
3d436d2a | 289 | |
d329e058 | 290 | extern void verify_loop_structure (struct loops *); |
3d436d2a ZD |
291 | |
292 | /* Loop analysis. */ | |
d47cc544 | 293 | extern bool just_once_each_iteration_p (struct loop *, basic_block); |
d329e058 | 294 | extern unsigned expected_loop_iterations (const struct loop *); |
617b465c ZD |
295 | |
296 | /* Loop manipulation. */ | |
d329e058 | 297 | extern bool can_duplicate_loop_p (struct loop *loop); |
617b465c ZD |
298 | |
299 | #define DLTHE_FLAG_UPDATE_FREQ 1 /* Update frequencies in | |
300 | duplicate_loop_to_header_edge. */ | |
301 | ||
d329e058 AJ |
302 | extern int duplicate_loop_to_header_edge (struct loop *, edge, struct loops *, |
303 | unsigned, sbitmap, edge, edge *, | |
304 | unsigned *, int); | |
305 | extern struct loop *loopify (struct loops *, edge, edge, basic_block); | |
306 | extern void unloop (struct loops *, struct loop *); | |
307 | extern bool remove_path (struct loops *, edge); | |
d47cc544 | 308 | extern edge split_loop_bb (basic_block, rtx); |
617b465c | 309 | |
50654f6c ZD |
310 | /* Induction variable analysis. */ |
311 | ||
312 | /* The description of induction variable. The things are a bit complicated | |
313 | due to need to handle subregs and extends. The value of the object described | |
314 | by it can be obtained as follows (all computations are done in extend_mode): | |
315 | ||
316 | Value in i-th iteration is | |
317 | delta + mult * extend_{extend_mode} (subreg_{mode} (base + i * step)). | |
318 | ||
319 | If first_special is true, the value in the first iteration is | |
320 | delta + mult * base | |
321 | ||
322 | If extend = NIL, first_special must be false, delta 0, mult 1 and value is | |
323 | subreg_{mode} (base + i * step) | |
324 | ||
325 | The get_iv_value function can be used to obtain these expressions. | |
326 | ||
327 | ??? Add a third mode field that would specify the mode in that inner | |
328 | computation is done, which would enable it to be different from the | |
329 | outer one? */ | |
330 | ||
331 | struct rtx_iv | |
332 | { | |
333 | /* Its base and step (mode of base and step is supposed to be extend_mode, | |
334 | see the description above). */ | |
335 | rtx base, step; | |
336 | ||
337 | /* The type of extend applied to it (SIGN_EXTEND, ZERO_EXTEND or NIL). */ | |
338 | enum rtx_code extend; | |
339 | ||
340 | /* Operations applied in the extended mode. */ | |
341 | rtx delta, mult; | |
342 | ||
343 | /* The mode it is extended to. */ | |
344 | enum machine_mode extend_mode; | |
345 | ||
346 | /* The mode the variable iterates in. */ | |
347 | enum machine_mode mode; | |
348 | ||
349 | /* Whether we have already filled the remaining fields. */ | |
350 | unsigned analysed : 1; | |
351 | ||
352 | /* Whether the first iteration needs to be handled specially. */ | |
353 | unsigned first_special : 1; | |
354 | }; | |
355 | ||
f2dca510 ZD |
356 | /* The description of an exit from the loop and of the number of iterations |
357 | till we take the exit. */ | |
50654f6c ZD |
358 | |
359 | struct niter_desc | |
360 | { | |
361 | /* The edge out of the loop. */ | |
362 | edge out_edge; | |
363 | ||
364 | /* The other edge leading from the condition. */ | |
365 | edge in_edge; | |
366 | ||
367 | /* True if we are able to say anything about number of iterations of the | |
368 | loop. */ | |
369 | bool simple_p; | |
370 | ||
371 | /* True if the loop iterates the constant number of times. */ | |
372 | bool const_iter; | |
373 | ||
374 | /* Number of iterations if constant. */ | |
375 | unsigned HOST_WIDEST_INT niter; | |
376 | ||
377 | /* Upper bound on the number of iterations. */ | |
378 | unsigned HOST_WIDEST_INT niter_max; | |
379 | ||
380 | /* Assumptions under that the rest of the information is valid. */ | |
381 | rtx assumptions; | |
382 | ||
383 | /* Assumptions under that the loop ends before reaching the latch, | |
384 | even if value of niter_expr says otherwise. */ | |
385 | rtx noloop_assumptions; | |
386 | ||
387 | /* Condition under that the loop is infinite. */ | |
388 | rtx infinite; | |
389 | ||
390 | /* Whether the comparison is signed. */ | |
391 | bool signed_p; | |
392 | ||
393 | /* The mode in that niter_expr should be computed. */ | |
394 | enum machine_mode mode; | |
395 | ||
396 | /* The number of iterations of the loop. */ | |
397 | rtx niter_expr; | |
398 | }; | |
399 | ||
400 | extern void iv_analysis_loop_init (struct loop *); | |
401 | extern rtx iv_get_reaching_def (rtx, rtx); | |
6d4e0ecc | 402 | extern bool iv_analyze (rtx, rtx, struct rtx_iv *); |
50654f6c ZD |
403 | extern rtx get_iv_value (struct rtx_iv *, rtx); |
404 | extern void find_simple_exit (struct loop *, struct niter_desc *); | |
405 | extern void iv_number_of_iterations (struct loop *, rtx, rtx, | |
406 | struct niter_desc *); | |
407 | extern void iv_analysis_done (void); | |
408 | ||
409 | extern struct niter_desc *get_simple_loop_desc (struct loop *loop); | |
410 | extern void free_simple_loop_desc (struct loop *loop); | |
411 | ||
412 | static inline struct niter_desc * | |
413 | simple_loop_desc (struct loop *loop) | |
414 | { | |
415 | return loop->aux; | |
416 | } | |
417 | ||
5e962776 ZD |
418 | /* Register pressure estimation for induction variable optimizations & loop |
419 | invariant motion. */ | |
420 | extern unsigned global_cost_for_size (unsigned, unsigned, unsigned); | |
421 | extern void init_set_costs (void); | |
422 | ||
617b465c | 423 | /* Loop optimizer initialization. */ |
d329e058 AJ |
424 | extern struct loops *loop_optimizer_init (FILE *); |
425 | extern void loop_optimizer_finalize (struct loops *, FILE *); | |
617b465c ZD |
426 | |
427 | /* Optimization passes. */ | |
d329e058 | 428 | extern void unswitch_loops (struct loops *); |
617b465c | 429 | |
b17d5d7c ZD |
430 | enum |
431 | { | |
432 | UAP_PEEL = 1, /* Enables loop peeling. */ | |
433 | UAP_UNROLL = 2, /* Enables peeling of loops if it seems profitable. */ | |
434 | UAP_UNROLL_ALL = 4 /* Enables peeling of all loops. */ | |
435 | }; | |
436 | ||
d329e058 | 437 | extern void unroll_and_peel_loops (struct loops *, int); |
689ba89d | 438 | extern void doloop_optimize_loops (struct loops *); |
5e962776 | 439 | extern void move_loop_invariants (struct loops *); |
59587b18 JQ |
440 | |
441 | #endif /* GCC_CFGLOOP_H */ |