1*e4b17023SJohn Marino /* Loop unswitching for GNU compiler.
2*e4b17023SJohn Marino Copyright (C) 2002, 2003, 2004, 2005, 2007, 2008, 2009, 2010, 2012
3*e4b17023SJohn Marino 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 "hard-reg-set.h"
27*e4b17023SJohn Marino #include "obstack.h"
28*e4b17023SJohn Marino #include "basic-block.h"
29*e4b17023SJohn Marino #include "cfgloop.h"
30*e4b17023SJohn Marino #include "cfglayout.h"
31*e4b17023SJohn Marino #include "params.h"
32*e4b17023SJohn Marino #include "output.h"
33*e4b17023SJohn Marino #include "expr.h"
34*e4b17023SJohn Marino
35*e4b17023SJohn Marino /* This pass moves constant conditions out of loops, duplicating the loop
36*e4b17023SJohn Marino in progress, i.e. this code:
37*e4b17023SJohn Marino
38*e4b17023SJohn Marino while (loop_cond)
39*e4b17023SJohn Marino {
40*e4b17023SJohn Marino A;
41*e4b17023SJohn Marino if (cond)
42*e4b17023SJohn Marino branch1;
43*e4b17023SJohn Marino else
44*e4b17023SJohn Marino branch2;
45*e4b17023SJohn Marino B;
46*e4b17023SJohn Marino if (cond)
47*e4b17023SJohn Marino branch3;
48*e4b17023SJohn Marino C;
49*e4b17023SJohn Marino }
50*e4b17023SJohn Marino where nothing inside the loop alters cond is transformed
51*e4b17023SJohn Marino into
52*e4b17023SJohn Marino
53*e4b17023SJohn Marino if (cond)
54*e4b17023SJohn Marino {
55*e4b17023SJohn Marino while (loop_cond)
56*e4b17023SJohn Marino {
57*e4b17023SJohn Marino A;
58*e4b17023SJohn Marino branch1;
59*e4b17023SJohn Marino B;
60*e4b17023SJohn Marino branch3;
61*e4b17023SJohn Marino C;
62*e4b17023SJohn Marino }
63*e4b17023SJohn Marino }
64*e4b17023SJohn Marino else
65*e4b17023SJohn Marino {
66*e4b17023SJohn Marino while (loop_cond)
67*e4b17023SJohn Marino {
68*e4b17023SJohn Marino A;
69*e4b17023SJohn Marino branch2;
70*e4b17023SJohn Marino B;
71*e4b17023SJohn Marino C;
72*e4b17023SJohn Marino }
73*e4b17023SJohn Marino }
74*e4b17023SJohn Marino
75*e4b17023SJohn Marino Duplicating the loop might lead to code growth exponential in number of
76*e4b17023SJohn Marino branches inside loop, so we limit the number of unswitchings performed
77*e4b17023SJohn Marino in a single loop to PARAM_MAX_UNSWITCH_LEVEL. We only perform the
78*e4b17023SJohn Marino transformation on innermost loops, as the benefit of doing it on loops
79*e4b17023SJohn Marino containing subloops would not be very large compared to complications
80*e4b17023SJohn Marino with handling this case. */
81*e4b17023SJohn Marino
82*e4b17023SJohn Marino static struct loop *unswitch_loop (struct loop *, basic_block, rtx, rtx);
83*e4b17023SJohn Marino static void unswitch_single_loop (struct loop *, rtx, int);
84*e4b17023SJohn Marino static rtx may_unswitch_on (basic_block, struct loop *, rtx *);
85*e4b17023SJohn Marino
86*e4b17023SJohn Marino /* Prepare a sequence comparing OP0 with OP1 using COMP and jumping to LABEL if
87*e4b17023SJohn Marino true, with probability PROB. If CINSN is not NULL, it is the insn to copy
88*e4b17023SJohn Marino in order to create a jump. */
89*e4b17023SJohn Marino
90*e4b17023SJohn Marino rtx
compare_and_jump_seq(rtx op0,rtx op1,enum rtx_code comp,rtx label,int prob,rtx cinsn)91*e4b17023SJohn Marino compare_and_jump_seq (rtx op0, rtx op1, enum rtx_code comp, rtx label, int prob,
92*e4b17023SJohn Marino rtx cinsn)
93*e4b17023SJohn Marino {
94*e4b17023SJohn Marino rtx seq, jump, cond;
95*e4b17023SJohn Marino enum machine_mode mode;
96*e4b17023SJohn Marino
97*e4b17023SJohn Marino mode = GET_MODE (op0);
98*e4b17023SJohn Marino if (mode == VOIDmode)
99*e4b17023SJohn Marino mode = GET_MODE (op1);
100*e4b17023SJohn Marino
101*e4b17023SJohn Marino start_sequence ();
102*e4b17023SJohn Marino if (GET_MODE_CLASS (mode) == MODE_CC)
103*e4b17023SJohn Marino {
104*e4b17023SJohn Marino /* A hack -- there seems to be no easy generic way how to make a
105*e4b17023SJohn Marino conditional jump from a ccmode comparison. */
106*e4b17023SJohn Marino gcc_assert (cinsn);
107*e4b17023SJohn Marino cond = XEXP (SET_SRC (pc_set (cinsn)), 0);
108*e4b17023SJohn Marino gcc_assert (GET_CODE (cond) == comp);
109*e4b17023SJohn Marino gcc_assert (rtx_equal_p (op0, XEXP (cond, 0)));
110*e4b17023SJohn Marino gcc_assert (rtx_equal_p (op1, XEXP (cond, 1)));
111*e4b17023SJohn Marino emit_jump_insn (copy_insn (PATTERN (cinsn)));
112*e4b17023SJohn Marino jump = get_last_insn ();
113*e4b17023SJohn Marino gcc_assert (JUMP_P (jump));
114*e4b17023SJohn Marino JUMP_LABEL (jump) = JUMP_LABEL (cinsn);
115*e4b17023SJohn Marino LABEL_NUSES (JUMP_LABEL (jump))++;
116*e4b17023SJohn Marino redirect_jump (jump, label, 0);
117*e4b17023SJohn Marino }
118*e4b17023SJohn Marino else
119*e4b17023SJohn Marino {
120*e4b17023SJohn Marino gcc_assert (!cinsn);
121*e4b17023SJohn Marino
122*e4b17023SJohn Marino op0 = force_operand (op0, NULL_RTX);
123*e4b17023SJohn Marino op1 = force_operand (op1, NULL_RTX);
124*e4b17023SJohn Marino do_compare_rtx_and_jump (op0, op1, comp, 0,
125*e4b17023SJohn Marino mode, NULL_RTX, NULL_RTX, label, -1);
126*e4b17023SJohn Marino jump = get_last_insn ();
127*e4b17023SJohn Marino gcc_assert (JUMP_P (jump));
128*e4b17023SJohn Marino JUMP_LABEL (jump) = label;
129*e4b17023SJohn Marino LABEL_NUSES (label)++;
130*e4b17023SJohn Marino }
131*e4b17023SJohn Marino add_reg_note (jump, REG_BR_PROB, GEN_INT (prob));
132*e4b17023SJohn Marino
133*e4b17023SJohn Marino seq = get_insns ();
134*e4b17023SJohn Marino end_sequence ();
135*e4b17023SJohn Marino
136*e4b17023SJohn Marino return seq;
137*e4b17023SJohn Marino }
138*e4b17023SJohn Marino
139*e4b17023SJohn Marino /* Main entry point. Perform loop unswitching on all suitable loops. */
140*e4b17023SJohn Marino void
unswitch_loops(void)141*e4b17023SJohn Marino unswitch_loops (void)
142*e4b17023SJohn Marino {
143*e4b17023SJohn Marino loop_iterator li;
144*e4b17023SJohn Marino struct loop *loop;
145*e4b17023SJohn Marino
146*e4b17023SJohn Marino /* Go through inner loops (only original ones). */
147*e4b17023SJohn Marino
148*e4b17023SJohn Marino FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
149*e4b17023SJohn Marino {
150*e4b17023SJohn Marino unswitch_single_loop (loop, NULL_RTX, 0);
151*e4b17023SJohn Marino #ifdef ENABLE_CHECKING
152*e4b17023SJohn Marino verify_dominators (CDI_DOMINATORS);
153*e4b17023SJohn Marino verify_loop_structure ();
154*e4b17023SJohn Marino #endif
155*e4b17023SJohn Marino }
156*e4b17023SJohn Marino
157*e4b17023SJohn Marino iv_analysis_done ();
158*e4b17023SJohn Marino }
159*e4b17023SJohn Marino
160*e4b17023SJohn Marino /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
161*e4b17023SJohn Marino basic blocks (for what it means see comments below). In case condition
162*e4b17023SJohn Marino compares loop invariant cc mode register, return the jump in CINSN. */
163*e4b17023SJohn Marino
164*e4b17023SJohn Marino static rtx
may_unswitch_on(basic_block bb,struct loop * loop,rtx * cinsn)165*e4b17023SJohn Marino may_unswitch_on (basic_block bb, struct loop *loop, rtx *cinsn)
166*e4b17023SJohn Marino {
167*e4b17023SJohn Marino rtx test, at, op[2], stest;
168*e4b17023SJohn Marino struct rtx_iv iv;
169*e4b17023SJohn Marino unsigned i;
170*e4b17023SJohn Marino enum machine_mode mode;
171*e4b17023SJohn Marino
172*e4b17023SJohn Marino /* BB must end in a simple conditional jump. */
173*e4b17023SJohn Marino if (EDGE_COUNT (bb->succs) != 2)
174*e4b17023SJohn Marino return NULL_RTX;
175*e4b17023SJohn Marino if (!any_condjump_p (BB_END (bb)))
176*e4b17023SJohn Marino return NULL_RTX;
177*e4b17023SJohn Marino
178*e4b17023SJohn Marino /* With branches inside loop. */
179*e4b17023SJohn Marino if (!flow_bb_inside_loop_p (loop, EDGE_SUCC (bb, 0)->dest)
180*e4b17023SJohn Marino || !flow_bb_inside_loop_p (loop, EDGE_SUCC (bb, 1)->dest))
181*e4b17023SJohn Marino return NULL_RTX;
182*e4b17023SJohn Marino
183*e4b17023SJohn Marino /* It must be executed just once each iteration (because otherwise we
184*e4b17023SJohn Marino are unable to update dominator/irreducible loop information correctly). */
185*e4b17023SJohn Marino if (!just_once_each_iteration_p (loop, bb))
186*e4b17023SJohn Marino return NULL_RTX;
187*e4b17023SJohn Marino
188*e4b17023SJohn Marino /* Condition must be invariant. */
189*e4b17023SJohn Marino test = get_condition (BB_END (bb), &at, true, false);
190*e4b17023SJohn Marino if (!test)
191*e4b17023SJohn Marino return NULL_RTX;
192*e4b17023SJohn Marino
193*e4b17023SJohn Marino for (i = 0; i < 2; i++)
194*e4b17023SJohn Marino {
195*e4b17023SJohn Marino op[i] = XEXP (test, i);
196*e4b17023SJohn Marino
197*e4b17023SJohn Marino if (CONSTANT_P (op[i]))
198*e4b17023SJohn Marino continue;
199*e4b17023SJohn Marino
200*e4b17023SJohn Marino if (!iv_analyze (at, op[i], &iv))
201*e4b17023SJohn Marino return NULL_RTX;
202*e4b17023SJohn Marino if (iv.step != const0_rtx
203*e4b17023SJohn Marino || iv.first_special)
204*e4b17023SJohn Marino return NULL_RTX;
205*e4b17023SJohn Marino
206*e4b17023SJohn Marino op[i] = get_iv_value (&iv, const0_rtx);
207*e4b17023SJohn Marino }
208*e4b17023SJohn Marino
209*e4b17023SJohn Marino mode = GET_MODE (op[0]);
210*e4b17023SJohn Marino if (mode == VOIDmode)
211*e4b17023SJohn Marino mode = GET_MODE (op[1]);
212*e4b17023SJohn Marino if (GET_MODE_CLASS (mode) == MODE_CC)
213*e4b17023SJohn Marino {
214*e4b17023SJohn Marino if (at != BB_END (bb))
215*e4b17023SJohn Marino return NULL_RTX;
216*e4b17023SJohn Marino
217*e4b17023SJohn Marino if (!rtx_equal_p (op[0], XEXP (test, 0))
218*e4b17023SJohn Marino || !rtx_equal_p (op[1], XEXP (test, 1)))
219*e4b17023SJohn Marino return NULL_RTX;
220*e4b17023SJohn Marino
221*e4b17023SJohn Marino *cinsn = BB_END (bb);
222*e4b17023SJohn Marino return test;
223*e4b17023SJohn Marino }
224*e4b17023SJohn Marino
225*e4b17023SJohn Marino stest = simplify_gen_relational (GET_CODE (test), SImode,
226*e4b17023SJohn Marino mode, op[0], op[1]);
227*e4b17023SJohn Marino if (stest == const0_rtx
228*e4b17023SJohn Marino || stest == const_true_rtx)
229*e4b17023SJohn Marino return stest;
230*e4b17023SJohn Marino
231*e4b17023SJohn Marino return canon_condition (gen_rtx_fmt_ee (GET_CODE (test), SImode,
232*e4b17023SJohn Marino op[0], op[1]));
233*e4b17023SJohn Marino }
234*e4b17023SJohn Marino
235*e4b17023SJohn Marino /* Reverses CONDition; returns NULL if we cannot. */
236*e4b17023SJohn Marino rtx
reversed_condition(rtx cond)237*e4b17023SJohn Marino reversed_condition (rtx cond)
238*e4b17023SJohn Marino {
239*e4b17023SJohn Marino enum rtx_code reversed;
240*e4b17023SJohn Marino reversed = reversed_comparison_code (cond, NULL);
241*e4b17023SJohn Marino if (reversed == UNKNOWN)
242*e4b17023SJohn Marino return NULL_RTX;
243*e4b17023SJohn Marino else
244*e4b17023SJohn Marino return gen_rtx_fmt_ee (reversed,
245*e4b17023SJohn Marino GET_MODE (cond), XEXP (cond, 0),
246*e4b17023SJohn Marino XEXP (cond, 1));
247*e4b17023SJohn Marino }
248*e4b17023SJohn Marino
249*e4b17023SJohn Marino /* Unswitch single LOOP. COND_CHECKED holds list of conditions we already
250*e4b17023SJohn Marino unswitched on and are therefore known to be true in this LOOP. NUM is
251*e4b17023SJohn Marino number of unswitchings done; do not allow it to grow too much, it is too
252*e4b17023SJohn Marino easy to create example on that the code would grow exponentially. */
253*e4b17023SJohn Marino static void
unswitch_single_loop(struct loop * loop,rtx cond_checked,int num)254*e4b17023SJohn Marino unswitch_single_loop (struct loop *loop, rtx cond_checked, int num)
255*e4b17023SJohn Marino {
256*e4b17023SJohn Marino basic_block *bbs;
257*e4b17023SJohn Marino struct loop *nloop;
258*e4b17023SJohn Marino unsigned i;
259*e4b17023SJohn Marino rtx cond, rcond = NULL_RTX, conds, rconds, acond, cinsn;
260*e4b17023SJohn Marino int repeat;
261*e4b17023SJohn Marino edge e;
262*e4b17023SJohn Marino
263*e4b17023SJohn Marino /* Do not unswitch too much. */
264*e4b17023SJohn Marino if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
265*e4b17023SJohn Marino {
266*e4b17023SJohn Marino if (dump_file)
267*e4b17023SJohn Marino fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
268*e4b17023SJohn Marino return;
269*e4b17023SJohn Marino }
270*e4b17023SJohn Marino
271*e4b17023SJohn Marino /* Only unswitch innermost loops. */
272*e4b17023SJohn Marino if (loop->inner)
273*e4b17023SJohn Marino {
274*e4b17023SJohn Marino if (dump_file)
275*e4b17023SJohn Marino fprintf (dump_file, ";; Not unswitching, not innermost loop\n");
276*e4b17023SJohn Marino return;
277*e4b17023SJohn Marino }
278*e4b17023SJohn Marino
279*e4b17023SJohn Marino /* We must be able to duplicate loop body. */
280*e4b17023SJohn Marino if (!can_duplicate_loop_p (loop))
281*e4b17023SJohn Marino {
282*e4b17023SJohn Marino if (dump_file)
283*e4b17023SJohn Marino fprintf (dump_file, ";; Not unswitching, can't duplicate loop\n");
284*e4b17023SJohn Marino return;
285*e4b17023SJohn Marino }
286*e4b17023SJohn Marino
287*e4b17023SJohn Marino /* The loop should not be too large, to limit code growth. */
288*e4b17023SJohn Marino if (num_loop_insns (loop) > PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS))
289*e4b17023SJohn Marino {
290*e4b17023SJohn Marino if (dump_file)
291*e4b17023SJohn Marino fprintf (dump_file, ";; Not unswitching, loop too big\n");
292*e4b17023SJohn Marino return;
293*e4b17023SJohn Marino }
294*e4b17023SJohn Marino
295*e4b17023SJohn Marino /* Do not unswitch in cold areas. */
296*e4b17023SJohn Marino if (optimize_loop_for_size_p (loop))
297*e4b17023SJohn Marino {
298*e4b17023SJohn Marino if (dump_file)
299*e4b17023SJohn Marino fprintf (dump_file, ";; Not unswitching, not hot area\n");
300*e4b17023SJohn Marino return;
301*e4b17023SJohn Marino }
302*e4b17023SJohn Marino
303*e4b17023SJohn Marino /* Nor if the loop usually does not roll. */
304*e4b17023SJohn Marino if (expected_loop_iterations (loop) < 1)
305*e4b17023SJohn Marino {
306*e4b17023SJohn Marino if (dump_file)
307*e4b17023SJohn Marino fprintf (dump_file, ";; Not unswitching, loop iterations < 1\n");
308*e4b17023SJohn Marino return;
309*e4b17023SJohn Marino }
310*e4b17023SJohn Marino
311*e4b17023SJohn Marino do
312*e4b17023SJohn Marino {
313*e4b17023SJohn Marino repeat = 0;
314*e4b17023SJohn Marino cinsn = NULL_RTX;
315*e4b17023SJohn Marino
316*e4b17023SJohn Marino /* Find a bb to unswitch on. */
317*e4b17023SJohn Marino bbs = get_loop_body (loop);
318*e4b17023SJohn Marino iv_analysis_loop_init (loop);
319*e4b17023SJohn Marino for (i = 0; i < loop->num_nodes; i++)
320*e4b17023SJohn Marino if ((cond = may_unswitch_on (bbs[i], loop, &cinsn)))
321*e4b17023SJohn Marino break;
322*e4b17023SJohn Marino
323*e4b17023SJohn Marino if (i == loop->num_nodes)
324*e4b17023SJohn Marino {
325*e4b17023SJohn Marino free (bbs);
326*e4b17023SJohn Marino return;
327*e4b17023SJohn Marino }
328*e4b17023SJohn Marino
329*e4b17023SJohn Marino if (cond != const0_rtx
330*e4b17023SJohn Marino && cond != const_true_rtx)
331*e4b17023SJohn Marino {
332*e4b17023SJohn Marino rcond = reversed_condition (cond);
333*e4b17023SJohn Marino if (rcond)
334*e4b17023SJohn Marino rcond = canon_condition (rcond);
335*e4b17023SJohn Marino
336*e4b17023SJohn Marino /* Check whether the result can be predicted. */
337*e4b17023SJohn Marino for (acond = cond_checked; acond; acond = XEXP (acond, 1))
338*e4b17023SJohn Marino simplify_using_condition (XEXP (acond, 0), &cond, NULL);
339*e4b17023SJohn Marino }
340*e4b17023SJohn Marino
341*e4b17023SJohn Marino if (cond == const_true_rtx)
342*e4b17023SJohn Marino {
343*e4b17023SJohn Marino /* Remove false path. */
344*e4b17023SJohn Marino e = FALLTHRU_EDGE (bbs[i]);
345*e4b17023SJohn Marino remove_path (e);
346*e4b17023SJohn Marino free (bbs);
347*e4b17023SJohn Marino repeat = 1;
348*e4b17023SJohn Marino }
349*e4b17023SJohn Marino else if (cond == const0_rtx)
350*e4b17023SJohn Marino {
351*e4b17023SJohn Marino /* Remove true path. */
352*e4b17023SJohn Marino e = BRANCH_EDGE (bbs[i]);
353*e4b17023SJohn Marino remove_path (e);
354*e4b17023SJohn Marino free (bbs);
355*e4b17023SJohn Marino repeat = 1;
356*e4b17023SJohn Marino }
357*e4b17023SJohn Marino } while (repeat);
358*e4b17023SJohn Marino
359*e4b17023SJohn Marino /* We found the condition we can unswitch on. */
360*e4b17023SJohn Marino conds = alloc_EXPR_LIST (0, cond, cond_checked);
361*e4b17023SJohn Marino if (rcond)
362*e4b17023SJohn Marino rconds = alloc_EXPR_LIST (0, rcond, cond_checked);
363*e4b17023SJohn Marino else
364*e4b17023SJohn Marino rconds = cond_checked;
365*e4b17023SJohn Marino
366*e4b17023SJohn Marino if (dump_file)
367*e4b17023SJohn Marino fprintf (dump_file, ";; Unswitching loop\n");
368*e4b17023SJohn Marino
369*e4b17023SJohn Marino /* Unswitch the loop on this condition. */
370*e4b17023SJohn Marino nloop = unswitch_loop (loop, bbs[i], copy_rtx_if_shared (cond), cinsn);
371*e4b17023SJohn Marino gcc_assert (nloop);
372*e4b17023SJohn Marino
373*e4b17023SJohn Marino /* Invoke itself on modified loops. */
374*e4b17023SJohn Marino unswitch_single_loop (nloop, rconds, num + 1);
375*e4b17023SJohn Marino unswitch_single_loop (loop, conds, num + 1);
376*e4b17023SJohn Marino
377*e4b17023SJohn Marino free_EXPR_LIST_node (conds);
378*e4b17023SJohn Marino if (rcond)
379*e4b17023SJohn Marino free_EXPR_LIST_node (rconds);
380*e4b17023SJohn Marino
381*e4b17023SJohn Marino free (bbs);
382*e4b17023SJohn Marino }
383*e4b17023SJohn Marino
384*e4b17023SJohn Marino /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support
385*e4b17023SJohn Marino unswitching of innermost loops. UNSWITCH_ON must be executed in every
386*e4b17023SJohn Marino iteration, i.e. it must dominate LOOP latch. COND is the condition
387*e4b17023SJohn Marino determining which loop is entered. Returns NULL if impossible, new loop
388*e4b17023SJohn Marino otherwise. The new loop is entered if COND is true. If CINSN is not
389*e4b17023SJohn Marino NULL, it is the insn in that COND is compared. */
390*e4b17023SJohn Marino
391*e4b17023SJohn Marino static struct loop *
unswitch_loop(struct loop * loop,basic_block unswitch_on,rtx cond,rtx cinsn)392*e4b17023SJohn Marino unswitch_loop (struct loop *loop, basic_block unswitch_on, rtx cond, rtx cinsn)
393*e4b17023SJohn Marino {
394*e4b17023SJohn Marino edge entry, latch_edge, true_edge, false_edge, e;
395*e4b17023SJohn Marino basic_block switch_bb, unswitch_on_alt;
396*e4b17023SJohn Marino struct loop *nloop;
397*e4b17023SJohn Marino int irred_flag, prob;
398*e4b17023SJohn Marino rtx seq;
399*e4b17023SJohn Marino
400*e4b17023SJohn Marino /* Some sanity checking. */
401*e4b17023SJohn Marino gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
402*e4b17023SJohn Marino gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
403*e4b17023SJohn Marino gcc_assert (just_once_each_iteration_p (loop, unswitch_on));
404*e4b17023SJohn Marino gcc_assert (!loop->inner);
405*e4b17023SJohn Marino gcc_assert (flow_bb_inside_loop_p (loop, EDGE_SUCC (unswitch_on, 0)->dest));
406*e4b17023SJohn Marino gcc_assert (flow_bb_inside_loop_p (loop, EDGE_SUCC (unswitch_on, 1)->dest));
407*e4b17023SJohn Marino
408*e4b17023SJohn Marino entry = loop_preheader_edge (loop);
409*e4b17023SJohn Marino
410*e4b17023SJohn Marino /* Make a copy. */
411*e4b17023SJohn Marino irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP;
412*e4b17023SJohn Marino entry->flags &= ~EDGE_IRREDUCIBLE_LOOP;
413*e4b17023SJohn Marino if (!duplicate_loop_to_header_edge (loop, entry, 1,
414*e4b17023SJohn Marino NULL, NULL, NULL, 0))
415*e4b17023SJohn Marino return NULL;
416*e4b17023SJohn Marino entry->flags |= irred_flag;
417*e4b17023SJohn Marino
418*e4b17023SJohn Marino /* Record the block with condition we unswitch on. */
419*e4b17023SJohn Marino unswitch_on_alt = get_bb_copy (unswitch_on);
420*e4b17023SJohn Marino true_edge = BRANCH_EDGE (unswitch_on_alt);
421*e4b17023SJohn Marino false_edge = FALLTHRU_EDGE (unswitch_on);
422*e4b17023SJohn Marino latch_edge = single_succ_edge (get_bb_copy (loop->latch));
423*e4b17023SJohn Marino
424*e4b17023SJohn Marino /* Create a block with the condition. */
425*e4b17023SJohn Marino prob = true_edge->probability;
426*e4b17023SJohn Marino switch_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
427*e4b17023SJohn Marino seq = compare_and_jump_seq (XEXP (cond, 0), XEXP (cond, 1), GET_CODE (cond),
428*e4b17023SJohn Marino block_label (true_edge->dest),
429*e4b17023SJohn Marino prob, cinsn);
430*e4b17023SJohn Marino emit_insn_after (seq, BB_END (switch_bb));
431*e4b17023SJohn Marino e = make_edge (switch_bb, true_edge->dest, 0);
432*e4b17023SJohn Marino e->probability = prob;
433*e4b17023SJohn Marino e->count = latch_edge->count * prob / REG_BR_PROB_BASE;
434*e4b17023SJohn Marino e = make_edge (switch_bb, FALLTHRU_EDGE (unswitch_on)->dest, EDGE_FALLTHRU);
435*e4b17023SJohn Marino e->probability = false_edge->probability;
436*e4b17023SJohn Marino e->count = latch_edge->count * (false_edge->probability) / REG_BR_PROB_BASE;
437*e4b17023SJohn Marino
438*e4b17023SJohn Marino if (irred_flag)
439*e4b17023SJohn Marino {
440*e4b17023SJohn Marino switch_bb->flags |= BB_IRREDUCIBLE_LOOP;
441*e4b17023SJohn Marino EDGE_SUCC (switch_bb, 0)->flags |= EDGE_IRREDUCIBLE_LOOP;
442*e4b17023SJohn Marino EDGE_SUCC (switch_bb, 1)->flags |= EDGE_IRREDUCIBLE_LOOP;
443*e4b17023SJohn Marino }
444*e4b17023SJohn Marino else
445*e4b17023SJohn Marino {
446*e4b17023SJohn Marino switch_bb->flags &= ~BB_IRREDUCIBLE_LOOP;
447*e4b17023SJohn Marino EDGE_SUCC (switch_bb, 0)->flags &= ~EDGE_IRREDUCIBLE_LOOP;
448*e4b17023SJohn Marino EDGE_SUCC (switch_bb, 1)->flags &= ~EDGE_IRREDUCIBLE_LOOP;
449*e4b17023SJohn Marino }
450*e4b17023SJohn Marino
451*e4b17023SJohn Marino /* Loopify from the copy of LOOP body, constructing the new loop. */
452*e4b17023SJohn Marino nloop = loopify (latch_edge,
453*e4b17023SJohn Marino single_pred_edge (get_bb_copy (loop->header)), switch_bb,
454*e4b17023SJohn Marino BRANCH_EDGE (switch_bb), FALLTHRU_EDGE (switch_bb), true,
455*e4b17023SJohn Marino prob, REG_BR_PROB_BASE - prob);
456*e4b17023SJohn Marino
457*e4b17023SJohn Marino /* Remove branches that are now unreachable in new loops. */
458*e4b17023SJohn Marino remove_path (true_edge);
459*e4b17023SJohn Marino remove_path (false_edge);
460*e4b17023SJohn Marino
461*e4b17023SJohn Marino /* Preserve the simple loop preheaders. */
462*e4b17023SJohn Marino split_edge (loop_preheader_edge (loop));
463*e4b17023SJohn Marino split_edge (loop_preheader_edge (nloop));
464*e4b17023SJohn Marino
465*e4b17023SJohn Marino return nloop;
466*e4b17023SJohn Marino }
467