]>
Commit | Line | Data |
---|---|---|
0526a3ff | 1 | /* Loop optimizer initialization routines and RTL loop optimization passes. |
d91f7526 | 2 | Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2010 |
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" |
31 | #include "timevar.h" | |
32 | #include "flags.h" | |
3072d30e | 33 | #include "df.h" |
ccae4f9f | 34 | #include "ggc.h" |
6a606e3c | 35 | |
0526a3ff | 36 | \f |
88e6f696 | 37 | /* Initialize loop structures. This is used by the tree and RTL loop |
c8d055f6 | 38 | optimizers. FLAGS specify what properties to compute and/or ensure for |
39 | loops. */ | |
6a606e3c | 40 | |
88e6f696 | 41 | void |
3f5be5f4 | 42 | loop_optimizer_init (unsigned flags) |
6a606e3c | 43 | { |
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 |
6a606e3c | 108 | } |
109 | ||
88e6f696 | 110 | /* Finalize loop structures. */ |
111 | ||
6a606e3c | 112 | void |
88e6f696 | 113 | loop_optimizer_finalize (void) |
6a606e3c | 114 | { |
17519ba0 | 115 | loop_iterator li; |
116 | struct loop *loop; | |
88e6f696 | 117 | basic_block bb; |
6a606e3c | 118 | |
79f958cb | 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 | ||
7a3bf727 | 135 | gcc_assert (current_loops != NULL); |
f9cce2dc | 136 | |
17519ba0 | 137 | FOR_EACH_LOOP (li, loop, 0) |
138 | { | |
139 | free_simple_loop_desc (loop); | |
140 | } | |
6a606e3c | 141 | |
6a606e3c | 142 | /* Clean up. */ |
88e6f696 | 143 | flow_loops_free (current_loops); |
ccae4f9f | 144 | ggc_free (current_loops); |
88e6f696 | 145 | current_loops = NULL; |
146 | ||
147 | FOR_ALL_BB (bb) | |
148 | { | |
149 | bb->loop_father = NULL; | |
150 | } | |
6a606e3c | 151 | } |
0526a3ff | 152 | |
77fce4cd | 153 | \f |
0526a3ff | 154 | /* Gate for the RTL loop superpass. The actual passes are subpasses. |
155 | See passes.c for more on that. */ | |
156 | ||
77fce4cd | 157 | static bool |
158 | gate_handle_loop2 (void) | |
159 | { | |
759626e6 | 160 | if (optimize > 0 |
161 | && (flag_move_loop_invariants | |
162 | || flag_unswitch_loops | |
163 | || flag_peel_loops | |
164 | || flag_unroll_loops | |
a82484af | 165 | #ifdef HAVE_doloop_end |
759626e6 | 166 | || (flag_branch_on_count_reg && HAVE_doloop_end) |
a82484af | 167 | #endif |
759626e6 | 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 | } | |
77fce4cd | 178 | } |
179 | ||
20099e35 | 180 | struct rtl_opt_pass pass_loop2 = |
77fce4cd | 181 | { |
20099e35 | 182 | { |
183 | RTL_PASS, | |
0526a3ff | 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 */ | |
20099e35 | 195 | TODO_ggc_collect /* todo_flags_finish */ |
196 | } | |
0526a3ff | 197 | }; |
77fce4cd | 198 | |
0526a3ff | 199 | \f |
200 | /* Initialization of the RTL loop passes. */ | |
2a1990e9 | 201 | static unsigned int |
0526a3ff | 202 | rtl_loop_init (void) |
203 | { | |
207c7ab2 | 204 | gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT); |
48e1416a | 205 | |
77fce4cd | 206 | if (dump_file) |
4a020a8c | 207 | { |
208 | dump_reg_info (dump_file); | |
209 | dump_flow_info (dump_file, dump_flags); | |
210 | } | |
77fce4cd | 211 | |
88e6f696 | 212 | loop_optimizer_init (LOOPS_NORMAL); |
2a1990e9 | 213 | return 0; |
0526a3ff | 214 | } |
77fce4cd | 215 | |
20099e35 | 216 | struct rtl_opt_pass pass_rtl_loop_init = |
0526a3ff | 217 | { |
20099e35 | 218 | { |
219 | RTL_PASS, | |
228967a9 | 220 | "loop2_init", /* name */ |
0526a3ff | 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 */ | |
771e2890 | 231 | TODO_verify_rtl_sharing /* todo_flags_finish */ |
20099e35 | 232 | } |
0526a3ff | 233 | }; |
77fce4cd | 234 | |
0526a3ff | 235 | \f |
236 | /* Finalization of the RTL loop passes. */ | |
88e6f696 | 237 | |
2a1990e9 | 238 | static unsigned int |
0526a3ff | 239 | rtl_loop_done (void) |
240 | { | |
79f958cb | 241 | /* No longer preserve loops, remove them now. */ |
242 | cfun->curr_properties &= ~PROP_loops; | |
88e6f696 | 243 | loop_optimizer_finalize (); |
77fce4cd | 244 | free_dominance_info (CDI_DOMINATORS); |
245 | ||
3072d30e | 246 | cleanup_cfg (0); |
77fce4cd | 247 | if (dump_file) |
4a020a8c | 248 | { |
249 | dump_reg_info (dump_file); | |
250 | dump_flow_info (dump_file, dump_flags); | |
251 | } | |
0526a3ff | 252 | |
2a1990e9 | 253 | return 0; |
77fce4cd | 254 | } |
255 | ||
20099e35 | 256 | struct rtl_opt_pass pass_rtl_loop_done = |
77fce4cd | 257 | { |
20099e35 | 258 | { |
259 | RTL_PASS, | |
228967a9 | 260 | "loop2_done", /* name */ |
0526a3ff | 261 | NULL, /* gate */ |
262 | rtl_loop_done, /* execute */ | |
77fce4cd | 263 | NULL, /* sub */ |
264 | NULL, /* next */ | |
265 | 0, /* static_pass_number */ | |
266 | TV_LOOP, /* tv_id */ | |
267 | 0, /* properties_required */ | |
268 | 0, /* properties_provided */ | |
79f958cb | 269 | PROP_loops, /* properties_destroyed */ |
77fce4cd | 270 | 0, /* todo_flags_start */ |
a2676c4f | 271 | TODO_verify_flow |
771e2890 | 272 | | TODO_verify_rtl_sharing /* todo_flags_finish */ |
20099e35 | 273 | } |
0526a3ff | 274 | }; |
275 | ||
276 | \f | |
277 | /* Loop invariant code motion. */ | |
228967a9 | 278 | static bool |
279 | gate_rtl_move_loop_invariants (void) | |
280 | { | |
281 | return flag_move_loop_invariants; | |
282 | } | |
283 | ||
2a1990e9 | 284 | static unsigned int |
0526a3ff | 285 | rtl_move_loop_invariants (void) |
286 | { | |
7a3bf727 | 287 | if (number_of_loops () > 1) |
7194de72 | 288 | move_loop_invariants (); |
2a1990e9 | 289 | return 0; |
0526a3ff | 290 | } |
291 | ||
20099e35 | 292 | struct rtl_opt_pass pass_rtl_move_loop_invariants = |
0526a3ff | 293 | { |
20099e35 | 294 | { |
295 | RTL_PASS, | |
3072d30e | 296 | "loop2_invariant", /* name */ |
228967a9 | 297 | gate_rtl_move_loop_invariants, /* gate */ |
0526a3ff | 298 | rtl_move_loop_invariants, /* execute */ |
299 | NULL, /* sub */ | |
300 | NULL, /* next */ | |
301 | 0, /* static_pass_number */ | |
5f34746b | 302 | TV_LOOP_MOVE_INVARIANTS, /* tv_id */ |
0526a3ff | 303 | 0, /* properties_required */ |
304 | 0, /* properties_provided */ | |
305 | 0, /* properties_destroyed */ | |
48e1416a | 306 | 0, /* todo_flags_start */ |
314966f4 | 307 | TODO_df_verify | |
771e2890 | 308 | TODO_df_finish | TODO_verify_rtl_sharing /* todo_flags_finish */ |
20099e35 | 309 | } |
0526a3ff | 310 | }; |
311 | ||
312 | \f | |
313 | /* Loop unswitching for RTL. */ | |
228967a9 | 314 | static bool |
315 | gate_rtl_unswitch (void) | |
316 | { | |
317 | return flag_unswitch_loops; | |
318 | } | |
319 | ||
2a1990e9 | 320 | static unsigned int |
0526a3ff | 321 | rtl_unswitch (void) |
322 | { | |
7a3bf727 | 323 | if (number_of_loops () > 1) |
7194de72 | 324 | unswitch_loops (); |
2a1990e9 | 325 | return 0; |
0526a3ff | 326 | } |
327 | ||
20099e35 | 328 | struct rtl_opt_pass pass_rtl_unswitch = |
0526a3ff | 329 | { |
20099e35 | 330 | { |
331 | RTL_PASS, | |
228967a9 | 332 | "loop2_unswitch", /* name */ |
333 | gate_rtl_unswitch, /* gate */ | |
0526a3ff | 334 | rtl_unswitch, /* execute */ |
335 | NULL, /* sub */ | |
336 | NULL, /* next */ | |
337 | 0, /* static_pass_number */ | |
5f34746b | 338 | TV_LOOP_UNSWITCH, /* tv_id */ |
0526a3ff | 339 | 0, /* properties_required */ |
340 | 0, /* properties_provided */ | |
341 | 0, /* properties_destroyed */ | |
342 | 0, /* todo_flags_start */ | |
771e2890 | 343 | TODO_verify_rtl_sharing, /* todo_flags_finish */ |
20099e35 | 344 | } |
0526a3ff | 345 | }; |
346 | ||
347 | \f | |
348 | /* Loop unswitching for RTL. */ | |
228967a9 | 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 | ||
2a1990e9 | 355 | static unsigned int |
0526a3ff | 356 | rtl_unroll_and_peel_loops (void) |
357 | { | |
7a3bf727 | 358 | if (number_of_loops () > 1) |
0526a3ff | 359 | { |
360 | int flags = 0; | |
3072d30e | 361 | if (dump_file) |
362 | df_dump (dump_file); | |
0526a3ff | 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 | ||
7194de72 | 371 | unroll_and_peel_loops (flags); |
0526a3ff | 372 | } |
2a1990e9 | 373 | return 0; |
0526a3ff | 374 | } |
375 | ||
20099e35 | 376 | struct rtl_opt_pass pass_rtl_unroll_and_peel_loops = |
0526a3ff | 377 | { |
20099e35 | 378 | { |
379 | RTL_PASS, | |
228967a9 | 380 | "loop2_unroll", /* name */ |
381 | gate_rtl_unroll_and_peel_loops, /* gate */ | |
0526a3ff | 382 | rtl_unroll_and_peel_loops, /* execute */ |
383 | NULL, /* sub */ | |
384 | NULL, /* next */ | |
385 | 0, /* static_pass_number */ | |
5f34746b | 386 | TV_LOOP_UNROLL, /* tv_id */ |
0526a3ff | 387 | 0, /* properties_required */ |
388 | 0, /* properties_provided */ | |
389 | 0, /* properties_destroyed */ | |
390 | 0, /* todo_flags_start */ | |
771e2890 | 391 | TODO_verify_rtl_sharing, /* todo_flags_finish */ |
20099e35 | 392 | } |
0526a3ff | 393 | }; |
394 | ||
395 | \f | |
396 | /* The doloop optimization. */ | |
228967a9 | 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 | ||
2a1990e9 | 407 | static unsigned int |
0526a3ff | 408 | rtl_doloop (void) |
409 | { | |
410 | #ifdef HAVE_doloop_end | |
7a3bf727 | 411 | if (number_of_loops () > 1) |
7194de72 | 412 | doloop_optimize_loops (); |
0526a3ff | 413 | #endif |
2a1990e9 | 414 | return 0; |
0526a3ff | 415 | } |
416 | ||
20099e35 | 417 | struct rtl_opt_pass pass_rtl_doloop = |
0526a3ff | 418 | { |
20099e35 | 419 | { |
420 | RTL_PASS, | |
228967a9 | 421 | "loop2_doloop", /* name */ |
422 | gate_rtl_doloop, /* gate */ | |
0526a3ff | 423 | rtl_doloop, /* execute */ |
424 | NULL, /* sub */ | |
425 | NULL, /* next */ | |
426 | 0, /* static_pass_number */ | |
5f34746b | 427 | TV_LOOP_DOLOOP, /* tv_id */ |
0526a3ff | 428 | 0, /* properties_required */ |
429 | 0, /* properties_provided */ | |
430 | 0, /* properties_destroyed */ | |
431 | 0, /* todo_flags_start */ | |
771e2890 | 432 | TODO_verify_rtl_sharing /* todo_flags_finish */ |
20099e35 | 433 | } |
77fce4cd | 434 | }; |