1 /* Loop optimizer initialization routines and RTL loop optimization passes.
2 Copyright (C) 2002-2013 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
9 version.
10
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
19
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "tm.h"
24 #include "rtl.h"
25 #include "regs.h"
26 #include "obstack.h"
27 #include "basic-block.h"
28 #include "cfgloop.h"
29 #include "tree-pass.h"
30 #include "flags.h"
31 #include "df.h"
32 #include "ggc.h"
33
34
35 /* Apply FLAGS to the loop state. */
36
37 static void
apply_loop_flags(unsigned flags)38 apply_loop_flags (unsigned flags)
39 {
40 if (flags & LOOPS_MAY_HAVE_MULTIPLE_LATCHES)
41 {
42 /* If the loops may have multiple latches, we cannot canonicalize
43 them further (and most of the loop manipulation functions will
44 not work). However, we avoid modifying cfg, which some
45 passes may want. */
46 gcc_assert ((flags & ~(LOOPS_MAY_HAVE_MULTIPLE_LATCHES
47 | LOOPS_HAVE_RECORDED_EXITS)) == 0);
48 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
49 }
50 else
51 disambiguate_loops_with_multiple_latches ();
52
53 /* Create pre-headers. */
54 if (flags & LOOPS_HAVE_PREHEADERS)
55 {
56 int cp_flags = CP_SIMPLE_PREHEADERS;
57
58 if (flags & LOOPS_HAVE_FALLTHRU_PREHEADERS)
59 cp_flags |= CP_FALLTHRU_PREHEADERS;
60
61 create_preheaders (cp_flags);
62 }
63
64 /* Force all latches to have only single successor. */
65 if (flags & LOOPS_HAVE_SIMPLE_LATCHES)
66 force_single_succ_latches ();
67
68 /* Mark irreducible loops. */
69 if (flags & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
70 mark_irreducible_loops ();
71
72 if (flags & LOOPS_HAVE_RECORDED_EXITS)
73 record_loop_exits ();
74 }
75
76 /* Initialize loop structures. This is used by the tree and RTL loop
77 optimizers. FLAGS specify what properties to compute and/or ensure for
78 loops. */
79
80 void
loop_optimizer_init(unsigned flags)81 loop_optimizer_init (unsigned flags)
82 {
83 timevar_push (TV_LOOP_INIT);
84
85 if (!current_loops)
86 {
87 gcc_assert (!(cfun->curr_properties & PROP_loops));
88
89 /* Find the loops. */
90 current_loops = flow_loops_find (NULL);
91 }
92 else
93 {
94 gcc_assert (cfun->curr_properties & PROP_loops);
95
96 /* Ensure that the dominators are computed, like flow_loops_find does. */
97 calculate_dominance_info (CDI_DOMINATORS);
98
99 #ifdef ENABLE_CHECKING
100 verify_loop_structure ();
101 #endif
102
103 /* Clear all flags. */
104 loops_state_clear (~0U);
105 }
106
107 /* Apply flags to loops. */
108 apply_loop_flags (flags);
109
110 /* Dump loops. */
111 flow_loops_dump (dump_file, NULL, 1);
112
113 #ifdef ENABLE_CHECKING
114 verify_loop_structure ();
115 #endif
116
117 timevar_pop (TV_LOOP_INIT);
118 }
119
120 /* Finalize loop structures. */
121
122 void
loop_optimizer_finalize(void)123 loop_optimizer_finalize (void)
124 {
125 loop_iterator li;
126 struct loop *loop;
127 basic_block bb;
128
129 timevar_push (TV_LOOP_FINI);
130
131 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
132 release_recorded_exits ();
133
134 /* If we should preserve loop structure, do not free it but clear
135 flags that advanced properties are there as we are not preserving
136 that in full. */
137 if (cfun->curr_properties & PROP_loops)
138 {
139 loops_state_clear (LOOP_CLOSED_SSA
140 | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
141 | LOOPS_HAVE_PREHEADERS
142 | LOOPS_HAVE_SIMPLE_LATCHES
143 | LOOPS_HAVE_FALLTHRU_PREHEADERS);
144 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
145 goto loop_fini_done;
146 }
147
148 gcc_assert (current_loops != NULL);
149
150 FOR_EACH_LOOP (li, loop, 0)
151 {
152 free_simple_loop_desc (loop);
153 }
154
155 /* Clean up. */
156 flow_loops_free (current_loops);
157 ggc_free (current_loops);
158 current_loops = NULL;
159
160 FOR_ALL_BB (bb)
161 {
162 bb->loop_father = NULL;
163 }
164
165 loop_fini_done:
166 timevar_pop (TV_LOOP_FINI);
167 }
168
169 /* The structure of loops might have changed. Some loops might get removed
170 (and their headers and latches were set to NULL), loop exists might get
171 removed (thus the loop nesting may be wrong), and some blocks and edges
172 were changed (so the information about bb --> loop mapping does not have
173 to be correct). But still for the remaining loops the header dominates
174 the latch, and loops did not get new subloops (new loops might possibly
175 get created, but we are not interested in them). Fix up the mess.
176
177 If CHANGED_BBS is not NULL, basic blocks whose loop depth has changed are
178 marked in it.
179
180 Returns the number of new discovered loops. */
181
182 unsigned
fix_loop_structure(bitmap changed_bbs)183 fix_loop_structure (bitmap changed_bbs)
184 {
185 basic_block bb;
186 int record_exits = 0;
187 loop_iterator li;
188 struct loop *loop;
189 unsigned old_nloops, i;
190
191 timevar_push (TV_LOOP_INIT);
192
193 /* We need exact and fast dominance info to be available. */
194 gcc_assert (dom_info_state (CDI_DOMINATORS) == DOM_OK);
195
196 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
197 {
198 release_recorded_exits ();
199 record_exits = LOOPS_HAVE_RECORDED_EXITS;
200 }
201
202 /* Remember the depth of the blocks in the loop hierarchy, so that we can
203 recognize blocks whose loop nesting relationship has changed. */
204 if (changed_bbs)
205 FOR_EACH_BB (bb)
206 bb->aux = (void *) (size_t) loop_depth (bb->loop_father);
207
208 /* Remove the dead loops from structures. We start from the innermost
209 loops, so that when we remove the loops, we know that the loops inside
210 are preserved, and do not waste time relinking loops that will be
211 removed later. */
212 FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
213 {
214 /* Detect the case that the loop is no longer present even though
215 it wasn't marked for removal.
216 ??? If we do that we can get away with not marking loops for
217 removal at all. And possibly avoid some spurious removals. */
218 if (loop->header
219 && bb_loop_header_p (loop->header))
220 continue;
221
222 if (dump_file && (dump_flags & TDF_DETAILS))
223 fprintf (dump_file, "fix_loop_structure: removing loop %d\n",
224 loop->num);
225
226 while (loop->inner)
227 {
228 struct loop *ploop = loop->inner;
229 flow_loop_tree_node_remove (ploop);
230 flow_loop_tree_node_add (loop_outer (loop), ploop);
231 }
232
233 /* Remove the loop. */
234 loop->header = NULL;
235 flow_loop_tree_node_remove (loop);
236 }
237
238 /* Remember the number of loops so we can return how many new loops
239 flow_loops_find discovered. */
240 old_nloops = number_of_loops ();
241
242 /* Re-compute loop structure in-place. */
243 flow_loops_find (current_loops);
244
245 /* Mark the blocks whose loop has changed. */
246 if (changed_bbs)
247 {
248 FOR_EACH_BB (bb)
249 {
250 if ((void *) (size_t) loop_depth (bb->loop_father) != bb->aux)
251 bitmap_set_bit (changed_bbs, bb->index);
252
253 bb->aux = NULL;
254 }
255 }
256
257 /* Finally free deleted loops. */
258 FOR_EACH_VEC_ELT (*get_loops (), i, loop)
259 if (loop && loop->header == NULL)
260 {
261 (*get_loops ())[i] = NULL;
262 flow_loop_free (loop);
263 }
264
265 loops_state_clear (LOOPS_NEED_FIXUP);
266
267 /* Apply flags to loops. */
268 apply_loop_flags (current_loops->state | record_exits);
269
270 #ifdef ENABLE_CHECKING
271 verify_loop_structure ();
272 #endif
273
274 timevar_pop (TV_LOOP_INIT);
275
276 return number_of_loops () - old_nloops;
277 }
278
279 /* Gate for the RTL loop superpass. The actual passes are subpasses.
280 See passes.c for more on that. */
281
282 static bool
gate_handle_loop2(void)283 gate_handle_loop2 (void)
284 {
285 if (optimize > 0
286 && (flag_move_loop_invariants
287 || flag_unswitch_loops
288 || flag_peel_loops
289 || flag_unroll_loops
290 #ifdef HAVE_doloop_end
291 || (flag_branch_on_count_reg && HAVE_doloop_end)
292 #endif
293 ))
294 return true;
295 else
296 {
297 /* No longer preserve loops, remove them now. */
298 cfun->curr_properties &= ~PROP_loops;
299 if (current_loops)
300 loop_optimizer_finalize ();
301 return false;
302 }
303 }
304
305 struct rtl_opt_pass pass_loop2 =
306 {
307 {
308 RTL_PASS,
309 "loop2", /* name */
310 OPTGROUP_LOOP, /* optinfo_flags */
311 gate_handle_loop2, /* gate */
312 NULL, /* execute */
313 NULL, /* sub */
314 NULL, /* next */
315 0, /* static_pass_number */
316 TV_LOOP, /* tv_id */
317 0, /* properties_required */
318 0, /* properties_provided */
319 0, /* properties_destroyed */
320 0, /* todo_flags_start */
321 TODO_ggc_collect /* todo_flags_finish */
322 }
323 };
324
325
326 /* Initialization of the RTL loop passes. */
327 static unsigned int
rtl_loop_init(void)328 rtl_loop_init (void)
329 {
330 gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
331
332 if (dump_file)
333 {
334 dump_reg_info (dump_file);
335 dump_flow_info (dump_file, dump_flags);
336 }
337
338 loop_optimizer_init (LOOPS_NORMAL);
339 return 0;
340 }
341
342 struct rtl_opt_pass pass_rtl_loop_init =
343 {
344 {
345 RTL_PASS,
346 "loop2_init", /* name */
347 OPTGROUP_LOOP, /* optinfo_flags */
348 NULL, /* gate */
349 rtl_loop_init, /* execute */
350 NULL, /* sub */
351 NULL, /* next */
352 0, /* static_pass_number */
353 TV_LOOP, /* tv_id */
354 0, /* properties_required */
355 0, /* properties_provided */
356 0, /* properties_destroyed */
357 0, /* todo_flags_start */
358 TODO_verify_rtl_sharing /* todo_flags_finish */
359 }
360 };
361
362
363 /* Finalization of the RTL loop passes. */
364
365 static unsigned int
rtl_loop_done(void)366 rtl_loop_done (void)
367 {
368 /* No longer preserve loops, remove them now. */
369 cfun->curr_properties &= ~PROP_loops;
370 loop_optimizer_finalize ();
371 free_dominance_info (CDI_DOMINATORS);
372
373 cleanup_cfg (0);
374 if (dump_file)
375 {
376 dump_reg_info (dump_file);
377 dump_flow_info (dump_file, dump_flags);
378 }
379
380 return 0;
381 }
382
383 struct rtl_opt_pass pass_rtl_loop_done =
384 {
385 {
386 RTL_PASS,
387 "loop2_done", /* name */
388 OPTGROUP_LOOP, /* optinfo_flags */
389 NULL, /* gate */
390 rtl_loop_done, /* execute */
391 NULL, /* sub */
392 NULL, /* next */
393 0, /* static_pass_number */
394 TV_LOOP, /* tv_id */
395 0, /* properties_required */
396 0, /* properties_provided */
397 PROP_loops, /* properties_destroyed */
398 0, /* todo_flags_start */
399 TODO_verify_flow
400 | TODO_verify_rtl_sharing /* todo_flags_finish */
401 }
402 };
403
404
405 /* Loop invariant code motion. */
406 static bool
gate_rtl_move_loop_invariants(void)407 gate_rtl_move_loop_invariants (void)
408 {
409 return flag_move_loop_invariants;
410 }
411
412 static unsigned int
rtl_move_loop_invariants(void)413 rtl_move_loop_invariants (void)
414 {
415 if (number_of_loops () > 1)
416 move_loop_invariants ();
417 return 0;
418 }
419
420 struct rtl_opt_pass pass_rtl_move_loop_invariants =
421 {
422 {
423 RTL_PASS,
424 "loop2_invariant", /* name */
425 OPTGROUP_LOOP, /* optinfo_flags */
426 gate_rtl_move_loop_invariants, /* gate */
427 rtl_move_loop_invariants, /* execute */
428 NULL, /* sub */
429 NULL, /* next */
430 0, /* static_pass_number */
431 TV_LOOP_MOVE_INVARIANTS, /* tv_id */
432 0, /* properties_required */
433 0, /* properties_provided */
434 0, /* properties_destroyed */
435 0, /* todo_flags_start */
436 TODO_df_verify |
437 TODO_df_finish | TODO_verify_rtl_sharing /* todo_flags_finish */
438 }
439 };
440
441
442 /* Loop unswitching for RTL. */
443 static bool
gate_rtl_unswitch(void)444 gate_rtl_unswitch (void)
445 {
446 return flag_unswitch_loops;
447 }
448
449 static unsigned int
rtl_unswitch(void)450 rtl_unswitch (void)
451 {
452 if (number_of_loops () > 1)
453 unswitch_loops ();
454 return 0;
455 }
456
457 struct rtl_opt_pass pass_rtl_unswitch =
458 {
459 {
460 RTL_PASS,
461 "loop2_unswitch", /* name */
462 OPTGROUP_LOOP, /* optinfo_flags */
463 gate_rtl_unswitch, /* gate */
464 rtl_unswitch, /* execute */
465 NULL, /* sub */
466 NULL, /* next */
467 0, /* static_pass_number */
468 TV_LOOP_UNSWITCH, /* tv_id */
469 0, /* properties_required */
470 0, /* properties_provided */
471 0, /* properties_destroyed */
472 0, /* todo_flags_start */
473 TODO_verify_rtl_sharing, /* todo_flags_finish */
474 }
475 };
476
477
478 /* Loop unswitching for RTL. */
479 static bool
gate_rtl_unroll_and_peel_loops(void)480 gate_rtl_unroll_and_peel_loops (void)
481 {
482 return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops);
483 }
484
485 static unsigned int
rtl_unroll_and_peel_loops(void)486 rtl_unroll_and_peel_loops (void)
487 {
488 if (number_of_loops () > 1)
489 {
490 int flags = 0;
491 if (dump_file)
492 df_dump (dump_file);
493
494 if (flag_peel_loops)
495 flags |= UAP_PEEL;
496 if (flag_unroll_loops)
497 flags |= UAP_UNROLL;
498 if (flag_unroll_all_loops)
499 flags |= UAP_UNROLL_ALL;
500
501 unroll_and_peel_loops (flags);
502 }
503 return 0;
504 }
505
506 struct rtl_opt_pass pass_rtl_unroll_and_peel_loops =
507 {
508 {
509 RTL_PASS,
510 "loop2_unroll", /* name */
511 OPTGROUP_LOOP, /* optinfo_flags */
512 gate_rtl_unroll_and_peel_loops, /* gate */
513 rtl_unroll_and_peel_loops, /* execute */
514 NULL, /* sub */
515 NULL, /* next */
516 0, /* static_pass_number */
517 TV_LOOP_UNROLL, /* tv_id */
518 0, /* properties_required */
519 0, /* properties_provided */
520 0, /* properties_destroyed */
521 0, /* todo_flags_start */
522 TODO_verify_rtl_sharing, /* todo_flags_finish */
523 }
524 };
525
526
527 /* The doloop optimization. */
528 static bool
gate_rtl_doloop(void)529 gate_rtl_doloop (void)
530 {
531 #ifdef HAVE_doloop_end
532 return (flag_branch_on_count_reg && HAVE_doloop_end);
533 #else
534 return 0;
535 #endif
536 }
537
538 static unsigned int
rtl_doloop(void)539 rtl_doloop (void)
540 {
541 #ifdef HAVE_doloop_end
542 if (number_of_loops () > 1)
543 doloop_optimize_loops ();
544 #endif
545 return 0;
546 }
547
548 struct rtl_opt_pass pass_rtl_doloop =
549 {
550 {
551 RTL_PASS,
552 "loop2_doloop", /* name */
553 OPTGROUP_LOOP, /* optinfo_flags */
554 gate_rtl_doloop, /* gate */
555 rtl_doloop, /* execute */
556 NULL, /* sub */
557 NULL, /* next */
558 0, /* static_pass_number */
559 TV_LOOP_DOLOOP, /* tv_id */
560 0, /* properties_required */
561 0, /* properties_provided */
562 0, /* properties_destroyed */
563 0, /* todo_flags_start */
564 TODO_verify_rtl_sharing /* todo_flags_finish */
565 }
566 };
567