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