1*e4b17023SJohn Marino /* Code to analyze doloop loops in order for targets to perform late
2*e4b17023SJohn Marino optimizations converting doloops to other forms of hardware loops.
3*e4b17023SJohn Marino Copyright (C) 2011 Free Software Foundation, Inc.
4*e4b17023SJohn Marino
5*e4b17023SJohn Marino This file is part of GCC.
6*e4b17023SJohn Marino
7*e4b17023SJohn Marino GCC is free software; you can redistribute it and/or modify it under
8*e4b17023SJohn Marino the terms of the GNU General Public License as published by the Free
9*e4b17023SJohn Marino Software Foundation; either version 3, or (at your option) any later
10*e4b17023SJohn Marino version.
11*e4b17023SJohn Marino
12*e4b17023SJohn Marino GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13*e4b17023SJohn Marino WARRANTY; without even the implied warranty of MERCHANTABILITY or
14*e4b17023SJohn Marino FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15*e4b17023SJohn Marino for more details.
16*e4b17023SJohn Marino
17*e4b17023SJohn Marino You should have received a copy of the GNU General Public License
18*e4b17023SJohn Marino along with GCC; see the file COPYING3. If not see
19*e4b17023SJohn Marino <http://www.gnu.org/licenses/>. */
20*e4b17023SJohn Marino
21*e4b17023SJohn Marino #include "config.h"
22*e4b17023SJohn Marino #include "system.h"
23*e4b17023SJohn Marino #include "coretypes.h"
24*e4b17023SJohn Marino #include "tm.h"
25*e4b17023SJohn Marino #include "rtl.h"
26*e4b17023SJohn Marino #include "flags.h"
27*e4b17023SJohn Marino #include "expr.h"
28*e4b17023SJohn Marino #include "hard-reg-set.h"
29*e4b17023SJohn Marino #include "regs.h"
30*e4b17023SJohn Marino #include "basic-block.h"
31*e4b17023SJohn Marino #include "tm_p.h"
32*e4b17023SJohn Marino #include "df.h"
33*e4b17023SJohn Marino #include "cfglayout.h"
34*e4b17023SJohn Marino #include "cfgloop.h"
35*e4b17023SJohn Marino #include "output.h"
36*e4b17023SJohn Marino #include "recog.h"
37*e4b17023SJohn Marino #include "target.h"
38*e4b17023SJohn Marino #include "hw-doloop.h"
39*e4b17023SJohn Marino
40*e4b17023SJohn Marino #ifdef HAVE_doloop_end
41*e4b17023SJohn Marino
42*e4b17023SJohn Marino /* Dump information collected in LOOPS. */
43*e4b17023SJohn Marino static void
dump_hwloops(hwloop_info loops)44*e4b17023SJohn Marino dump_hwloops (hwloop_info loops)
45*e4b17023SJohn Marino {
46*e4b17023SJohn Marino hwloop_info loop;
47*e4b17023SJohn Marino
48*e4b17023SJohn Marino for (loop = loops; loop; loop = loop->next)
49*e4b17023SJohn Marino {
50*e4b17023SJohn Marino hwloop_info i;
51*e4b17023SJohn Marino basic_block b;
52*e4b17023SJohn Marino unsigned ix;
53*e4b17023SJohn Marino
54*e4b17023SJohn Marino fprintf (dump_file, ";; loop %d: ", loop->loop_no);
55*e4b17023SJohn Marino if (loop->bad)
56*e4b17023SJohn Marino fprintf (dump_file, "(bad) ");
57*e4b17023SJohn Marino fprintf (dump_file, "{head:%d, depth:%d, reg:%u}",
58*e4b17023SJohn Marino loop->head == NULL ? -1 : loop->head->index,
59*e4b17023SJohn Marino loop->depth, REGNO (loop->iter_reg));
60*e4b17023SJohn Marino
61*e4b17023SJohn Marino fprintf (dump_file, " blocks: [ ");
62*e4b17023SJohn Marino for (ix = 0; VEC_iterate (basic_block, loop->blocks, ix, b); ix++)
63*e4b17023SJohn Marino fprintf (dump_file, "%d ", b->index);
64*e4b17023SJohn Marino fprintf (dump_file, "] ");
65*e4b17023SJohn Marino
66*e4b17023SJohn Marino fprintf (dump_file, " inner loops: [ ");
67*e4b17023SJohn Marino for (ix = 0; VEC_iterate (hwloop_info, loop->loops, ix, i); ix++)
68*e4b17023SJohn Marino fprintf (dump_file, "%d ", i->loop_no);
69*e4b17023SJohn Marino fprintf (dump_file, "]\n");
70*e4b17023SJohn Marino }
71*e4b17023SJohn Marino fprintf (dump_file, "\n");
72*e4b17023SJohn Marino }
73*e4b17023SJohn Marino
74*e4b17023SJohn Marino /* Return true if BB is part of LOOP. */
75*e4b17023SJohn Marino static bool
bb_in_loop_p(hwloop_info loop,basic_block bb)76*e4b17023SJohn Marino bb_in_loop_p (hwloop_info loop, basic_block bb)
77*e4b17023SJohn Marino {
78*e4b17023SJohn Marino return bitmap_bit_p (loop->block_bitmap, bb->index);
79*e4b17023SJohn Marino }
80*e4b17023SJohn Marino
81*e4b17023SJohn Marino /* Scan the blocks of LOOP (and its inferiors), and record things such as
82*e4b17023SJohn Marino hard registers set, jumps out of and within the loop. */
83*e4b17023SJohn Marino static void
scan_loop(hwloop_info loop)84*e4b17023SJohn Marino scan_loop (hwloop_info loop)
85*e4b17023SJohn Marino {
86*e4b17023SJohn Marino unsigned ix;
87*e4b17023SJohn Marino basic_block bb;
88*e4b17023SJohn Marino
89*e4b17023SJohn Marino if (loop->bad)
90*e4b17023SJohn Marino return;
91*e4b17023SJohn Marino
92*e4b17023SJohn Marino if (REGNO_REG_SET_P (df_get_live_in (loop->successor),
93*e4b17023SJohn Marino REGNO (loop->iter_reg)))
94*e4b17023SJohn Marino loop->iter_reg_used_outside = true;
95*e4b17023SJohn Marino
96*e4b17023SJohn Marino for (ix = 0; VEC_iterate (basic_block, loop->blocks, ix, bb); ix++)
97*e4b17023SJohn Marino {
98*e4b17023SJohn Marino rtx insn;
99*e4b17023SJohn Marino edge e;
100*e4b17023SJohn Marino edge_iterator ei;
101*e4b17023SJohn Marino
102*e4b17023SJohn Marino if (bb != loop->tail)
103*e4b17023SJohn Marino FOR_EACH_EDGE (e, ei, bb->succs)
104*e4b17023SJohn Marino {
105*e4b17023SJohn Marino if (bb_in_loop_p (loop, e->dest))
106*e4b17023SJohn Marino {
107*e4b17023SJohn Marino if (!(e->flags & EDGE_FALLTHRU))
108*e4b17023SJohn Marino loop->jumps_within = true;
109*e4b17023SJohn Marino }
110*e4b17023SJohn Marino else
111*e4b17023SJohn Marino {
112*e4b17023SJohn Marino loop->jumps_outof = true;
113*e4b17023SJohn Marino if (!loop->bad)
114*e4b17023SJohn Marino gcc_assert (!REGNO_REG_SET_P (df_get_live_in (e->dest),
115*e4b17023SJohn Marino REGNO (loop->iter_reg)));
116*e4b17023SJohn Marino }
117*e4b17023SJohn Marino }
118*e4b17023SJohn Marino
119*e4b17023SJohn Marino for (insn = BB_HEAD (bb);
120*e4b17023SJohn Marino insn != NEXT_INSN (BB_END (bb));
121*e4b17023SJohn Marino insn = NEXT_INSN (insn))
122*e4b17023SJohn Marino {
123*e4b17023SJohn Marino df_ref *def_rec;
124*e4b17023SJohn Marino HARD_REG_SET set_this_insn;
125*e4b17023SJohn Marino
126*e4b17023SJohn Marino if (!NONDEBUG_INSN_P (insn))
127*e4b17023SJohn Marino continue;
128*e4b17023SJohn Marino
129*e4b17023SJohn Marino if (recog_memoized (insn) < 0
130*e4b17023SJohn Marino && (GET_CODE (PATTERN (insn)) == ASM_INPUT
131*e4b17023SJohn Marino || asm_noperands (PATTERN (insn)) >= 0))
132*e4b17023SJohn Marino loop->has_asm = true;
133*e4b17023SJohn Marino
134*e4b17023SJohn Marino CLEAR_HARD_REG_SET (set_this_insn);
135*e4b17023SJohn Marino for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
136*e4b17023SJohn Marino {
137*e4b17023SJohn Marino rtx dreg = DF_REF_REG (*def_rec);
138*e4b17023SJohn Marino
139*e4b17023SJohn Marino if (!REG_P (dreg))
140*e4b17023SJohn Marino continue;
141*e4b17023SJohn Marino
142*e4b17023SJohn Marino add_to_hard_reg_set (&set_this_insn, GET_MODE (dreg),
143*e4b17023SJohn Marino REGNO (dreg));
144*e4b17023SJohn Marino }
145*e4b17023SJohn Marino
146*e4b17023SJohn Marino if (insn == loop->loop_end)
147*e4b17023SJohn Marino CLEAR_HARD_REG_BIT (set_this_insn, REGNO (loop->iter_reg));
148*e4b17023SJohn Marino else if (reg_mentioned_p (loop->iter_reg, PATTERN (insn)))
149*e4b17023SJohn Marino loop->iter_reg_used = true;
150*e4b17023SJohn Marino IOR_HARD_REG_SET (loop->regs_set_in_loop, set_this_insn);
151*e4b17023SJohn Marino }
152*e4b17023SJohn Marino }
153*e4b17023SJohn Marino }
154*e4b17023SJohn Marino
155*e4b17023SJohn Marino /* Compute the incoming_dest and incoming_src members of LOOP by
156*e4b17023SJohn Marino identifying the edges that jump into the loop. If there is more
157*e4b17023SJohn Marino than one block that jumps into the loop, incoming_src will be set
158*e4b17023SJohn Marino to NULL; likewise, if there is more than one block in the loop that
159*e4b17023SJohn Marino is the destination of an incoming edge, incoming_dest will be NULL.
160*e4b17023SJohn Marino
161*e4b17023SJohn Marino Return true if either of these two fields is nonnull, false
162*e4b17023SJohn Marino otherwise. */
163*e4b17023SJohn Marino static bool
process_incoming_edges(hwloop_info loop)164*e4b17023SJohn Marino process_incoming_edges (hwloop_info loop)
165*e4b17023SJohn Marino {
166*e4b17023SJohn Marino edge e;
167*e4b17023SJohn Marino edge_iterator ei;
168*e4b17023SJohn Marino bool first = true;
169*e4b17023SJohn Marino
170*e4b17023SJohn Marino FOR_EACH_EDGE (e, ei, loop->incoming)
171*e4b17023SJohn Marino {
172*e4b17023SJohn Marino if (first)
173*e4b17023SJohn Marino {
174*e4b17023SJohn Marino loop->incoming_src = e->src;
175*e4b17023SJohn Marino loop->incoming_dest = e->dest;
176*e4b17023SJohn Marino first = false;
177*e4b17023SJohn Marino }
178*e4b17023SJohn Marino else
179*e4b17023SJohn Marino {
180*e4b17023SJohn Marino if (e->dest != loop->incoming_dest)
181*e4b17023SJohn Marino loop->incoming_dest = NULL;
182*e4b17023SJohn Marino if (e->src != loop->incoming_src)
183*e4b17023SJohn Marino loop->incoming_src = NULL;
184*e4b17023SJohn Marino }
185*e4b17023SJohn Marino }
186*e4b17023SJohn Marino if (loop->incoming_src == NULL && loop->incoming_dest == NULL)
187*e4b17023SJohn Marino return false;
188*e4b17023SJohn Marino
189*e4b17023SJohn Marino return true;
190*e4b17023SJohn Marino }
191*e4b17023SJohn Marino
192*e4b17023SJohn Marino /* Try to identify a forwarder block that jump into LOOP, and add it to
193*e4b17023SJohn Marino the set of blocks in the loop, updating the vector of incoming blocks as
194*e4b17023SJohn Marino well. This transformation gives a second chance to loops we couldn't
195*e4b17023SJohn Marino otherwise handle by increasing the chance that we'll end up with one
196*e4b17023SJohn Marino incoming_src block.
197*e4b17023SJohn Marino Return true if we made a change, false otherwise. */
198*e4b17023SJohn Marino static bool
add_forwarder_blocks(hwloop_info loop)199*e4b17023SJohn Marino add_forwarder_blocks (hwloop_info loop)
200*e4b17023SJohn Marino {
201*e4b17023SJohn Marino edge e;
202*e4b17023SJohn Marino edge_iterator ei;
203*e4b17023SJohn Marino
204*e4b17023SJohn Marino FOR_EACH_EDGE (e, ei, loop->incoming)
205*e4b17023SJohn Marino {
206*e4b17023SJohn Marino if (forwarder_block_p (e->src))
207*e4b17023SJohn Marino {
208*e4b17023SJohn Marino edge e2;
209*e4b17023SJohn Marino edge_iterator ei2;
210*e4b17023SJohn Marino
211*e4b17023SJohn Marino if (dump_file)
212*e4b17023SJohn Marino fprintf (dump_file,
213*e4b17023SJohn Marino ";; Adding forwarder block %d to loop %d and retrying\n",
214*e4b17023SJohn Marino e->src->index, loop->loop_no);
215*e4b17023SJohn Marino VEC_safe_push (basic_block, heap, loop->blocks, e->src);
216*e4b17023SJohn Marino bitmap_set_bit (loop->block_bitmap, e->src->index);
217*e4b17023SJohn Marino FOR_EACH_EDGE (e2, ei2, e->src->preds)
218*e4b17023SJohn Marino VEC_safe_push (edge, gc, loop->incoming, e2);
219*e4b17023SJohn Marino VEC_unordered_remove (edge, loop->incoming, ei.index);
220*e4b17023SJohn Marino return true;
221*e4b17023SJohn Marino }
222*e4b17023SJohn Marino }
223*e4b17023SJohn Marino return false;
224*e4b17023SJohn Marino }
225*e4b17023SJohn Marino
226*e4b17023SJohn Marino /* Called from reorg_loops when a potential loop end is found. LOOP is
227*e4b17023SJohn Marino a newly set up structure describing the loop, it is this function's
228*e4b17023SJohn Marino responsibility to fill most of it. TAIL_BB and TAIL_INSN point to the
229*e4b17023SJohn Marino loop_end insn and its enclosing basic block. REG is the loop counter
230*e4b17023SJohn Marino register.
231*e4b17023SJohn Marino For our purposes, a loop is defined by the set of blocks reachable from
232*e4b17023SJohn Marino the loop head in which the loop counter register is live. This matches
233*e4b17023SJohn Marino the expected use; targets that call into this code usually replace the
234*e4b17023SJohn Marino loop counter with a different special register. */
235*e4b17023SJohn Marino static void
discover_loop(hwloop_info loop,basic_block tail_bb,rtx tail_insn,rtx reg)236*e4b17023SJohn Marino discover_loop (hwloop_info loop, basic_block tail_bb, rtx tail_insn, rtx reg)
237*e4b17023SJohn Marino {
238*e4b17023SJohn Marino bool found_tail;
239*e4b17023SJohn Marino unsigned dwork = 0;
240*e4b17023SJohn Marino basic_block bb;
241*e4b17023SJohn Marino VEC (basic_block,heap) *works;
242*e4b17023SJohn Marino
243*e4b17023SJohn Marino loop->tail = tail_bb;
244*e4b17023SJohn Marino loop->loop_end = tail_insn;
245*e4b17023SJohn Marino loop->iter_reg = reg;
246*e4b17023SJohn Marino loop->incoming = VEC_alloc (edge, gc, 2);
247*e4b17023SJohn Marino loop->start_label = JUMP_LABEL (tail_insn);
248*e4b17023SJohn Marino
249*e4b17023SJohn Marino if (EDGE_COUNT (tail_bb->succs) != 2)
250*e4b17023SJohn Marino {
251*e4b17023SJohn Marino loop->bad = true;
252*e4b17023SJohn Marino return;
253*e4b17023SJohn Marino }
254*e4b17023SJohn Marino loop->head = BRANCH_EDGE (tail_bb)->dest;
255*e4b17023SJohn Marino loop->successor = FALLTHRU_EDGE (tail_bb)->dest;
256*e4b17023SJohn Marino
257*e4b17023SJohn Marino works = VEC_alloc (basic_block, heap, 20);
258*e4b17023SJohn Marino VEC_safe_push (basic_block, heap, works, loop->head);
259*e4b17023SJohn Marino
260*e4b17023SJohn Marino found_tail = false;
261*e4b17023SJohn Marino for (dwork = 0; VEC_iterate (basic_block, works, dwork, bb); dwork++)
262*e4b17023SJohn Marino {
263*e4b17023SJohn Marino edge e;
264*e4b17023SJohn Marino edge_iterator ei;
265*e4b17023SJohn Marino if (bb == EXIT_BLOCK_PTR)
266*e4b17023SJohn Marino {
267*e4b17023SJohn Marino /* We've reached the exit block. The loop must be bad. */
268*e4b17023SJohn Marino if (dump_file)
269*e4b17023SJohn Marino fprintf (dump_file,
270*e4b17023SJohn Marino ";; Loop is bad - reached exit block while scanning\n");
271*e4b17023SJohn Marino loop->bad = true;
272*e4b17023SJohn Marino break;
273*e4b17023SJohn Marino }
274*e4b17023SJohn Marino
275*e4b17023SJohn Marino if (bitmap_bit_p (loop->block_bitmap, bb->index))
276*e4b17023SJohn Marino continue;
277*e4b17023SJohn Marino
278*e4b17023SJohn Marino /* We've not seen this block before. Add it to the loop's
279*e4b17023SJohn Marino list and then add each successor to the work list. */
280*e4b17023SJohn Marino
281*e4b17023SJohn Marino VEC_safe_push (basic_block, heap, loop->blocks, bb);
282*e4b17023SJohn Marino bitmap_set_bit (loop->block_bitmap, bb->index);
283*e4b17023SJohn Marino
284*e4b17023SJohn Marino if (bb == tail_bb)
285*e4b17023SJohn Marino found_tail = true;
286*e4b17023SJohn Marino else
287*e4b17023SJohn Marino {
288*e4b17023SJohn Marino FOR_EACH_EDGE (e, ei, bb->succs)
289*e4b17023SJohn Marino {
290*e4b17023SJohn Marino basic_block succ = EDGE_SUCC (bb, ei.index)->dest;
291*e4b17023SJohn Marino if (REGNO_REG_SET_P (df_get_live_in (succ),
292*e4b17023SJohn Marino REGNO (loop->iter_reg)))
293*e4b17023SJohn Marino VEC_safe_push (basic_block, heap, works, succ);
294*e4b17023SJohn Marino }
295*e4b17023SJohn Marino }
296*e4b17023SJohn Marino }
297*e4b17023SJohn Marino
298*e4b17023SJohn Marino if (!found_tail)
299*e4b17023SJohn Marino loop->bad = true;
300*e4b17023SJohn Marino
301*e4b17023SJohn Marino /* Find the predecessor, and make sure nothing else jumps into this loop. */
302*e4b17023SJohn Marino if (!loop->bad)
303*e4b17023SJohn Marino {
304*e4b17023SJohn Marino FOR_EACH_VEC_ELT (basic_block, loop->blocks, dwork, bb)
305*e4b17023SJohn Marino {
306*e4b17023SJohn Marino edge e;
307*e4b17023SJohn Marino edge_iterator ei;
308*e4b17023SJohn Marino FOR_EACH_EDGE (e, ei, bb->preds)
309*e4b17023SJohn Marino {
310*e4b17023SJohn Marino basic_block pred = e->src;
311*e4b17023SJohn Marino
312*e4b17023SJohn Marino if (!bb_in_loop_p (loop, pred))
313*e4b17023SJohn Marino {
314*e4b17023SJohn Marino if (dump_file)
315*e4b17023SJohn Marino fprintf (dump_file, ";; Loop %d: incoming edge %d -> %d\n",
316*e4b17023SJohn Marino loop->loop_no, pred->index,
317*e4b17023SJohn Marino e->dest->index);
318*e4b17023SJohn Marino VEC_safe_push (edge, gc, loop->incoming, e);
319*e4b17023SJohn Marino }
320*e4b17023SJohn Marino }
321*e4b17023SJohn Marino }
322*e4b17023SJohn Marino
323*e4b17023SJohn Marino if (!process_incoming_edges (loop))
324*e4b17023SJohn Marino {
325*e4b17023SJohn Marino if (dump_file)
326*e4b17023SJohn Marino fprintf (dump_file,
327*e4b17023SJohn Marino ";; retrying loop %d with forwarder blocks\n",
328*e4b17023SJohn Marino loop->loop_no);
329*e4b17023SJohn Marino if (!add_forwarder_blocks (loop))
330*e4b17023SJohn Marino {
331*e4b17023SJohn Marino if (dump_file)
332*e4b17023SJohn Marino fprintf (dump_file, ";; No forwarder blocks found\n");
333*e4b17023SJohn Marino loop->bad = true;
334*e4b17023SJohn Marino }
335*e4b17023SJohn Marino else if (!process_incoming_edges (loop))
336*e4b17023SJohn Marino {
337*e4b17023SJohn Marino if (dump_file)
338*e4b17023SJohn Marino fprintf (dump_file,
339*e4b17023SJohn Marino ";; can't find suitable entry for loop %d\n",
340*e4b17023SJohn Marino loop->loop_no);
341*e4b17023SJohn Marino }
342*e4b17023SJohn Marino }
343*e4b17023SJohn Marino }
344*e4b17023SJohn Marino
345*e4b17023SJohn Marino VEC_free (basic_block, heap, works);
346*e4b17023SJohn Marino }
347*e4b17023SJohn Marino
348*e4b17023SJohn Marino /* Analyze the structure of the loops in the current function. Use
349*e4b17023SJohn Marino STACK for bitmap allocations. Returns all the valid candidates for
350*e4b17023SJohn Marino hardware loops found in this function. HOOKS is the argument
351*e4b17023SJohn Marino passed to reorg_loops, used here to find the iteration registers
352*e4b17023SJohn Marino from a loop_end pattern. */
353*e4b17023SJohn Marino static hwloop_info
discover_loops(bitmap_obstack * stack,struct hw_doloop_hooks * hooks)354*e4b17023SJohn Marino discover_loops (bitmap_obstack *stack, struct hw_doloop_hooks *hooks)
355*e4b17023SJohn Marino {
356*e4b17023SJohn Marino hwloop_info loops = NULL;
357*e4b17023SJohn Marino hwloop_info loop;
358*e4b17023SJohn Marino basic_block bb;
359*e4b17023SJohn Marino int nloops = 0;
360*e4b17023SJohn Marino
361*e4b17023SJohn Marino /* Find all the possible loop tails. This means searching for every
362*e4b17023SJohn Marino loop_end instruction. For each one found, create a hwloop_info
363*e4b17023SJohn Marino structure and add the head block to the work list. */
364*e4b17023SJohn Marino FOR_EACH_BB (bb)
365*e4b17023SJohn Marino {
366*e4b17023SJohn Marino rtx tail = BB_END (bb);
367*e4b17023SJohn Marino rtx insn, reg;
368*e4b17023SJohn Marino
369*e4b17023SJohn Marino while (tail && GET_CODE (tail) == NOTE && tail != BB_HEAD (bb))
370*e4b17023SJohn Marino tail = PREV_INSN (tail);
371*e4b17023SJohn Marino
372*e4b17023SJohn Marino if (tail == NULL_RTX)
373*e4b17023SJohn Marino continue;
374*e4b17023SJohn Marino
375*e4b17023SJohn Marino if (!JUMP_P (tail))
376*e4b17023SJohn Marino continue;
377*e4b17023SJohn Marino reg = hooks->end_pattern_reg (tail);
378*e4b17023SJohn Marino if (reg == NULL_RTX)
379*e4b17023SJohn Marino continue;
380*e4b17023SJohn Marino
381*e4b17023SJohn Marino /* A possible loop end */
382*e4b17023SJohn Marino
383*e4b17023SJohn Marino /* There's a degenerate case we can handle - an empty loop consisting
384*e4b17023SJohn Marino of only a back branch. Handle that by deleting the branch. */
385*e4b17023SJohn Marino insn = JUMP_LABEL (tail);
386*e4b17023SJohn Marino while (insn && !NONDEBUG_INSN_P (insn))
387*e4b17023SJohn Marino insn = NEXT_INSN (insn);
388*e4b17023SJohn Marino if (insn == tail)
389*e4b17023SJohn Marino {
390*e4b17023SJohn Marino basic_block succ = FALLTHRU_EDGE (bb)->dest;
391*e4b17023SJohn Marino if (dump_file)
392*e4b17023SJohn Marino {
393*e4b17023SJohn Marino fprintf (dump_file, ";; degenerate loop ending at\n");
394*e4b17023SJohn Marino print_rtl_single (dump_file, tail);
395*e4b17023SJohn Marino }
396*e4b17023SJohn Marino if (!REGNO_REG_SET_P (df_get_live_in (succ), REGNO (reg)))
397*e4b17023SJohn Marino {
398*e4b17023SJohn Marino if (dump_file)
399*e4b17023SJohn Marino fprintf (dump_file, ";; deleting it\n");
400*e4b17023SJohn Marino delete_insn_and_edges (tail);
401*e4b17023SJohn Marino continue;
402*e4b17023SJohn Marino }
403*e4b17023SJohn Marino }
404*e4b17023SJohn Marino
405*e4b17023SJohn Marino loop = XCNEW (struct hwloop_info_d);
406*e4b17023SJohn Marino loop->next = loops;
407*e4b17023SJohn Marino loops = loop;
408*e4b17023SJohn Marino loop->loop_no = nloops++;
409*e4b17023SJohn Marino loop->blocks = VEC_alloc (basic_block, heap, 20);
410*e4b17023SJohn Marino loop->block_bitmap = BITMAP_ALLOC (stack);
411*e4b17023SJohn Marino
412*e4b17023SJohn Marino if (dump_file)
413*e4b17023SJohn Marino {
414*e4b17023SJohn Marino fprintf (dump_file, ";; potential loop %d ending at\n",
415*e4b17023SJohn Marino loop->loop_no);
416*e4b17023SJohn Marino print_rtl_single (dump_file, tail);
417*e4b17023SJohn Marino }
418*e4b17023SJohn Marino
419*e4b17023SJohn Marino discover_loop (loop, bb, tail, reg);
420*e4b17023SJohn Marino }
421*e4b17023SJohn Marino
422*e4b17023SJohn Marino /* Compute loop nestings. Given two loops A and B, either the sets
423*e4b17023SJohn Marino of their blocks don't intersect at all, or one is the subset of
424*e4b17023SJohn Marino the other, or the blocks don't form a good nesting structure. */
425*e4b17023SJohn Marino for (loop = loops; loop; loop = loop->next)
426*e4b17023SJohn Marino {
427*e4b17023SJohn Marino hwloop_info other;
428*e4b17023SJohn Marino
429*e4b17023SJohn Marino if (loop->bad)
430*e4b17023SJohn Marino continue;
431*e4b17023SJohn Marino
432*e4b17023SJohn Marino for (other = loops; other; other = other->next)
433*e4b17023SJohn Marino {
434*e4b17023SJohn Marino if (other->bad)
435*e4b17023SJohn Marino continue;
436*e4b17023SJohn Marino
437*e4b17023SJohn Marino if (!bitmap_intersect_p (other->block_bitmap, loop->block_bitmap))
438*e4b17023SJohn Marino continue;
439*e4b17023SJohn Marino if (!bitmap_intersect_compl_p (other->block_bitmap,
440*e4b17023SJohn Marino loop->block_bitmap))
441*e4b17023SJohn Marino VEC_safe_push (hwloop_info, heap, loop->loops, other);
442*e4b17023SJohn Marino else if (!bitmap_intersect_compl_p (loop->block_bitmap,
443*e4b17023SJohn Marino other->block_bitmap))
444*e4b17023SJohn Marino VEC_safe_push (hwloop_info, heap, other->loops, loop);
445*e4b17023SJohn Marino else
446*e4b17023SJohn Marino {
447*e4b17023SJohn Marino if (dump_file)
448*e4b17023SJohn Marino fprintf (dump_file,
449*e4b17023SJohn Marino ";; can't find suitable nesting for loops %d and %d\n",
450*e4b17023SJohn Marino loop->loop_no, other->loop_no);
451*e4b17023SJohn Marino loop->bad = other->bad = true;
452*e4b17023SJohn Marino }
453*e4b17023SJohn Marino }
454*e4b17023SJohn Marino }
455*e4b17023SJohn Marino
456*e4b17023SJohn Marino if (dump_file)
457*e4b17023SJohn Marino dump_hwloops (loops);
458*e4b17023SJohn Marino
459*e4b17023SJohn Marino return loops;
460*e4b17023SJohn Marino }
461*e4b17023SJohn Marino
462*e4b17023SJohn Marino /* Free up the loop structures in LOOPS. */
463*e4b17023SJohn Marino static void
free_loops(hwloop_info loops)464*e4b17023SJohn Marino free_loops (hwloop_info loops)
465*e4b17023SJohn Marino {
466*e4b17023SJohn Marino while (loops)
467*e4b17023SJohn Marino {
468*e4b17023SJohn Marino hwloop_info loop = loops;
469*e4b17023SJohn Marino loops = loop->next;
470*e4b17023SJohn Marino VEC_free (hwloop_info, heap, loop->loops);
471*e4b17023SJohn Marino VEC_free (basic_block, heap, loop->blocks);
472*e4b17023SJohn Marino BITMAP_FREE (loop->block_bitmap);
473*e4b17023SJohn Marino XDELETE (loop);
474*e4b17023SJohn Marino }
475*e4b17023SJohn Marino }
476*e4b17023SJohn Marino
477*e4b17023SJohn Marino #define BB_AUX_INDEX(BB) ((intptr_t) (BB)->aux)
478*e4b17023SJohn Marino
479*e4b17023SJohn Marino /* Initialize the aux fields to give ascending indices to basic blocks. */
480*e4b17023SJohn Marino static void
set_bb_indices(void)481*e4b17023SJohn Marino set_bb_indices (void)
482*e4b17023SJohn Marino {
483*e4b17023SJohn Marino basic_block bb;
484*e4b17023SJohn Marino intptr_t index;
485*e4b17023SJohn Marino
486*e4b17023SJohn Marino index = 0;
487*e4b17023SJohn Marino FOR_EACH_BB (bb)
488*e4b17023SJohn Marino bb->aux = (void *) index++;
489*e4b17023SJohn Marino }
490*e4b17023SJohn Marino
491*e4b17023SJohn Marino /* The taken-branch edge from the loop end can actually go forward.
492*e4b17023SJohn Marino If the target's hardware loop support requires that the loop end be
493*e4b17023SJohn Marino after the loop start, try to reorder a loop's basic blocks when we
494*e4b17023SJohn Marino find such a case.
495*e4b17023SJohn Marino This is not very aggressive; it only moves at most one block. It
496*e4b17023SJohn Marino does not introduce new branches into loops; it may remove them, or
497*e4b17023SJohn Marino it may switch fallthru/jump edges. */
498*e4b17023SJohn Marino static void
reorder_loops(hwloop_info loops)499*e4b17023SJohn Marino reorder_loops (hwloop_info loops)
500*e4b17023SJohn Marino {
501*e4b17023SJohn Marino basic_block bb;
502*e4b17023SJohn Marino hwloop_info loop;
503*e4b17023SJohn Marino
504*e4b17023SJohn Marino cfg_layout_initialize (0);
505*e4b17023SJohn Marino
506*e4b17023SJohn Marino set_bb_indices ();
507*e4b17023SJohn Marino
508*e4b17023SJohn Marino for (loop = loops; loop; loop = loop->next)
509*e4b17023SJohn Marino {
510*e4b17023SJohn Marino edge e;
511*e4b17023SJohn Marino edge_iterator ei;
512*e4b17023SJohn Marino
513*e4b17023SJohn Marino if (loop->bad)
514*e4b17023SJohn Marino continue;
515*e4b17023SJohn Marino
516*e4b17023SJohn Marino if (BB_AUX_INDEX (loop->head) <= BB_AUX_INDEX (loop->tail))
517*e4b17023SJohn Marino continue;
518*e4b17023SJohn Marino
519*e4b17023SJohn Marino FOR_EACH_EDGE (e, ei, loop->head->succs)
520*e4b17023SJohn Marino {
521*e4b17023SJohn Marino if (bitmap_bit_p (loop->block_bitmap, e->dest->index)
522*e4b17023SJohn Marino && BB_AUX_INDEX (e->dest) < BB_AUX_INDEX (loop->tail))
523*e4b17023SJohn Marino {
524*e4b17023SJohn Marino basic_block start_bb = e->dest;
525*e4b17023SJohn Marino basic_block start_prev_bb = start_bb->prev_bb;
526*e4b17023SJohn Marino
527*e4b17023SJohn Marino if (dump_file)
528*e4b17023SJohn Marino fprintf (dump_file, ";; Moving block %d before block %d\n",
529*e4b17023SJohn Marino loop->head->index, start_bb->index);
530*e4b17023SJohn Marino loop->head->prev_bb->next_bb = loop->head->next_bb;
531*e4b17023SJohn Marino loop->head->next_bb->prev_bb = loop->head->prev_bb;
532*e4b17023SJohn Marino
533*e4b17023SJohn Marino loop->head->prev_bb = start_prev_bb;
534*e4b17023SJohn Marino loop->head->next_bb = start_bb;
535*e4b17023SJohn Marino start_prev_bb->next_bb = start_bb->prev_bb = loop->head;
536*e4b17023SJohn Marino
537*e4b17023SJohn Marino set_bb_indices ();
538*e4b17023SJohn Marino break;
539*e4b17023SJohn Marino }
540*e4b17023SJohn Marino }
541*e4b17023SJohn Marino loops = loops->next;
542*e4b17023SJohn Marino }
543*e4b17023SJohn Marino
544*e4b17023SJohn Marino FOR_EACH_BB (bb)
545*e4b17023SJohn Marino {
546*e4b17023SJohn Marino if (bb->next_bb != EXIT_BLOCK_PTR)
547*e4b17023SJohn Marino bb->aux = bb->next_bb;
548*e4b17023SJohn Marino else
549*e4b17023SJohn Marino bb->aux = NULL;
550*e4b17023SJohn Marino }
551*e4b17023SJohn Marino cfg_layout_finalize ();
552*e4b17023SJohn Marino clear_aux_for_blocks ();
553*e4b17023SJohn Marino df_analyze ();
554*e4b17023SJohn Marino }
555*e4b17023SJohn Marino
556*e4b17023SJohn Marino /* Call the OPT function for LOOP and all of its sub-loops. This is
557*e4b17023SJohn Marino done in a depth-first search; innermost loops are visited first.
558*e4b17023SJohn Marino OPTIMIZE and FAIL are the functions passed to reorg_loops by the
559*e4b17023SJohn Marino target's reorg pass. */
560*e4b17023SJohn Marino static void
optimize_loop(hwloop_info loop,struct hw_doloop_hooks * hooks)561*e4b17023SJohn Marino optimize_loop (hwloop_info loop, struct hw_doloop_hooks *hooks)
562*e4b17023SJohn Marino {
563*e4b17023SJohn Marino int ix;
564*e4b17023SJohn Marino hwloop_info inner;
565*e4b17023SJohn Marino int inner_depth = 0;
566*e4b17023SJohn Marino
567*e4b17023SJohn Marino if (loop->visited)
568*e4b17023SJohn Marino return;
569*e4b17023SJohn Marino
570*e4b17023SJohn Marino loop->visited = 1;
571*e4b17023SJohn Marino
572*e4b17023SJohn Marino if (loop->bad)
573*e4b17023SJohn Marino {
574*e4b17023SJohn Marino if (dump_file)
575*e4b17023SJohn Marino fprintf (dump_file, ";; loop %d bad when found\n", loop->loop_no);
576*e4b17023SJohn Marino goto bad_loop;
577*e4b17023SJohn Marino }
578*e4b17023SJohn Marino
579*e4b17023SJohn Marino /* Every loop contains in its list of inner loops every loop nested inside
580*e4b17023SJohn Marino it, even if there are intermediate loops. This works because we're doing
581*e4b17023SJohn Marino a depth-first search here and never visit a loop more than once.
582*e4b17023SJohn Marino Recursion depth is effectively limited by the number of available
583*e4b17023SJohn Marino hardware registers. */
584*e4b17023SJohn Marino for (ix = 0; VEC_iterate (hwloop_info, loop->loops, ix, inner); ix++)
585*e4b17023SJohn Marino {
586*e4b17023SJohn Marino optimize_loop (inner, hooks);
587*e4b17023SJohn Marino
588*e4b17023SJohn Marino if (!inner->bad && inner_depth < inner->depth)
589*e4b17023SJohn Marino inner_depth = inner->depth;
590*e4b17023SJohn Marino /* The set of registers may be changed while optimizing the inner
591*e4b17023SJohn Marino loop. */
592*e4b17023SJohn Marino IOR_HARD_REG_SET (loop->regs_set_in_loop, inner->regs_set_in_loop);
593*e4b17023SJohn Marino }
594*e4b17023SJohn Marino
595*e4b17023SJohn Marino loop->depth = inner_depth + 1;
596*e4b17023SJohn Marino
597*e4b17023SJohn Marino if (hooks->opt (loop))
598*e4b17023SJohn Marino return;
599*e4b17023SJohn Marino
600*e4b17023SJohn Marino bad_loop:
601*e4b17023SJohn Marino if (dump_file)
602*e4b17023SJohn Marino fprintf (dump_file, ";; loop %d is bad\n", loop->loop_no);
603*e4b17023SJohn Marino
604*e4b17023SJohn Marino loop->bad = true;
605*e4b17023SJohn Marino hooks->fail (loop);
606*e4b17023SJohn Marino }
607*e4b17023SJohn Marino
608*e4b17023SJohn Marino /* This function can be used from a port's machine_dependent_reorg to
609*e4b17023SJohn Marino find and analyze loops that end in loop_end instructions. It uses
610*e4b17023SJohn Marino a set of function pointers in HOOKS to call back into the
611*e4b17023SJohn Marino target-specific functions to perform the actual machine-specific
612*e4b17023SJohn Marino transformations.
613*e4b17023SJohn Marino
614*e4b17023SJohn Marino Such transformations typically involve additional set-up
615*e4b17023SJohn Marino instructions before the loop, to define loop bounds or set up a
616*e4b17023SJohn Marino special loop counter register.
617*e4b17023SJohn Marino
618*e4b17023SJohn Marino DO_REORDER should be set to true if we should try to use the
619*e4b17023SJohn Marino reorder_loops function to ensure the loop end occurs after the loop
620*e4b17023SJohn Marino start. This is for use by targets where the loop hardware requires
621*e4b17023SJohn Marino this condition.
622*e4b17023SJohn Marino
623*e4b17023SJohn Marino HOOKS is used to pass in target specific hooks; see
624*e4b17023SJohn Marino hw-doloop.h. */
625*e4b17023SJohn Marino void
reorg_loops(bool do_reorder,struct hw_doloop_hooks * hooks)626*e4b17023SJohn Marino reorg_loops (bool do_reorder, struct hw_doloop_hooks *hooks)
627*e4b17023SJohn Marino {
628*e4b17023SJohn Marino hwloop_info loops = NULL;
629*e4b17023SJohn Marino hwloop_info loop;
630*e4b17023SJohn Marino bitmap_obstack stack;
631*e4b17023SJohn Marino
632*e4b17023SJohn Marino df_live_add_problem ();
633*e4b17023SJohn Marino df_live_set_all_dirty ();
634*e4b17023SJohn Marino df_analyze ();
635*e4b17023SJohn Marino
636*e4b17023SJohn Marino bitmap_obstack_initialize (&stack);
637*e4b17023SJohn Marino
638*e4b17023SJohn Marino if (dump_file)
639*e4b17023SJohn Marino fprintf (dump_file, ";; Find loops, first pass\n\n");
640*e4b17023SJohn Marino
641*e4b17023SJohn Marino loops = discover_loops (&stack, hooks);
642*e4b17023SJohn Marino
643*e4b17023SJohn Marino if (do_reorder)
644*e4b17023SJohn Marino {
645*e4b17023SJohn Marino reorder_loops (loops);
646*e4b17023SJohn Marino free_loops (loops);
647*e4b17023SJohn Marino
648*e4b17023SJohn Marino if (dump_file)
649*e4b17023SJohn Marino fprintf (dump_file, ";; Find loops, second pass\n\n");
650*e4b17023SJohn Marino
651*e4b17023SJohn Marino loops = discover_loops (&stack, hooks);
652*e4b17023SJohn Marino }
653*e4b17023SJohn Marino
654*e4b17023SJohn Marino for (loop = loops; loop; loop = loop->next)
655*e4b17023SJohn Marino scan_loop (loop);
656*e4b17023SJohn Marino
657*e4b17023SJohn Marino /* Now apply the optimizations. */
658*e4b17023SJohn Marino for (loop = loops; loop; loop = loop->next)
659*e4b17023SJohn Marino optimize_loop (loop, hooks);
660*e4b17023SJohn Marino
661*e4b17023SJohn Marino if (dump_file)
662*e4b17023SJohn Marino {
663*e4b17023SJohn Marino fprintf (dump_file, ";; After hardware loops optimization:\n\n");
664*e4b17023SJohn Marino dump_hwloops (loops);
665*e4b17023SJohn Marino }
666*e4b17023SJohn Marino
667*e4b17023SJohn Marino free_loops (loops);
668*e4b17023SJohn Marino
669*e4b17023SJohn Marino if (dump_file)
670*e4b17023SJohn Marino print_rtl (dump_file, get_insns ());
671*e4b17023SJohn Marino }
672*e4b17023SJohn Marino #endif
673