/* Loop unswitching for GNU compiler.
- Copyright (C) 2002 Free Software Foundation, Inc.
+ Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc.
This file is part of GCC.
#include "expr.h"
/* This pass moves constant conditions out of loops, duplicating the loop
- in progres, i.e. this code:
+ in progress, i.e. this code:
while (loop_cond)
{
containing subloops would not be very large compared to complications
with handling this case. */
-static struct loop *unswitch_loop PARAMS ((struct loops *,
- struct loop *, basic_block));
-static void unswitch_single_loop PARAMS ((struct loops *, struct loop *,
- rtx, int));
-static bool may_unswitch_on_p PARAMS ((struct loops *, basic_block,
- struct loop *, basic_block *));
-static rtx reversed_condition PARAMS ((rtx));
+static struct loop *unswitch_loop (struct loops *, struct loop *,
+ basic_block, rtx, rtx);
+static void unswitch_single_loop (struct loops *, struct loop *, rtx, int);
+static rtx may_unswitch_on (basic_block, struct loop *, rtx *);
+
+/* Prepare a sequence comparing OP0 with OP1 using COMP and jumping to LABEL if
+ true, with probability PROB. If CINSN is not NULL, it is the insn to copy
+ in order to create a jump. */
+
+rtx
+compare_and_jump_seq (rtx op0, rtx op1, enum rtx_code comp, rtx label, int prob,
+ rtx cinsn)
+{
+ rtx seq, jump, cond;
+ enum machine_mode mode;
+
+ mode = GET_MODE (op0);
+ if (mode == VOIDmode)
+ mode = GET_MODE (op1);
+
+ start_sequence ();
+ if (GET_MODE_CLASS (mode) == MODE_CC)
+ {
+ /* A hack -- there seems to be no easy generic way how to make a
+ conditional jump from a ccmode comparison. */
+ if (!cinsn)
+ abort ();
+ cond = XEXP (SET_SRC (pc_set (cinsn)), 0);
+ if (GET_CODE (cond) != comp
+ || !rtx_equal_p (op0, XEXP (cond, 0))
+ || !rtx_equal_p (op1, XEXP (cond, 1)))
+ abort ();
+ emit_jump_insn (copy_insn (PATTERN (cinsn)));
+ jump = get_last_insn ();
+ JUMP_LABEL (jump) = JUMP_LABEL (cinsn);
+ LABEL_NUSES (JUMP_LABEL (jump))++;
+ redirect_jump (jump, label, 0);
+ }
+ else
+ {
+ if (cinsn)
+ abort ();
+
+ op0 = force_operand (op0, NULL_RTX);
+ op1 = force_operand (op1, NULL_RTX);
+ do_compare_rtx_and_jump (op0, op1, comp, 0,
+ mode, NULL_RTX, NULL_RTX, label);
+ jump = get_last_insn ();
+ JUMP_LABEL (jump) = label;
+ LABEL_NUSES (label)++;
+ }
+ REG_NOTES (jump) = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob),
+ REG_NOTES (jump));
+ seq = get_insns ();
+ end_sequence ();
+
+ return seq;
+}
/* Main entry point. Perform loop unswitching on all suitable LOOPS. */
void
-unswitch_loops (loops)
- struct loops *loops;
+unswitch_loops (struct loops *loops)
{
int i, num;
struct loop *loop;
/* Go through inner loops (only original ones). */
num = loops->num;
-
+
for (i = 1; i < num; i++)
{
/* Removed loop? */
unswitch_single_loop (loops, loop, NULL_RTX, 0);
#ifdef ENABLE_CHECKING
- verify_dominators (loops->cfg.dom);
+ verify_dominators (CDI_DOMINATORS);
verify_loop_structure (loops);
#endif
}
+
+ iv_analysis_done ();
}
/* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
- basic blocks (for what it means see comments below). List of basic blocks
- inside LOOP is provided in BODY to save time. */
-static bool
-may_unswitch_on_p (loops, bb, loop, body)
- struct loops *loops;
- basic_block bb;
- struct loop *loop;
- basic_block *body;
+ basic blocks (for what it means see comments below). In case condition
+ compares loop invariant cc mode register, return the jump in CINSN. */
+
+static rtx
+may_unswitch_on (basic_block bb, struct loop *loop, rtx *cinsn)
{
- rtx test;
+ rtx test, at, insn, op[2];
+ struct rtx_iv iv;
unsigned i;
+ enum machine_mode mode;
/* BB must end in a simple conditional jump. */
if (!bb->succ || !bb->succ->succ_next || bb->succ->succ_next->succ_next)
- return false;
- if (!any_condjump_p (bb->end))
- return false;
+ return NULL_RTX;
+ if (!any_condjump_p (BB_END (bb)))
+ return NULL_RTX;
/* With branches inside loop. */
if (!flow_bb_inside_loop_p (loop, bb->succ->dest)
|| !flow_bb_inside_loop_p (loop, bb->succ->succ_next->dest))
- return false;
+ return NULL_RTX;
/* It must be executed just once each iteration (because otherwise we
are unable to update dominator/irreducible loop information correctly). */
- if (!just_once_each_iteration_p (loops, loop, bb))
- return false;
+ if (!just_once_each_iteration_p (loop, bb))
+ return NULL_RTX;
- /* Condition must be invariant. We use just a stupid test of invariantness
- of the condition: all used regs must not be modified inside loop body. */
- test = get_condition (bb->end, NULL);
+ /* Condition must be invariant. */
+ test = get_condition (BB_END (bb), &at, true);
if (!test)
- return false;
+ return NULL_RTX;
- for (i = 0; i < loop->num_nodes; i++)
- if (modified_between_p (test, body[i]->head, NEXT_INSN (body[i]->end)))
- return false;
+ for (i = 0; i < 2; i++)
+ {
+ op[i] = XEXP (test, i);
- return true;
+ if (CONSTANT_P (op[i]))
+ continue;
+
+ insn = iv_get_reaching_def (at, op[i]);
+ if (!iv_analyse (insn, op[i], &iv))
+ return NULL_RTX;
+ if (iv.step != const0_rtx
+ || iv.first_special)
+ return NULL_RTX;
+
+ op[i] = get_iv_value (&iv, const0_rtx);
+ }
+
+ mode = GET_MODE (op[0]);
+ if (mode == VOIDmode)
+ mode = GET_MODE (op[1]);
+ if (GET_MODE_CLASS (mode) == MODE_CC)
+ {
+ if (at != BB_END (bb))
+ return NULL_RTX;
+
+ *cinsn = BB_END (bb);
+ if (!rtx_equal_p (op[0], XEXP (test, 0))
+ || !rtx_equal_p (op[1], XEXP (test, 1)))
+ return NULL_RTX;
+
+ return test;
+ }
+
+ return canon_condition (gen_rtx_fmt_ee (GET_CODE (test), SImode,
+ op[0], op[1]));
}
/* Reverses CONDition; returns NULL if we cannot. */
-static rtx
-reversed_condition (cond)
- rtx cond;
+rtx
+reversed_condition (rtx cond)
{
enum rtx_code reversed;
reversed = reversed_comparison_code (cond, NULL);
number of unswitchings done; do not allow it to grow too much, it is too
easy to create example on that the code would grow exponentially. */
static void
-unswitch_single_loop (loops, loop, cond_checked, num)
- struct loops *loops;
- struct loop *loop;
- rtx cond_checked;
- int num;
+unswitch_single_loop (struct loops *loops, struct loop *loop,
+ rtx cond_checked, int num)
{
- basic_block *bbs, bb;
+ basic_block *bbs;
struct loop *nloop;
unsigned i;
- int true_first;
- rtx cond, rcond, conds, rconds, acond, split_before;
- int always_true;
- int always_false;
+ rtx cond, rcond, conds, rconds, acond, cinsn = NULL_RTX;
int repeat;
edge e;
fprintf (rtl_dump_file, ";; Not unswitching, not innermost loop\n");
return;
}
-
+
/* We must be able to duplicate loop body. */
if (!can_duplicate_loop_p (loop))
{
fprintf (rtl_dump_file, ";; Not unswitching, loop too big\n");
return;
}
-
+
/* Do not unswitch in cold areas. */
if (!maybe_hot_bb_p (loop->header))
{
fprintf (rtl_dump_file, ";; Not unswitching, not hot area\n");
return;
}
-
+
/* Nor if the loop usually does not roll. */
if (expected_loop_iterations (loop) < 1)
{
do
{
repeat = 0;
-
+
/* Find a bb to unswitch on. */
bbs = get_loop_body (loop);
+ iv_analysis_loop_init (loop);
for (i = 0; i < loop->num_nodes; i++)
- if (may_unswitch_on_p (loops, bbs[i], loop, bbs))
+ if ((cond = may_unswitch_on (bbs[i], loop, &cinsn)))
break;
if (i == loop->num_nodes)
return;
}
- if (!(cond = get_condition (bbs[i]->end, &split_before)))
- abort ();
rcond = reversed_condition (cond);
-
+ if (rcond)
+ rcond = canon_condition (rcond);
+
/* Check whether the result can be predicted. */
- always_true = 0;
- always_false = 0;
for (acond = cond_checked; acond; acond = XEXP (acond, 1))
- {
- if (rtx_equal_p (cond, XEXP (acond, 0)))
- {
- always_true = 1;
- break;
- }
- if (rtx_equal_p (rcond, XEXP (acond, 0)))
- {
- always_false = 1;
- break;
- }
- }
+ simplify_using_condition (XEXP (acond, 0), &cond, NULL);
- if (always_true)
+ if (cond == const_true_rtx)
{
/* Remove false path. */
- for (e = bbs[i]->succ; !(e->flags & EDGE_FALLTHRU); e = e->succ_next);
+ e = FALLTHRU_EDGE (bbs[i]);
remove_path (loops, e);
free (bbs);
repeat = 1;
}
- else if (always_false)
+ else if (cond == const0_rtx)
{
/* Remove true path. */
- for (e = bbs[i]->succ; e->flags & EDGE_FALLTHRU; e = e->succ_next);
+ e = BRANCH_EDGE (bbs[i]);
remove_path (loops, e);
free (bbs);
repeat = 1;
}
} while (repeat);
-
+
/* We found the condition we can unswitch on. */
conds = alloc_EXPR_LIST (0, cond, cond_checked);
if (rcond)
else
rconds = cond_checked;
- /* Separate condition in a single basic block. */
- bb = split_loop_bb (loops, bbs[i], PREV_INSN (split_before))->dest;
- free (bbs);
- true_first = !(bb->succ->flags & EDGE_FALLTHRU);
if (rtl_dump_file)
fprintf (rtl_dump_file, ";; Unswitching loop\n");
/* Unswitch the loop on this condition. */
- nloop = unswitch_loop (loops, loop, bb);
+ nloop = unswitch_loop (loops, loop, bbs[i], cond, cinsn);
if (!nloop)
abort ();
/* Invoke itself on modified loops. */
- unswitch_single_loop (loops, nloop, true_first ? conds : rconds, num + 1);
- unswitch_single_loop (loops, loop, true_first ? rconds : conds, num + 1);
+ unswitch_single_loop (loops, nloop, rconds, num + 1);
+ unswitch_single_loop (loops, loop, conds, num + 1);
free_EXPR_LIST_node (conds);
if (rcond)
/* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support
unswitching of innermost loops. UNSWITCH_ON must be executed in every
- iteration, i.e. it must dominate LOOP latch, and should only contain code
- for the condition we unswitch on. Returns NULL if impossible, new
- loop otherwise. */
+ iteration, i.e. it must dominate LOOP latch. COND is the condition
+ determining which loop is entered. Returns NULL if impossible, new loop
+ otherwise. The new loop is entered if COND is true. If CINSN is not
+ NULL, it is the insn in that COND is compared. */
+
static struct loop *
-unswitch_loop (loops, loop, unswitch_on)
- struct loops *loops;
- struct loop *loop;
- basic_block unswitch_on;
+unswitch_loop (struct loops *loops, struct loop *loop, basic_block unswitch_on,
+ rtx cond, rtx cinsn)
{
- edge entry, latch_edge;
+ edge entry, latch_edge, true_edge, false_edge, e;
basic_block switch_bb, unswitch_on_alt, src;
struct loop *nloop;
sbitmap zero_bitmap;
- int irred_flag;
+ int irred_flag, prob;
+ rtx seq;
/* Some sanity checking. */
if (!flow_bb_inside_loop_p (loop, unswitch_on))
if (!unswitch_on->succ || !unswitch_on->succ->succ_next ||
unswitch_on->succ->succ_next->succ_next)
abort ();
- if (!just_once_each_iteration_p (loops, loop, unswitch_on))
+ if (!just_once_each_iteration_p (loop, unswitch_on))
abort ();
if (loop->inner)
abort ();
abort ();
if (!flow_bb_inside_loop_p (loop, unswitch_on->succ->succ_next->dest))
abort ();
-
- /* Will we be able to perform redirection? */
- if (!any_condjump_p (unswitch_on->end))
- return NULL;
- if (!cfg_layout_can_duplicate_bb_p (unswitch_on))
- return NULL;
entry = loop_preheader_edge (loop);
-
+
/* Make a copy. */
src = entry->src;
irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP;
entry->flags |= irred_flag;
/* Record the block with condition we unswitch on. */
- unswitch_on_alt = RBI (unswitch_on)->copy;
+ unswitch_on_alt = unswitch_on->rbi->copy;
+ true_edge = BRANCH_EDGE (unswitch_on_alt);
+ false_edge = FALLTHRU_EDGE (unswitch_on);
+ latch_edge = loop->latch->rbi->copy->succ;
+
+ /* Create a block with the condition. */
+ prob = true_edge->probability;
+ switch_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
+ seq = compare_and_jump_seq (XEXP (cond, 0), XEXP (cond, 1), GET_CODE (cond),
+ block_label (true_edge->dest),
+ prob, cinsn);
+ emit_insn_after (seq, BB_END (switch_bb));
+ e = make_edge (switch_bb, true_edge->dest, 0);
+ e->probability = prob;
+ e->count = latch_edge->count * prob / REG_BR_PROB_BASE;
+ e = make_edge (switch_bb, FALLTHRU_EDGE (unswitch_on)->dest, EDGE_FALLTHRU);
+ e->probability = false_edge->probability;
+ e->count = latch_edge->count * (false_edge->probability) / REG_BR_PROB_BASE;
- /* Make a copy of the block containing the condition; we will use
- it as switch to decide which loop we want to use. */
- switch_bb = cfg_layout_duplicate_bb (unswitch_on, NULL);
if (irred_flag)
{
switch_bb->flags |= BB_IRREDUCIBLE_LOOP;
switch_bb->succ->flags &= ~EDGE_IRREDUCIBLE_LOOP;
switch_bb->succ->succ_next->flags &= ~EDGE_IRREDUCIBLE_LOOP;
}
- add_to_dominance_info (loops->cfg.dom, switch_bb);
- RBI (unswitch_on)->copy = unswitch_on_alt;
/* Loopify from the copy of LOOP body, constructing the new loop. */
- for (latch_edge = RBI (loop->latch)->copy->succ;
- latch_edge->dest != loop->header;
- latch_edge = latch_edge->succ_next);
nloop = loopify (loops, latch_edge,
- RBI (loop->header)->copy->pred, switch_bb);
+ loop->header->rbi->copy->pred, switch_bb);
- /* Remove branches that are now unreachable in new loops. We rely on the
- fact that cfg_layout_duplicate_bb reverses list of edges. */
- remove_path (loops, unswitch_on->succ);
- remove_path (loops, unswitch_on_alt->succ);
+ /* Remove branches that are now unreachable in new loops. */
+ remove_path (loops, true_edge);
+ remove_path (loops, false_edge);
/* One of created loops do not have to be subloop of the outer loop now,
- so fix its placement in loop datastructure. */
+ so fix its placement in loop data structure. */
fix_loop_placement (loop);
fix_loop_placement (nloop);
+ /* Preserve the simple loop preheaders. */
+ loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX);
+ loop_split_edge_with (loop_preheader_edge (nloop), NULL_RTX);
+
return nloop;
}