#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "rtl.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "cfgloop.h"
#include "cfglayout.h"
#include "params.h"
#include "output.h"
#include "expr.h"
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 *);
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)
{
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;
}
void
unswitch_loops (struct loops *loops)
{
int i, num;
struct loop *loop;
num = loops->num;
for (i = 1; i < num; i++)
{
loop = loops->parray[i];
if (!loop)
continue;
if (loop->inner)
continue;
unswitch_single_loop (loops, loop, NULL_RTX, 0);
#ifdef ENABLE_CHECKING
verify_dominators (CDI_DOMINATORS);
verify_loop_structure (loops);
#endif
}
iv_analysis_done ();
}
static rtx
may_unswitch_on (basic_block bb, struct loop *loop, rtx *cinsn)
{
rtx test, at, insn, op[2], stest;
struct rtx_iv iv;
unsigned i;
enum machine_mode mode;
if (EDGE_COUNT (bb->succs) != 2)
return NULL_RTX;
if (!any_condjump_p (BB_END (bb)))
return NULL_RTX;
if (!flow_bb_inside_loop_p (loop, EDGE_SUCC (bb, 0)->dest)
|| !flow_bb_inside_loop_p (loop, EDGE_SUCC (bb, 1)->dest))
return NULL_RTX;
if (!just_once_each_iteration_p (loop, bb))
return NULL_RTX;
test = get_condition (BB_END (bb), &at, true, false);
if (!test)
return NULL_RTX;
for (i = 0; i < 2; i++)
{
op[i] = XEXP (test, i);
if (CONSTANT_P (op[i]))
continue;
insn = iv_get_reaching_def (at, op[i]);
if (!iv_analyze (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;
}
stest = simplify_gen_relational (GET_CODE (test), SImode,
mode, op[0], op[1]);
if (stest == const0_rtx
|| stest == const_true_rtx)
return stest;
return canon_condition (gen_rtx_fmt_ee (GET_CODE (test), SImode,
op[0], op[1]));
}
rtx
reversed_condition (rtx cond)
{
enum rtx_code reversed;
reversed = reversed_comparison_code (cond, NULL);
if (reversed == UNKNOWN)
return NULL_RTX;
else
return gen_rtx_fmt_ee (reversed,
GET_MODE (cond), XEXP (cond, 0),
XEXP (cond, 1));
}
static void
unswitch_single_loop (struct loops *loops, struct loop *loop,
rtx cond_checked, int num)
{
basic_block *bbs;
struct loop *nloop;
unsigned i;
rtx cond, rcond = NULL_RTX, conds, rconds, acond, cinsn = NULL_RTX;
int repeat;
edge e;
if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
{
if (dump_file)
fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
return;
}
if (loop->inner)
{
if (dump_file)
fprintf (dump_file, ";; Not unswitching, not innermost loop\n");
return;
}
if (!can_duplicate_loop_p (loop))
{
if (dump_file)
fprintf (dump_file, ";; Not unswitching, can't duplicate loop\n");
return;
}
if (num_loop_insns (loop) > PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS))
{
if (dump_file)
fprintf (dump_file, ";; Not unswitching, loop too big\n");
return;
}
if (!maybe_hot_bb_p (loop->header))
{
if (dump_file)
fprintf (dump_file, ";; Not unswitching, not hot area\n");
return;
}
if (expected_loop_iterations (loop) < 1)
{
if (dump_file)
fprintf (dump_file, ";; Not unswitching, loop iterations < 1\n");
return;
}
do
{
repeat = 0;
bbs = get_loop_body (loop);
iv_analysis_loop_init (loop);
for (i = 0; i < loop->num_nodes; i++)
if ((cond = may_unswitch_on (bbs[i], loop, &cinsn)))
break;
if (i == loop->num_nodes)
{
free (bbs);
return;
}
if (cond != const0_rtx
&& cond != const_true_rtx)
{
rcond = reversed_condition (cond);
if (rcond)
rcond = canon_condition (rcond);
for (acond = cond_checked; acond; acond = XEXP (acond, 1))
simplify_using_condition (XEXP (acond, 0), &cond, NULL);
}
if (cond == const_true_rtx)
{
e = FALLTHRU_EDGE (bbs[i]);
remove_path (loops, e);
free (bbs);
repeat = 1;
}
else if (cond == const0_rtx)
{
e = BRANCH_EDGE (bbs[i]);
remove_path (loops, e);
free (bbs);
repeat = 1;
}
} while (repeat);
conds = alloc_EXPR_LIST (0, cond, cond_checked);
if (rcond)
rconds = alloc_EXPR_LIST (0, rcond, cond_checked);
else
rconds = cond_checked;
if (dump_file)
fprintf (dump_file, ";; Unswitching loop\n");
nloop = unswitch_loop (loops, loop, bbs[i], cond, cinsn);
if (!nloop)
abort ();
unswitch_single_loop (loops, nloop, rconds, num + 1);
unswitch_single_loop (loops, loop, conds, num + 1);
free_EXPR_LIST_node (conds);
if (rcond)
free_EXPR_LIST_node (rconds);
free (bbs);
}
static struct loop *
unswitch_loop (struct loops *loops, struct loop *loop, basic_block unswitch_on,
rtx cond, rtx cinsn)
{
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, prob;
rtx seq;
if (!flow_bb_inside_loop_p (loop, unswitch_on))
abort ();
if (EDGE_COUNT (unswitch_on->succs) != 2)
abort ();
if (!just_once_each_iteration_p (loop, unswitch_on))
abort ();
if (loop->inner)
abort ();
if (!flow_bb_inside_loop_p (loop, EDGE_SUCC (unswitch_on, 0)->dest))
abort ();
if (!flow_bb_inside_loop_p (loop, EDGE_SUCC (unswitch_on, 1)->dest))
abort ();
entry = loop_preheader_edge (loop);
src = entry->src;
irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP;
entry->flags &= ~EDGE_IRREDUCIBLE_LOOP;
zero_bitmap = sbitmap_alloc (2);
sbitmap_zero (zero_bitmap);
if (!duplicate_loop_to_header_edge (loop, entry, loops, 1,
zero_bitmap, NULL, NULL, NULL, 0))
return NULL;
free (zero_bitmap);
entry->flags |= irred_flag;
unswitch_on_alt = unswitch_on->rbi->copy;
true_edge = BRANCH_EDGE (unswitch_on_alt);
false_edge = FALLTHRU_EDGE (unswitch_on);
latch_edge = EDGE_SUCC (loop->latch->rbi->copy, 0);
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;
if (irred_flag)
{
switch_bb->flags |= BB_IRREDUCIBLE_LOOP;
EDGE_SUCC (switch_bb, 0)->flags |= EDGE_IRREDUCIBLE_LOOP;
EDGE_SUCC (switch_bb, 1)->flags |= EDGE_IRREDUCIBLE_LOOP;
}
else
{
switch_bb->flags &= ~BB_IRREDUCIBLE_LOOP;
EDGE_SUCC (switch_bb, 0)->flags &= ~EDGE_IRREDUCIBLE_LOOP;
EDGE_SUCC (switch_bb, 1)->flags &= ~EDGE_IRREDUCIBLE_LOOP;
}
nloop = loopify (loops, latch_edge,
EDGE_PRED (loop->header->rbi->copy, 0), switch_bb,
BRANCH_EDGE (switch_bb), FALLTHRU_EDGE (switch_bb), true);
remove_path (loops, true_edge);
remove_path (loops, false_edge);
fix_loop_placement (loop);
fix_loop_placement (nloop);
loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX);
loop_split_edge_with (loop_preheader_edge (nloop), NULL_RTX);
return nloop;
}