]>
Commit | Line | Data |
---|---|---|
9fa26457 | 1 | /* Loop optimizer initialization routines and RTL loop optimization passes. |
d652f226 | 2 | Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2010 |
66647d44 | 3 | Free Software Foundation, Inc. |
617b465c ZD |
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 | |
9dcd6f09 | 9 | Software Foundation; either version 3, or (at your option) any later |
617b465c ZD |
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 | |
9dcd6f09 NC |
18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ | |
617b465c ZD |
20 | |
21 | #include "config.h" | |
22 | #include "system.h" | |
23 | #include "coretypes.h" | |
24 | #include "tm.h" | |
25 | #include "rtl.h" | |
532aafad | 26 | #include "regs.h" |
7932a3db | 27 | #include "obstack.h" |
617b465c ZD |
28 | #include "basic-block.h" |
29 | #include "cfgloop.h" | |
ef330312 PB |
30 | #include "tree-pass.h" |
31 | #include "timevar.h" | |
32 | #include "flags.h" | |
6fb5fa3c | 33 | #include "df.h" |
9e2f83a5 | 34 | #include "ggc.h" |
617b465c | 35 | |
9fa26457 | 36 | \f |
598ec7bd | 37 | /* Initialize loop structures. This is used by the tree and RTL loop |
d78f3f78 ZD |
38 | optimizers. FLAGS specify what properties to compute and/or ensure for |
39 | loops. */ | |
617b465c | 40 | |
598ec7bd | 41 | void |
10d22567 | 42 | loop_optimizer_init (unsigned flags) |
617b465c | 43 | { |
7d776ee2 RG |
44 | if (!current_loops) |
45 | { | |
46 | struct loops *loops = ggc_alloc_cleared_loops (); | |
47 | ||
48 | gcc_assert (!(cfun->curr_properties & PROP_loops)); | |
5e962776 | 49 | |
7d776ee2 | 50 | /* Find the loops. */ |
598ec7bd | 51 | |
7d776ee2 RG |
52 | flow_loops_find (loops); |
53 | current_loops = loops; | |
54 | } | |
55 | else | |
56 | { | |
57 | gcc_assert (cfun->curr_properties & PROP_loops); | |
617b465c | 58 | |
7d776ee2 RG |
59 | /* Ensure that the dominators are computed, like flow_loops_find does. */ |
60 | calculate_dominance_info (CDI_DOMINATORS); | |
61 | ||
62 | #ifdef ENABLE_CHECKING | |
63 | verify_loop_structure (); | |
64 | #endif | |
65 | } | |
598ec7bd | 66 | |
89f8f30f ZD |
67 | if (flags & LOOPS_MAY_HAVE_MULTIPLE_LATCHES) |
68 | { | |
69 | /* If the loops may have multiple latches, we cannot canonicalize | |
70 | them further (and most of the loop manipulation functions will | |
71 | not work). However, we avoid modifying cfg, which some | |
72 | passes may want. */ | |
73 | gcc_assert ((flags & ~(LOOPS_MAY_HAVE_MULTIPLE_LATCHES | |
74 | | LOOPS_HAVE_RECORDED_EXITS)) == 0); | |
f87000d0 | 75 | loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES); |
89f8f30f ZD |
76 | } |
77 | else | |
78 | disambiguate_loops_with_multiple_latches (); | |
79 | ||
617b465c | 80 | /* Create pre-headers. */ |
d78f3f78 | 81 | if (flags & LOOPS_HAVE_PREHEADERS) |
e855c69d AB |
82 | { |
83 | int cp_flags = CP_SIMPLE_PREHEADERS; | |
84 | ||
85 | if (flags & LOOPS_HAVE_FALLTHRU_PREHEADERS) | |
86 | cp_flags |= CP_FALLTHRU_PREHEADERS; | |
b8698a0f | 87 | |
e855c69d AB |
88 | create_preheaders (cp_flags); |
89 | } | |
617b465c ZD |
90 | |
91 | /* Force all latches to have only single successor. */ | |
d78f3f78 | 92 | if (flags & LOOPS_HAVE_SIMPLE_LATCHES) |
d73be268 | 93 | force_single_succ_latches (); |
617b465c ZD |
94 | |
95 | /* Mark irreducible loops. */ | |
d78f3f78 | 96 | if (flags & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) |
d73be268 | 97 | mark_irreducible_loops (); |
d78f3f78 | 98 | |
6270df4c ZD |
99 | if (flags & LOOPS_HAVE_RECORDED_EXITS) |
100 | record_loop_exits (); | |
617b465c ZD |
101 | |
102 | /* Dump loops. */ | |
d73be268 | 103 | flow_loops_dump (dump_file, NULL, 1); |
617b465c ZD |
104 | |
105 | #ifdef ENABLE_CHECKING | |
d73be268 | 106 | verify_loop_structure (); |
617b465c | 107 | #endif |
617b465c ZD |
108 | } |
109 | ||
598ec7bd ZD |
110 | /* Finalize loop structures. */ |
111 | ||
617b465c | 112 | void |
598ec7bd | 113 | loop_optimizer_finalize (void) |
617b465c | 114 | { |
42fd6772 ZD |
115 | loop_iterator li; |
116 | struct loop *loop; | |
598ec7bd | 117 | basic_block bb; |
617b465c | 118 | |
7d776ee2 RG |
119 | if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS)) |
120 | release_recorded_exits (); | |
121 | ||
122 | /* If we should preserve loop structure, do not free it but clear | |
123 | flags that advanced properties are there as we are not preserving | |
124 | that in full. */ | |
125 | if (cfun->curr_properties & PROP_loops) | |
126 | { | |
127 | loops_state_clear (LOOP_CLOSED_SSA | |
128 | | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS | |
129 | | LOOPS_HAVE_PREHEADERS | |
130 | | LOOPS_HAVE_SIMPLE_LATCHES | |
131 | | LOOPS_HAVE_FALLTHRU_PREHEADERS); | |
132 | return; | |
133 | } | |
134 | ||
d51157de | 135 | gcc_assert (current_loops != NULL); |
50654f6c | 136 | |
42fd6772 ZD |
137 | FOR_EACH_LOOP (li, loop, 0) |
138 | { | |
139 | free_simple_loop_desc (loop); | |
140 | } | |
617b465c | 141 | |
617b465c | 142 | /* Clean up. */ |
598ec7bd | 143 | flow_loops_free (current_loops); |
9e2f83a5 | 144 | ggc_free (current_loops); |
598ec7bd ZD |
145 | current_loops = NULL; |
146 | ||
147 | FOR_ALL_BB (bb) | |
148 | { | |
149 | bb->loop_father = NULL; | |
150 | } | |
617b465c | 151 | } |
9fa26457 | 152 | |
ef330312 | 153 | \f |
9fa26457 SB |
154 | /* Gate for the RTL loop superpass. The actual passes are subpasses. |
155 | See passes.c for more on that. */ | |
156 | ||
ef330312 PB |
157 | static bool |
158 | gate_handle_loop2 (void) | |
159 | { | |
225820ee RG |
160 | if (optimize > 0 |
161 | && (flag_move_loop_invariants | |
162 | || flag_unswitch_loops | |
163 | || flag_peel_loops | |
164 | || flag_unroll_loops | |
1f922264 | 165 | #ifdef HAVE_doloop_end |
225820ee | 166 | || (flag_branch_on_count_reg && HAVE_doloop_end) |
1f922264 | 167 | #endif |
225820ee RG |
168 | )) |
169 | return true; | |
170 | else | |
171 | { | |
172 | /* No longer preserve loops, remove them now. */ | |
173 | cfun->curr_properties &= ~PROP_loops; | |
174 | if (current_loops) | |
175 | loop_optimizer_finalize (); | |
176 | return false; | |
177 | } | |
ef330312 PB |
178 | } |
179 | ||
8ddbbcae | 180 | struct rtl_opt_pass pass_loop2 = |
ef330312 | 181 | { |
8ddbbcae JH |
182 | { |
183 | RTL_PASS, | |
9fa26457 SB |
184 | "loop2", /* name */ |
185 | gate_handle_loop2, /* gate */ | |
186 | NULL, /* execute */ | |
187 | NULL, /* sub */ | |
188 | NULL, /* next */ | |
189 | 0, /* static_pass_number */ | |
190 | TV_LOOP, /* tv_id */ | |
191 | 0, /* properties_required */ | |
192 | 0, /* properties_provided */ | |
193 | 0, /* properties_destroyed */ | |
194 | 0, /* todo_flags_start */ | |
8ddbbcae JH |
195 | TODO_ggc_collect /* todo_flags_finish */ |
196 | } | |
9fa26457 | 197 | }; |
ef330312 | 198 | |
9fa26457 SB |
199 | \f |
200 | /* Initialization of the RTL loop passes. */ | |
c2924966 | 201 | static unsigned int |
9fa26457 SB |
202 | rtl_loop_init (void) |
203 | { | |
ad21dab7 | 204 | gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT); |
b8698a0f | 205 | |
ef330312 | 206 | if (dump_file) |
532aafad SB |
207 | { |
208 | dump_reg_info (dump_file); | |
209 | dump_flow_info (dump_file, dump_flags); | |
210 | } | |
ef330312 | 211 | |
598ec7bd | 212 | loop_optimizer_init (LOOPS_NORMAL); |
c2924966 | 213 | return 0; |
9fa26457 | 214 | } |
ef330312 | 215 | |
8ddbbcae | 216 | struct rtl_opt_pass pass_rtl_loop_init = |
9fa26457 | 217 | { |
8ddbbcae JH |
218 | { |
219 | RTL_PASS, | |
defb77dc | 220 | "loop2_init", /* name */ |
9fa26457 SB |
221 | NULL, /* gate */ |
222 | rtl_loop_init, /* execute */ | |
223 | NULL, /* sub */ | |
224 | NULL, /* next */ | |
225 | 0, /* static_pass_number */ | |
226 | TV_LOOP, /* tv_id */ | |
227 | 0, /* properties_required */ | |
228 | 0, /* properties_provided */ | |
229 | 0, /* properties_destroyed */ | |
230 | 0, /* todo_flags_start */ | |
22c5fa5f | 231 | TODO_verify_rtl_sharing /* todo_flags_finish */ |
8ddbbcae | 232 | } |
9fa26457 | 233 | }; |
ef330312 | 234 | |
9fa26457 SB |
235 | \f |
236 | /* Finalization of the RTL loop passes. */ | |
598ec7bd | 237 | |
c2924966 | 238 | static unsigned int |
9fa26457 SB |
239 | rtl_loop_done (void) |
240 | { | |
7d776ee2 RG |
241 | /* No longer preserve loops, remove them now. */ |
242 | cfun->curr_properties &= ~PROP_loops; | |
598ec7bd | 243 | loop_optimizer_finalize (); |
ef330312 PB |
244 | free_dominance_info (CDI_DOMINATORS); |
245 | ||
6fb5fa3c | 246 | cleanup_cfg (0); |
ef330312 | 247 | if (dump_file) |
532aafad SB |
248 | { |
249 | dump_reg_info (dump_file); | |
250 | dump_flow_info (dump_file, dump_flags); | |
251 | } | |
9fa26457 | 252 | |
c2924966 | 253 | return 0; |
ef330312 PB |
254 | } |
255 | ||
8ddbbcae | 256 | struct rtl_opt_pass pass_rtl_loop_done = |
ef330312 | 257 | { |
8ddbbcae JH |
258 | { |
259 | RTL_PASS, | |
defb77dc | 260 | "loop2_done", /* name */ |
9fa26457 SB |
261 | NULL, /* gate */ |
262 | rtl_loop_done, /* execute */ | |
ef330312 PB |
263 | NULL, /* sub */ |
264 | NULL, /* next */ | |
265 | 0, /* static_pass_number */ | |
266 | TV_LOOP, /* tv_id */ | |
267 | 0, /* properties_required */ | |
268 | 0, /* properties_provided */ | |
7d776ee2 | 269 | PROP_loops, /* properties_destroyed */ |
ef330312 | 270 | 0, /* todo_flags_start */ |
c7dd803e | 271 | TODO_verify_flow |
22c5fa5f | 272 | | TODO_verify_rtl_sharing /* todo_flags_finish */ |
8ddbbcae | 273 | } |
9fa26457 SB |
274 | }; |
275 | ||
276 | \f | |
277 | /* Loop invariant code motion. */ | |
defb77dc PB |
278 | static bool |
279 | gate_rtl_move_loop_invariants (void) | |
280 | { | |
281 | return flag_move_loop_invariants; | |
282 | } | |
283 | ||
c2924966 | 284 | static unsigned int |
9fa26457 SB |
285 | rtl_move_loop_invariants (void) |
286 | { | |
d51157de | 287 | if (number_of_loops () > 1) |
d73be268 | 288 | move_loop_invariants (); |
c2924966 | 289 | return 0; |
9fa26457 SB |
290 | } |
291 | ||
8ddbbcae | 292 | struct rtl_opt_pass pass_rtl_move_loop_invariants = |
9fa26457 | 293 | { |
8ddbbcae JH |
294 | { |
295 | RTL_PASS, | |
6fb5fa3c | 296 | "loop2_invariant", /* name */ |
defb77dc | 297 | gate_rtl_move_loop_invariants, /* gate */ |
9fa26457 SB |
298 | rtl_move_loop_invariants, /* execute */ |
299 | NULL, /* sub */ | |
300 | NULL, /* next */ | |
301 | 0, /* static_pass_number */ | |
b56ae8c7 | 302 | TV_LOOP_MOVE_INVARIANTS, /* tv_id */ |
9fa26457 SB |
303 | 0, /* properties_required */ |
304 | 0, /* properties_provided */ | |
305 | 0, /* properties_destroyed */ | |
b8698a0f | 306 | 0, /* todo_flags_start */ |
0d475361 | 307 | TODO_df_verify | |
22c5fa5f | 308 | TODO_df_finish | TODO_verify_rtl_sharing /* todo_flags_finish */ |
8ddbbcae | 309 | } |
9fa26457 SB |
310 | }; |
311 | ||
312 | \f | |
313 | /* Loop unswitching for RTL. */ | |
defb77dc PB |
314 | static bool |
315 | gate_rtl_unswitch (void) | |
316 | { | |
317 | return flag_unswitch_loops; | |
318 | } | |
319 | ||
c2924966 | 320 | static unsigned int |
9fa26457 SB |
321 | rtl_unswitch (void) |
322 | { | |
d51157de | 323 | if (number_of_loops () > 1) |
d73be268 | 324 | unswitch_loops (); |
c2924966 | 325 | return 0; |
9fa26457 SB |
326 | } |
327 | ||
8ddbbcae | 328 | struct rtl_opt_pass pass_rtl_unswitch = |
9fa26457 | 329 | { |
8ddbbcae JH |
330 | { |
331 | RTL_PASS, | |
defb77dc PB |
332 | "loop2_unswitch", /* name */ |
333 | gate_rtl_unswitch, /* gate */ | |
9fa26457 SB |
334 | rtl_unswitch, /* execute */ |
335 | NULL, /* sub */ | |
336 | NULL, /* next */ | |
337 | 0, /* static_pass_number */ | |
b56ae8c7 | 338 | TV_LOOP_UNSWITCH, /* tv_id */ |
9fa26457 SB |
339 | 0, /* properties_required */ |
340 | 0, /* properties_provided */ | |
341 | 0, /* properties_destroyed */ | |
342 | 0, /* todo_flags_start */ | |
22c5fa5f | 343 | TODO_verify_rtl_sharing, /* todo_flags_finish */ |
8ddbbcae | 344 | } |
9fa26457 SB |
345 | }; |
346 | ||
347 | \f | |
348 | /* Loop unswitching for RTL. */ | |
defb77dc PB |
349 | static bool |
350 | gate_rtl_unroll_and_peel_loops (void) | |
351 | { | |
352 | return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops); | |
353 | } | |
354 | ||
c2924966 | 355 | static unsigned int |
9fa26457 SB |
356 | rtl_unroll_and_peel_loops (void) |
357 | { | |
d51157de | 358 | if (number_of_loops () > 1) |
9fa26457 SB |
359 | { |
360 | int flags = 0; | |
6fb5fa3c DB |
361 | if (dump_file) |
362 | df_dump (dump_file); | |
9fa26457 SB |
363 | |
364 | if (flag_peel_loops) | |
365 | flags |= UAP_PEEL; | |
366 | if (flag_unroll_loops) | |
367 | flags |= UAP_UNROLL; | |
368 | if (flag_unroll_all_loops) | |
369 | flags |= UAP_UNROLL_ALL; | |
370 | ||
d73be268 | 371 | unroll_and_peel_loops (flags); |
9fa26457 | 372 | } |
c2924966 | 373 | return 0; |
9fa26457 SB |
374 | } |
375 | ||
8ddbbcae | 376 | struct rtl_opt_pass pass_rtl_unroll_and_peel_loops = |
9fa26457 | 377 | { |
8ddbbcae JH |
378 | { |
379 | RTL_PASS, | |
defb77dc PB |
380 | "loop2_unroll", /* name */ |
381 | gate_rtl_unroll_and_peel_loops, /* gate */ | |
9fa26457 SB |
382 | rtl_unroll_and_peel_loops, /* execute */ |
383 | NULL, /* sub */ | |
384 | NULL, /* next */ | |
385 | 0, /* static_pass_number */ | |
b56ae8c7 | 386 | TV_LOOP_UNROLL, /* tv_id */ |
9fa26457 SB |
387 | 0, /* properties_required */ |
388 | 0, /* properties_provided */ | |
389 | 0, /* properties_destroyed */ | |
390 | 0, /* todo_flags_start */ | |
22c5fa5f | 391 | TODO_verify_rtl_sharing, /* todo_flags_finish */ |
8ddbbcae | 392 | } |
9fa26457 SB |
393 | }; |
394 | ||
395 | \f | |
396 | /* The doloop optimization. */ | |
defb77dc PB |
397 | static bool |
398 | gate_rtl_doloop (void) | |
399 | { | |
400 | #ifdef HAVE_doloop_end | |
401 | return (flag_branch_on_count_reg && HAVE_doloop_end); | |
402 | #else | |
403 | return 0; | |
404 | #endif | |
405 | } | |
406 | ||
c2924966 | 407 | static unsigned int |
9fa26457 SB |
408 | rtl_doloop (void) |
409 | { | |
410 | #ifdef HAVE_doloop_end | |
d51157de | 411 | if (number_of_loops () > 1) |
d73be268 | 412 | doloop_optimize_loops (); |
9fa26457 | 413 | #endif |
c2924966 | 414 | return 0; |
9fa26457 SB |
415 | } |
416 | ||
8ddbbcae | 417 | struct rtl_opt_pass pass_rtl_doloop = |
9fa26457 | 418 | { |
8ddbbcae JH |
419 | { |
420 | RTL_PASS, | |
defb77dc PB |
421 | "loop2_doloop", /* name */ |
422 | gate_rtl_doloop, /* gate */ | |
9fa26457 SB |
423 | rtl_doloop, /* execute */ |
424 | NULL, /* sub */ | |
425 | NULL, /* next */ | |
426 | 0, /* static_pass_number */ | |
b56ae8c7 | 427 | TV_LOOP_DOLOOP, /* tv_id */ |
9fa26457 SB |
428 | 0, /* properties_required */ |
429 | 0, /* properties_provided */ | |
430 | 0, /* properties_destroyed */ | |
431 | 0, /* todo_flags_start */ | |
22c5fa5f | 432 | TODO_verify_rtl_sharing /* todo_flags_finish */ |
8ddbbcae | 433 | } |
ef330312 | 434 | }; |