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-2015 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
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
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/>. */
23 #include "coretypes.h"
29 #include "hard-reg-set.h"
38 #include "dominance.h"
41 #include "basic-block.h"
47 #include "hw-doloop.h"
50 #ifdef HAVE_doloop_end
52 /* Dump information collected in LOOPS. */
54 dump_hwloops (hwloop_info loops
)
58 for (loop
= loops
; loop
; loop
= loop
->next
)
64 fprintf (dump_file
, ";; loop %d: ", loop
->loop_no
);
66 fprintf (dump_file
, "(bad) ");
67 fprintf (dump_file
, "{head:%d, depth:%d, reg:%u}",
68 loop
->head
== NULL
? -1 : loop
->head
->index
,
69 loop
->depth
, REGNO (loop
->iter_reg
));
71 fprintf (dump_file
, " blocks: [ ");
72 for (ix
= 0; loop
->blocks
.iterate (ix
, &b
); ix
++)
73 fprintf (dump_file
, "%d ", b
->index
);
74 fprintf (dump_file
, "] ");
76 fprintf (dump_file
, " inner loops: [ ");
77 for (ix
= 0; loop
->loops
.iterate (ix
, &i
); ix
++)
78 fprintf (dump_file
, "%d ", i
->loop_no
);
79 fprintf (dump_file
, "]\n");
81 fprintf (dump_file
, "\n");
84 /* Return true if BB is part of LOOP. */
86 bb_in_loop_p (hwloop_info loop
, basic_block bb
)
88 return bitmap_bit_p (loop
->block_bitmap
, bb
->index
);
91 /* Scan the blocks of LOOP (and its inferiors), and record things such as
92 hard registers set, jumps out of and within the loop. */
94 scan_loop (hwloop_info loop
)
102 if (REGNO_REG_SET_P (df_get_live_in (loop
->successor
),
103 REGNO (loop
->iter_reg
)))
104 loop
->iter_reg_used_outside
= true;
106 for (ix
= 0; loop
->blocks
.iterate (ix
, &bb
); ix
++)
112 if (bb
!= loop
->tail
)
113 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
115 if (bb_in_loop_p (loop
, e
->dest
))
117 if (!(e
->flags
& EDGE_FALLTHRU
))
118 loop
->jumps_within
= true;
122 loop
->jumps_outof
= true;
124 gcc_assert (!REGNO_REG_SET_P (df_get_live_in (e
->dest
),
125 REGNO (loop
->iter_reg
)));
129 for (insn
= BB_HEAD (bb
);
130 insn
!= NEXT_INSN (BB_END (bb
));
131 insn
= NEXT_INSN (insn
))
134 HARD_REG_SET set_this_insn
;
136 if (!NONDEBUG_INSN_P (insn
))
139 if (recog_memoized (insn
) < 0
140 && (GET_CODE (PATTERN (insn
)) == ASM_INPUT
141 || asm_noperands (PATTERN (insn
)) >= 0))
142 loop
->has_asm
= true;
144 CLEAR_HARD_REG_SET (set_this_insn
);
145 FOR_EACH_INSN_DEF (def
, insn
)
147 rtx dreg
= DF_REF_REG (def
);
152 add_to_hard_reg_set (&set_this_insn
, GET_MODE (dreg
),
156 if (insn
== loop
->loop_end
)
157 CLEAR_HARD_REG_BIT (set_this_insn
, REGNO (loop
->iter_reg
));
158 else if (reg_mentioned_p (loop
->iter_reg
, PATTERN (insn
)))
159 loop
->iter_reg_used
= true;
160 IOR_HARD_REG_SET (loop
->regs_set_in_loop
, set_this_insn
);
165 /* Compute the incoming_dest and incoming_src members of LOOP by
166 identifying the edges that jump into the loop. If there is more
167 than one block that jumps into the loop, incoming_src will be set
168 to NULL; likewise, if there is more than one block in the loop that
169 is the destination of an incoming edge, incoming_dest will be NULL.
171 Return true if either of these two fields is nonnull, false
174 process_incoming_edges (hwloop_info loop
)
180 FOR_EACH_EDGE (e
, ei
, loop
->incoming
)
184 loop
->incoming_src
= e
->src
;
185 loop
->incoming_dest
= e
->dest
;
190 if (e
->dest
!= loop
->incoming_dest
)
191 loop
->incoming_dest
= NULL
;
192 if (e
->src
!= loop
->incoming_src
)
193 loop
->incoming_src
= NULL
;
196 if (loop
->incoming_src
== NULL
&& loop
->incoming_dest
== NULL
)
202 /* Try to identify a forwarder block that jump into LOOP, and add it to
203 the set of blocks in the loop, updating the vector of incoming blocks as
204 well. This transformation gives a second chance to loops we couldn't
205 otherwise handle by increasing the chance that we'll end up with one
207 Return true if we made a change, false otherwise. */
209 add_forwarder_blocks (hwloop_info loop
)
214 FOR_EACH_EDGE (e
, ei
, loop
->incoming
)
216 if (forwarder_block_p (e
->src
))
223 ";; Adding forwarder block %d to loop %d and retrying\n",
224 e
->src
->index
, loop
->loop_no
);
225 loop
->blocks
.safe_push (e
->src
);
226 bitmap_set_bit (loop
->block_bitmap
, e
->src
->index
);
227 FOR_EACH_EDGE (e2
, ei2
, e
->src
->preds
)
228 vec_safe_push (loop
->incoming
, e2
);
229 loop
->incoming
->unordered_remove (ei
.index
);
236 /* Called from reorg_loops when a potential loop end is found. LOOP is
237 a newly set up structure describing the loop, it is this function's
238 responsibility to fill most of it. TAIL_BB and TAIL_INSN point to the
239 loop_end insn and its enclosing basic block. REG is the loop counter
241 For our purposes, a loop is defined by the set of blocks reachable from
242 the loop head in which the loop counter register is live. This matches
243 the expected use; targets that call into this code usually replace the
244 loop counter with a different special register. */
246 discover_loop (hwloop_info loop
, basic_block tail_bb
, rtx_insn
*tail_insn
, rtx reg
)
252 loop
->tail
= tail_bb
;
253 loop
->loop_end
= tail_insn
;
254 loop
->iter_reg
= reg
;
255 vec_alloc (loop
->incoming
, 2);
256 loop
->start_label
= as_a
<rtx_insn
*> (JUMP_LABEL (tail_insn
));
258 if (EDGE_COUNT (tail_bb
->succs
) != 2)
263 loop
->head
= BRANCH_EDGE (tail_bb
)->dest
;
264 loop
->successor
= FALLTHRU_EDGE (tail_bb
)->dest
;
266 auto_vec
<basic_block
, 20> works
;
267 works
.safe_push (loop
->head
);
270 for (dwork
= 0; works
.iterate (dwork
, &bb
); dwork
++)
274 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
276 /* We've reached the exit block. The loop must be bad. */
279 ";; Loop is bad - reached exit block while scanning\n");
284 if (bitmap_bit_p (loop
->block_bitmap
, bb
->index
))
287 /* We've not seen this block before. Add it to the loop's
288 list and then add each successor to the work list. */
290 loop
->blocks
.safe_push (bb
);
291 bitmap_set_bit (loop
->block_bitmap
, bb
->index
);
297 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
299 basic_block succ
= EDGE_SUCC (bb
, ei
.index
)->dest
;
300 if (REGNO_REG_SET_P (df_get_live_in (succ
),
301 REGNO (loop
->iter_reg
)))
302 works
.safe_push (succ
);
310 /* Find the predecessor, and make sure nothing else jumps into this loop. */
313 FOR_EACH_VEC_ELT (loop
->blocks
, dwork
, bb
)
317 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
319 basic_block pred
= e
->src
;
321 if (!bb_in_loop_p (loop
, pred
))
324 fprintf (dump_file
, ";; Loop %d: incoming edge %d -> %d\n",
325 loop
->loop_no
, pred
->index
,
327 vec_safe_push (loop
->incoming
, e
);
332 if (!process_incoming_edges (loop
))
336 ";; retrying loop %d with forwarder blocks\n",
338 if (!add_forwarder_blocks (loop
))
341 fprintf (dump_file
, ";; No forwarder blocks found\n");
344 else if (!process_incoming_edges (loop
))
348 ";; can't find suitable entry for loop %d\n",
355 /* Analyze the structure of the loops in the current function. Use
356 LOOP_STACK for bitmap allocations. Returns all the valid candidates for
357 hardware loops found in this function. HOOKS is the argument
358 passed to reorg_loops, used here to find the iteration registers
359 from a loop_end pattern. */
361 discover_loops (bitmap_obstack
*loop_stack
, struct hw_doloop_hooks
*hooks
)
363 hwloop_info loops
= NULL
;
368 /* Find all the possible loop tails. This means searching for every
369 loop_end instruction. For each one found, create a hwloop_info
370 structure and add the head block to the work list. */
371 FOR_EACH_BB_FN (bb
, cfun
)
373 rtx_insn
*tail
= BB_END (bb
);
377 while (tail
&& NOTE_P (tail
) && tail
!= BB_HEAD (bb
))
378 tail
= PREV_INSN (tail
);
380 if (tail
== NULL_RTX
)
385 reg
= hooks
->end_pattern_reg (tail
);
389 /* A possible loop end */
391 /* There's a degenerate case we can handle - an empty loop consisting
392 of only a back branch. Handle that by deleting the branch. */
393 insn
= JUMP_LABEL_AS_INSN (tail
);
394 while (insn
&& !NONDEBUG_INSN_P (insn
))
395 insn
= NEXT_INSN (insn
);
398 basic_block succ
= FALLTHRU_EDGE (bb
)->dest
;
401 fprintf (dump_file
, ";; degenerate loop ending at\n");
402 print_rtl_single (dump_file
, tail
);
404 if (!REGNO_REG_SET_P (df_get_live_in (succ
), REGNO (reg
)))
407 fprintf (dump_file
, ";; deleting it\n");
408 delete_insn_and_edges (tail
);
413 loop
= XCNEW (struct hwloop_info_d
);
416 loop
->loop_no
= nloops
++;
417 loop
->blocks
.create (20);
418 loop
->block_bitmap
= BITMAP_ALLOC (loop_stack
);
422 fprintf (dump_file
, ";; potential loop %d ending at\n",
424 print_rtl_single (dump_file
, tail
);
427 discover_loop (loop
, bb
, tail
, reg
);
430 /* Compute loop nestings. Given two loops A and B, either the sets
431 of their blocks don't intersect at all, or one is the subset of
432 the other, or the blocks don't form a good nesting structure. */
433 for (loop
= loops
; loop
; loop
= loop
->next
)
440 for (other
= loops
; other
; other
= other
->next
)
445 if (!bitmap_intersect_p (other
->block_bitmap
, loop
->block_bitmap
))
447 if (!bitmap_intersect_compl_p (other
->block_bitmap
,
449 loop
->loops
.safe_push (other
);
450 else if (!bitmap_intersect_compl_p (loop
->block_bitmap
,
451 other
->block_bitmap
))
452 other
->loops
.safe_push (loop
);
457 ";; can't find suitable nesting for loops %d and %d\n",
458 loop
->loop_no
, other
->loop_no
);
459 loop
->bad
= other
->bad
= true;
465 dump_hwloops (loops
);
470 /* Free up the loop structures in LOOPS. */
472 free_loops (hwloop_info loops
)
476 hwloop_info loop
= loops
;
478 loop
->loops
.release ();
479 loop
->blocks
.release ();
480 BITMAP_FREE (loop
->block_bitmap
);
485 #define BB_AUX_INDEX(BB) ((intptr_t) (BB)->aux)
487 /* Initialize the aux fields to give ascending indices to basic blocks. */
489 set_bb_indices (void)
495 FOR_EACH_BB_FN (bb
, cfun
)
496 bb
->aux
= (void *) index
++;
499 /* The taken-branch edge from the loop end can actually go forward.
500 If the target's hardware loop support requires that the loop end be
501 after the loop start, try to reorder a loop's basic blocks when we
503 This is not very aggressive; it only moves at most one block. It
504 does not introduce new branches into loops; it may remove them, or
505 it may switch fallthru/jump edges. */
507 reorder_loops (hwloop_info loops
)
512 cfg_layout_initialize (0);
516 for (loop
= loops
; loop
; loop
= loop
->next
)
524 if (BB_AUX_INDEX (loop
->head
) <= BB_AUX_INDEX (loop
->tail
))
527 FOR_EACH_EDGE (e
, ei
, loop
->head
->succs
)
529 if (bitmap_bit_p (loop
->block_bitmap
, e
->dest
->index
)
530 && BB_AUX_INDEX (e
->dest
) < BB_AUX_INDEX (loop
->tail
))
532 basic_block start_bb
= e
->dest
;
533 basic_block start_prev_bb
= start_bb
->prev_bb
;
536 fprintf (dump_file
, ";; Moving block %d before block %d\n",
537 loop
->head
->index
, start_bb
->index
);
538 loop
->head
->prev_bb
->next_bb
= loop
->head
->next_bb
;
539 loop
->head
->next_bb
->prev_bb
= loop
->head
->prev_bb
;
541 loop
->head
->prev_bb
= start_prev_bb
;
542 loop
->head
->next_bb
= start_bb
;
543 start_prev_bb
->next_bb
= start_bb
->prev_bb
= loop
->head
;
552 FOR_EACH_BB_FN (bb
, cfun
)
554 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
555 bb
->aux
= bb
->next_bb
;
559 cfg_layout_finalize ();
560 clear_aux_for_blocks ();
564 /* Call the OPT function for LOOP and all of its sub-loops. This is
565 done in a depth-first search; innermost loops are visited first.
566 OPTIMIZE and FAIL are the functions passed to reorg_loops by the
567 target's reorg pass. */
569 optimize_loop (hwloop_info loop
, struct hw_doloop_hooks
*hooks
)
583 fprintf (dump_file
, ";; loop %d bad when found\n", loop
->loop_no
);
587 /* Every loop contains in its list of inner loops every loop nested inside
588 it, even if there are intermediate loops. This works because we're doing
589 a depth-first search here and never visit a loop more than once.
590 Recursion depth is effectively limited by the number of available
591 hardware registers. */
592 for (ix
= 0; loop
->loops
.iterate (ix
, &inner
); ix
++)
594 optimize_loop (inner
, hooks
);
596 if (!inner
->bad
&& inner_depth
< inner
->depth
)
597 inner_depth
= inner
->depth
;
598 /* The set of registers may be changed while optimizing the inner
600 IOR_HARD_REG_SET (loop
->regs_set_in_loop
, inner
->regs_set_in_loop
);
603 loop
->depth
= inner_depth
+ 1;
605 if (hooks
->opt (loop
))
610 fprintf (dump_file
, ";; loop %d is bad\n", loop
->loop_no
);
616 /* This function can be used from a port's machine_dependent_reorg to
617 find and analyze loops that end in loop_end instructions. It uses
618 a set of function pointers in HOOKS to call back into the
619 target-specific functions to perform the actual machine-specific
622 Such transformations typically involve additional set-up
623 instructions before the loop, to define loop bounds or set up a
624 special loop counter register.
626 DO_REORDER should be set to true if we should try to use the
627 reorder_loops function to ensure the loop end occurs after the loop
628 start. This is for use by targets where the loop hardware requires
631 HOOKS is used to pass in target specific hooks; see
634 reorg_loops (bool do_reorder
, struct hw_doloop_hooks
*hooks
)
636 hwloop_info loops
= NULL
;
638 bitmap_obstack loop_stack
;
640 df_live_add_problem ();
641 df_live_set_all_dirty ();
644 bitmap_obstack_initialize (&loop_stack
);
647 fprintf (dump_file
, ";; Find loops, first pass\n\n");
649 loops
= discover_loops (&loop_stack
, hooks
);
651 /* We can't enter cfglayout mode anymore if basic block partitioning
653 if (do_reorder
&& !flag_reorder_blocks_and_partition
)
655 reorder_loops (loops
);
659 fprintf (dump_file
, ";; Find loops, second pass\n\n");
661 loops
= discover_loops (&loop_stack
, hooks
);
664 for (loop
= loops
; loop
; loop
= loop
->next
)
667 /* Now apply the optimizations. */
668 for (loop
= loops
; loop
; loop
= loop
->next
)
669 optimize_loop (loop
, hooks
);
673 fprintf (dump_file
, ";; After hardware loops optimization:\n\n");
674 dump_hwloops (loops
);
678 bitmap_obstack_release (&loop_stack
);
681 print_rtl (dump_file
, get_insns ());