]>
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; |
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. */ | |
258 | extern int flow_loops_find PARAMS ((struct loops *, int flags)); | |
259 | extern int flow_loops_update PARAMS ((struct loops *, int flags)); | |
260 | extern void flow_loops_free PARAMS ((struct loops *)); | |
261 | extern void flow_loops_dump PARAMS ((const struct loops *, FILE *, | |
262 | void (*)(const struct loop *, | |
263 | FILE *, int), int)); | |
264 | extern void flow_loop_dump PARAMS ((const struct loop *, FILE *, | |
265 | void (*)(const struct loop *, | |
266 | FILE *, int), int)); | |
267 | extern int flow_loop_scan PARAMS ((struct loops *, | |
268 | struct loop *, int)); | |
35b07080 | 269 | extern void flow_loop_free PARAMS ((struct loop *)); |
3d436d2a ZD |
270 | void mark_irreducible_loops PARAMS ((struct loops *)); |
271 | ||
272 | /* Loop datastructure manipulation/querying. */ | |
273 | extern void flow_loop_tree_node_add PARAMS ((struct loop *, struct loop *)); | |
274 | extern void flow_loop_tree_node_remove PARAMS ((struct loop *)); | |
275 | extern bool flow_loop_outside_edge_p PARAMS ((const struct loop *, edge)); | |
276 | extern bool flow_loop_nested_p PARAMS ((const struct loop *, | |
277 | const struct loop *)); | |
278 | extern bool flow_bb_inside_loop_p PARAMS ((const struct loop *, | |
ca9398d1 | 279 | const basic_block)); |
3d436d2a ZD |
280 | extern struct loop * find_common_loop PARAMS ((struct loop *, struct loop *)); |
281 | extern int num_loop_insns PARAMS ((struct loop *)); | |
282 | extern int average_num_loop_insns PARAMS ((struct loop *)); | |
283 | ||
284 | /* Loops & cfg manipulation. */ | |
285 | extern basic_block *get_loop_body PARAMS ((const struct loop *)); | |
35b07080 | 286 | extern edge *get_loop_exit_edges PARAMS ((const struct loop *, unsigned *)); |
3d436d2a ZD |
287 | |
288 | extern edge loop_preheader_edge PARAMS ((const struct loop *)); | |
289 | extern edge loop_latch_edge PARAMS ((const struct loop *)); | |
290 | ||
291 | extern void add_bb_to_loop PARAMS ((basic_block, struct loop *)); | |
292 | extern void remove_bb_from_loops PARAMS ((basic_block)); | |
293 | ||
294 | extern void cancel_loop PARAMS ((struct loops *, struct loop *)); | |
295 | extern void cancel_loop_tree PARAMS ((struct loops *, struct loop *)); | |
296 | ||
297 | extern basic_block loop_split_edge_with PARAMS ((edge, rtx, struct loops *)); | |
617b465c | 298 | extern int fix_loop_placement PARAMS ((struct loop *)); |
3d436d2a ZD |
299 | |
300 | enum | |
301 | { | |
302 | CP_SIMPLE_PREHEADERS = 1, | |
303 | CP_INSIDE_CFGLAYOUT = 2 | |
304 | }; | |
305 | ||
306 | extern void create_preheaders PARAMS ((struct loops *, int)); | |
307 | extern void force_single_succ_latches PARAMS ((struct loops *)); | |
308 | ||
309 | extern void verify_loop_structure PARAMS ((struct loops *)); | |
310 | ||
311 | /* Loop analysis. */ | |
312 | extern bool simple_loop_p PARAMS ((struct loops *, struct loop *, | |
313 | struct loop_desc *)); | |
314 | extern rtx count_loop_iterations PARAMS ((struct loop_desc *, rtx, rtx)); | |
315 | extern bool just_once_each_iteration_p PARAMS ((struct loops *,struct loop *, | |
316 | basic_block)); | |
317 | extern unsigned expected_loop_iterations PARAMS ((const struct loop *)); | |
617b465c ZD |
318 | |
319 | /* Loop manipulation. */ | |
320 | extern bool can_duplicate_loop_p PARAMS ((struct loop *loop)); | |
321 | ||
322 | #define DLTHE_FLAG_UPDATE_FREQ 1 /* Update frequencies in | |
323 | duplicate_loop_to_header_edge. */ | |
324 | ||
325 | extern int duplicate_loop_to_header_edge PARAMS ((struct loop *, edge, | |
326 | struct loops *, unsigned, | |
327 | sbitmap, edge, edge *, | |
328 | unsigned *, int)); | |
329 | extern struct loop *loopify PARAMS ((struct loops *, edge, | |
330 | edge, basic_block)); | |
35b07080 | 331 | extern void unloop PARAMS ((struct loops *, struct loop *)); |
617b465c ZD |
332 | extern bool remove_path PARAMS ((struct loops *, edge)); |
333 | extern edge split_loop_bb PARAMS ((struct loops *, basic_block, | |
334 | rtx)); | |
335 | ||
336 | /* Loop optimizer initialization. */ | |
337 | extern struct loops *loop_optimizer_init PARAMS ((FILE *)); | |
338 | extern void loop_optimizer_finalize PARAMS ((struct loops *, FILE *)); | |
339 | ||
340 | /* Optimization passes. */ | |
341 | extern void unswitch_loops PARAMS ((struct loops *)); | |
342 | ||
b17d5d7c ZD |
343 | enum |
344 | { | |
345 | UAP_PEEL = 1, /* Enables loop peeling. */ | |
346 | UAP_UNROLL = 2, /* Enables peeling of loops if it seems profitable. */ | |
347 | UAP_UNROLL_ALL = 4 /* Enables peeling of all loops. */ | |
348 | }; | |
349 | ||
350 | extern void unroll_and_peel_loops PARAMS ((struct loops *, int)); |