2014-07-12 Paul Thomas <pault@gcc.gnu.org>
[official-gcc.git] / gcc / hw-doloop.c
blob9ab7e65db5f4d728bc51049740c43dd0e77bd7a6
1 /* Code to analyze doloop loops in order for targets to perform late
2 optimizations converting doloops to other forms of hardware loops.
3 Copyright (C) 2011-2014 Free Software Foundation, Inc.
5 This file is part of GCC.
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 3, or (at your option) any later
10 version.
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.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "rtl.h"
26 #include "flags.h"
27 #include "expr.h"
28 #include "hard-reg-set.h"
29 #include "regs.h"
30 #include "basic-block.h"
31 #include "tm_p.h"
32 #include "df.h"
33 #include "cfgloop.h"
34 #include "recog.h"
35 #include "target.h"
36 #include "hw-doloop.h"
37 #include "dumpfile.h"
39 #ifdef HAVE_doloop_end
41 /* Dump information collected in LOOPS. */
42 static void
43 dump_hwloops (hwloop_info loops)
45 hwloop_info loop;
47 for (loop = loops; loop; loop = loop->next)
49 hwloop_info i;
50 basic_block b;
51 unsigned ix;
53 fprintf (dump_file, ";; loop %d: ", loop->loop_no);
54 if (loop->bad)
55 fprintf (dump_file, "(bad) ");
56 fprintf (dump_file, "{head:%d, depth:%d, reg:%u}",
57 loop->head == NULL ? -1 : loop->head->index,
58 loop->depth, REGNO (loop->iter_reg));
60 fprintf (dump_file, " blocks: [ ");
61 for (ix = 0; loop->blocks.iterate (ix, &b); ix++)
62 fprintf (dump_file, "%d ", b->index);
63 fprintf (dump_file, "] ");
65 fprintf (dump_file, " inner loops: [ ");
66 for (ix = 0; loop->loops.iterate (ix, &i); ix++)
67 fprintf (dump_file, "%d ", i->loop_no);
68 fprintf (dump_file, "]\n");
70 fprintf (dump_file, "\n");
73 /* Return true if BB is part of LOOP. */
74 static bool
75 bb_in_loop_p (hwloop_info loop, basic_block bb)
77 return bitmap_bit_p (loop->block_bitmap, bb->index);
80 /* Scan the blocks of LOOP (and its inferiors), and record things such as
81 hard registers set, jumps out of and within the loop. */
82 static void
83 scan_loop (hwloop_info loop)
85 unsigned ix;
86 basic_block bb;
88 if (loop->bad)
89 return;
91 if (REGNO_REG_SET_P (df_get_live_in (loop->successor),
92 REGNO (loop->iter_reg)))
93 loop->iter_reg_used_outside = true;
95 for (ix = 0; loop->blocks.iterate (ix, &bb); ix++)
97 rtx insn;
98 edge e;
99 edge_iterator ei;
101 if (bb != loop->tail)
102 FOR_EACH_EDGE (e, ei, bb->succs)
104 if (bb_in_loop_p (loop, e->dest))
106 if (!(e->flags & EDGE_FALLTHRU))
107 loop->jumps_within = true;
109 else
111 loop->jumps_outof = true;
112 if (!loop->bad)
113 gcc_assert (!REGNO_REG_SET_P (df_get_live_in (e->dest),
114 REGNO (loop->iter_reg)));
118 for (insn = BB_HEAD (bb);
119 insn != NEXT_INSN (BB_END (bb));
120 insn = NEXT_INSN (insn))
122 df_ref def;
123 HARD_REG_SET set_this_insn;
125 if (!NONDEBUG_INSN_P (insn))
126 continue;
128 if (recog_memoized (insn) < 0
129 && (GET_CODE (PATTERN (insn)) == ASM_INPUT
130 || asm_noperands (PATTERN (insn)) >= 0))
131 loop->has_asm = true;
133 CLEAR_HARD_REG_SET (set_this_insn);
134 FOR_EACH_INSN_DEF (def, insn)
136 rtx dreg = DF_REF_REG (def);
138 if (!REG_P (dreg))
139 continue;
141 add_to_hard_reg_set (&set_this_insn, GET_MODE (dreg),
142 REGNO (dreg));
145 if (insn == loop->loop_end)
146 CLEAR_HARD_REG_BIT (set_this_insn, REGNO (loop->iter_reg));
147 else if (reg_mentioned_p (loop->iter_reg, PATTERN (insn)))
148 loop->iter_reg_used = true;
149 IOR_HARD_REG_SET (loop->regs_set_in_loop, set_this_insn);
154 /* Compute the incoming_dest and incoming_src members of LOOP by
155 identifying the edges that jump into the loop. If there is more
156 than one block that jumps into the loop, incoming_src will be set
157 to NULL; likewise, if there is more than one block in the loop that
158 is the destination of an incoming edge, incoming_dest will be NULL.
160 Return true if either of these two fields is nonnull, false
161 otherwise. */
162 static bool
163 process_incoming_edges (hwloop_info loop)
165 edge e;
166 edge_iterator ei;
167 bool first = true;
169 FOR_EACH_EDGE (e, ei, loop->incoming)
171 if (first)
173 loop->incoming_src = e->src;
174 loop->incoming_dest = e->dest;
175 first = false;
177 else
179 if (e->dest != loop->incoming_dest)
180 loop->incoming_dest = NULL;
181 if (e->src != loop->incoming_src)
182 loop->incoming_src = NULL;
185 if (loop->incoming_src == NULL && loop->incoming_dest == NULL)
186 return false;
188 return true;
191 /* Try to identify a forwarder block that jump into LOOP, and add it to
192 the set of blocks in the loop, updating the vector of incoming blocks as
193 well. This transformation gives a second chance to loops we couldn't
194 otherwise handle by increasing the chance that we'll end up with one
195 incoming_src block.
196 Return true if we made a change, false otherwise. */
197 static bool
198 add_forwarder_blocks (hwloop_info loop)
200 edge e;
201 edge_iterator ei;
203 FOR_EACH_EDGE (e, ei, loop->incoming)
205 if (forwarder_block_p (e->src))
207 edge e2;
208 edge_iterator ei2;
210 if (dump_file)
211 fprintf (dump_file,
212 ";; Adding forwarder block %d to loop %d and retrying\n",
213 e->src->index, loop->loop_no);
214 loop->blocks.safe_push (e->src);
215 bitmap_set_bit (loop->block_bitmap, e->src->index);
216 FOR_EACH_EDGE (e2, ei2, e->src->preds)
217 vec_safe_push (loop->incoming, e2);
218 loop->incoming->unordered_remove (ei.index);
219 return true;
222 return false;
225 /* Called from reorg_loops when a potential loop end is found. LOOP is
226 a newly set up structure describing the loop, it is this function's
227 responsibility to fill most of it. TAIL_BB and TAIL_INSN point to the
228 loop_end insn and its enclosing basic block. REG is the loop counter
229 register.
230 For our purposes, a loop is defined by the set of blocks reachable from
231 the loop head in which the loop counter register is live. This matches
232 the expected use; targets that call into this code usually replace the
233 loop counter with a different special register. */
234 static void
235 discover_loop (hwloop_info loop, basic_block tail_bb, rtx tail_insn, rtx reg)
237 bool found_tail;
238 unsigned dwork = 0;
239 basic_block bb;
241 loop->tail = tail_bb;
242 loop->loop_end = tail_insn;
243 loop->iter_reg = reg;
244 vec_alloc (loop->incoming, 2);
245 loop->start_label = JUMP_LABEL (tail_insn);
247 if (EDGE_COUNT (tail_bb->succs) != 2)
249 loop->bad = true;
250 return;
252 loop->head = BRANCH_EDGE (tail_bb)->dest;
253 loop->successor = FALLTHRU_EDGE (tail_bb)->dest;
255 auto_vec<basic_block, 20> works;
256 works.safe_push (loop->head);
258 found_tail = false;
259 for (dwork = 0; works.iterate (dwork, &bb); dwork++)
261 edge e;
262 edge_iterator ei;
263 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
265 /* We've reached the exit block. The loop must be bad. */
266 if (dump_file)
267 fprintf (dump_file,
268 ";; Loop is bad - reached exit block while scanning\n");
269 loop->bad = true;
270 break;
273 if (bitmap_bit_p (loop->block_bitmap, bb->index))
274 continue;
276 /* We've not seen this block before. Add it to the loop's
277 list and then add each successor to the work list. */
279 loop->blocks.safe_push (bb);
280 bitmap_set_bit (loop->block_bitmap, bb->index);
282 if (bb == tail_bb)
283 found_tail = true;
284 else
286 FOR_EACH_EDGE (e, ei, bb->succs)
288 basic_block succ = EDGE_SUCC (bb, ei.index)->dest;
289 if (REGNO_REG_SET_P (df_get_live_in (succ),
290 REGNO (loop->iter_reg)))
291 works.safe_push (succ);
296 if (!found_tail)
297 loop->bad = true;
299 /* Find the predecessor, and make sure nothing else jumps into this loop. */
300 if (!loop->bad)
302 FOR_EACH_VEC_ELT (loop->blocks, dwork, bb)
304 edge e;
305 edge_iterator ei;
306 FOR_EACH_EDGE (e, ei, bb->preds)
308 basic_block pred = e->src;
310 if (!bb_in_loop_p (loop, pred))
312 if (dump_file)
313 fprintf (dump_file, ";; Loop %d: incoming edge %d -> %d\n",
314 loop->loop_no, pred->index,
315 e->dest->index);
316 vec_safe_push (loop->incoming, e);
321 if (!process_incoming_edges (loop))
323 if (dump_file)
324 fprintf (dump_file,
325 ";; retrying loop %d with forwarder blocks\n",
326 loop->loop_no);
327 if (!add_forwarder_blocks (loop))
329 if (dump_file)
330 fprintf (dump_file, ";; No forwarder blocks found\n");
331 loop->bad = true;
333 else if (!process_incoming_edges (loop))
335 if (dump_file)
336 fprintf (dump_file,
337 ";; can't find suitable entry for loop %d\n",
338 loop->loop_no);
344 /* Analyze the structure of the loops in the current function. Use
345 LOOP_STACK for bitmap allocations. Returns all the valid candidates for
346 hardware loops found in this function. HOOKS is the argument
347 passed to reorg_loops, used here to find the iteration registers
348 from a loop_end pattern. */
349 static hwloop_info
350 discover_loops (bitmap_obstack *loop_stack, struct hw_doloop_hooks *hooks)
352 hwloop_info loops = NULL;
353 hwloop_info loop;
354 basic_block bb;
355 int nloops = 0;
357 /* Find all the possible loop tails. This means searching for every
358 loop_end instruction. For each one found, create a hwloop_info
359 structure and add the head block to the work list. */
360 FOR_EACH_BB_FN (bb, cfun)
362 rtx tail = BB_END (bb);
363 rtx insn, reg;
365 while (tail && NOTE_P (tail) && tail != BB_HEAD (bb))
366 tail = PREV_INSN (tail);
368 if (tail == NULL_RTX)
369 continue;
371 if (!JUMP_P (tail))
372 continue;
373 reg = hooks->end_pattern_reg (tail);
374 if (reg == NULL_RTX)
375 continue;
377 /* A possible loop end */
379 /* There's a degenerate case we can handle - an empty loop consisting
380 of only a back branch. Handle that by deleting the branch. */
381 insn = JUMP_LABEL (tail);
382 while (insn && !NONDEBUG_INSN_P (insn))
383 insn = NEXT_INSN (insn);
384 if (insn == tail)
386 basic_block succ = FALLTHRU_EDGE (bb)->dest;
387 if (dump_file)
389 fprintf (dump_file, ";; degenerate loop ending at\n");
390 print_rtl_single (dump_file, tail);
392 if (!REGNO_REG_SET_P (df_get_live_in (succ), REGNO (reg)))
394 if (dump_file)
395 fprintf (dump_file, ";; deleting it\n");
396 delete_insn_and_edges (tail);
397 continue;
401 loop = XCNEW (struct hwloop_info_d);
402 loop->next = loops;
403 loops = loop;
404 loop->loop_no = nloops++;
405 loop->blocks.create (20);
406 loop->block_bitmap = BITMAP_ALLOC (loop_stack);
408 if (dump_file)
410 fprintf (dump_file, ";; potential loop %d ending at\n",
411 loop->loop_no);
412 print_rtl_single (dump_file, tail);
415 discover_loop (loop, bb, tail, reg);
418 /* Compute loop nestings. Given two loops A and B, either the sets
419 of their blocks don't intersect at all, or one is the subset of
420 the other, or the blocks don't form a good nesting structure. */
421 for (loop = loops; loop; loop = loop->next)
423 hwloop_info other;
425 if (loop->bad)
426 continue;
428 for (other = loops; other; other = other->next)
430 if (other->bad)
431 continue;
433 if (!bitmap_intersect_p (other->block_bitmap, loop->block_bitmap))
434 continue;
435 if (!bitmap_intersect_compl_p (other->block_bitmap,
436 loop->block_bitmap))
437 loop->loops.safe_push (other);
438 else if (!bitmap_intersect_compl_p (loop->block_bitmap,
439 other->block_bitmap))
440 other->loops.safe_push (loop);
441 else
443 if (dump_file)
444 fprintf (dump_file,
445 ";; can't find suitable nesting for loops %d and %d\n",
446 loop->loop_no, other->loop_no);
447 loop->bad = other->bad = true;
452 if (dump_file)
453 dump_hwloops (loops);
455 return loops;
458 /* Free up the loop structures in LOOPS. */
459 static void
460 free_loops (hwloop_info loops)
462 while (loops)
464 hwloop_info loop = loops;
465 loops = loop->next;
466 loop->loops.release ();
467 loop->blocks.release ();
468 BITMAP_FREE (loop->block_bitmap);
469 XDELETE (loop);
473 #define BB_AUX_INDEX(BB) ((intptr_t) (BB)->aux)
475 /* Initialize the aux fields to give ascending indices to basic blocks. */
476 static void
477 set_bb_indices (void)
479 basic_block bb;
480 intptr_t index;
482 index = 0;
483 FOR_EACH_BB_FN (bb, cfun)
484 bb->aux = (void *) index++;
487 /* The taken-branch edge from the loop end can actually go forward.
488 If the target's hardware loop support requires that the loop end be
489 after the loop start, try to reorder a loop's basic blocks when we
490 find such a case.
491 This is not very aggressive; it only moves at most one block. It
492 does not introduce new branches into loops; it may remove them, or
493 it may switch fallthru/jump edges. */
494 static void
495 reorder_loops (hwloop_info loops)
497 basic_block bb;
498 hwloop_info loop;
500 cfg_layout_initialize (0);
502 set_bb_indices ();
504 for (loop = loops; loop; loop = loop->next)
506 edge e;
507 edge_iterator ei;
509 if (loop->bad)
510 continue;
512 if (BB_AUX_INDEX (loop->head) <= BB_AUX_INDEX (loop->tail))
513 continue;
515 FOR_EACH_EDGE (e, ei, loop->head->succs)
517 if (bitmap_bit_p (loop->block_bitmap, e->dest->index)
518 && BB_AUX_INDEX (e->dest) < BB_AUX_INDEX (loop->tail))
520 basic_block start_bb = e->dest;
521 basic_block start_prev_bb = start_bb->prev_bb;
523 if (dump_file)
524 fprintf (dump_file, ";; Moving block %d before block %d\n",
525 loop->head->index, start_bb->index);
526 loop->head->prev_bb->next_bb = loop->head->next_bb;
527 loop->head->next_bb->prev_bb = loop->head->prev_bb;
529 loop->head->prev_bb = start_prev_bb;
530 loop->head->next_bb = start_bb;
531 start_prev_bb->next_bb = start_bb->prev_bb = loop->head;
533 set_bb_indices ();
534 break;
537 loops = loops->next;
540 FOR_EACH_BB_FN (bb, cfun)
542 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
543 bb->aux = bb->next_bb;
544 else
545 bb->aux = NULL;
547 cfg_layout_finalize ();
548 clear_aux_for_blocks ();
549 df_analyze ();
552 /* Call the OPT function for LOOP and all of its sub-loops. This is
553 done in a depth-first search; innermost loops are visited first.
554 OPTIMIZE and FAIL are the functions passed to reorg_loops by the
555 target's reorg pass. */
556 static void
557 optimize_loop (hwloop_info loop, struct hw_doloop_hooks *hooks)
559 int ix;
560 hwloop_info inner;
561 int inner_depth = 0;
563 if (loop->visited)
564 return;
566 loop->visited = 1;
568 if (loop->bad)
570 if (dump_file)
571 fprintf (dump_file, ";; loop %d bad when found\n", loop->loop_no);
572 goto bad_loop;
575 /* Every loop contains in its list of inner loops every loop nested inside
576 it, even if there are intermediate loops. This works because we're doing
577 a depth-first search here and never visit a loop more than once.
578 Recursion depth is effectively limited by the number of available
579 hardware registers. */
580 for (ix = 0; loop->loops.iterate (ix, &inner); ix++)
582 optimize_loop (inner, hooks);
584 if (!inner->bad && inner_depth < inner->depth)
585 inner_depth = inner->depth;
586 /* The set of registers may be changed while optimizing the inner
587 loop. */
588 IOR_HARD_REG_SET (loop->regs_set_in_loop, inner->regs_set_in_loop);
591 loop->depth = inner_depth + 1;
593 if (hooks->opt (loop))
594 return;
596 bad_loop:
597 if (dump_file)
598 fprintf (dump_file, ";; loop %d is bad\n", loop->loop_no);
600 loop->bad = true;
601 hooks->fail (loop);
604 /* This function can be used from a port's machine_dependent_reorg to
605 find and analyze loops that end in loop_end instructions. It uses
606 a set of function pointers in HOOKS to call back into the
607 target-specific functions to perform the actual machine-specific
608 transformations.
610 Such transformations typically involve additional set-up
611 instructions before the loop, to define loop bounds or set up a
612 special loop counter register.
614 DO_REORDER should be set to true if we should try to use the
615 reorder_loops function to ensure the loop end occurs after the loop
616 start. This is for use by targets where the loop hardware requires
617 this condition.
619 HOOKS is used to pass in target specific hooks; see
620 hw-doloop.h. */
621 void
622 reorg_loops (bool do_reorder, struct hw_doloop_hooks *hooks)
624 hwloop_info loops = NULL;
625 hwloop_info loop;
626 bitmap_obstack loop_stack;
628 df_live_add_problem ();
629 df_live_set_all_dirty ();
630 df_analyze ();
632 bitmap_obstack_initialize (&loop_stack);
634 if (dump_file)
635 fprintf (dump_file, ";; Find loops, first pass\n\n");
637 loops = discover_loops (&loop_stack, hooks);
639 /* We can't enter cfglayout mode anymore if basic block partitioning
640 already happened. */
641 if (do_reorder && !flag_reorder_blocks_and_partition)
643 reorder_loops (loops);
644 free_loops (loops);
646 if (dump_file)
647 fprintf (dump_file, ";; Find loops, second pass\n\n");
649 loops = discover_loops (&loop_stack, hooks);
652 for (loop = loops; loop; loop = loop->next)
653 scan_loop (loop);
655 /* Now apply the optimizations. */
656 for (loop = loops; loop; loop = loop->next)
657 optimize_loop (loop, hooks);
659 if (dump_file)
661 fprintf (dump_file, ";; After hardware loops optimization:\n\n");
662 dump_hwloops (loops);
665 free_loops (loops);
666 bitmap_obstack_release (&loop_stack);
668 if (dump_file)
669 print_rtl (dump_file, get_insns ());
671 #endif