/* Conditional compare related functions
Copyright (C) 2014-2016 Free Software Foundation, Inc.
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3. If not see
. */
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "target.h"
#include "rtl.h"
#include "tree.h"
#include "gimple.h"
#include "tm_p.h"
#include "ssa.h"
#include "expmed.h"
#include "optabs.h"
#include "emit-rtl.h"
#include "stor-layout.h"
#include "tree-ssa-live.h"
#include "tree-outof-ssa.h"
#include "cfgexpand.h"
#include "ccmp.h"
#include "predict.h"
/* The following functions expand conditional compare (CCMP) instructions.
Here is a short description about the over all algorithm:
* ccmp_candidate_p is used to identify the CCMP candidate
* expand_ccmp_expr is the main entry, which calls expand_ccmp_expr_1
to expand CCMP.
* expand_ccmp_expr_1 uses a recursive algorithm to expand CCMP.
It calls two target hooks gen_ccmp_first and gen_ccmp_next to generate
CCMP instructions.
- gen_ccmp_first expands the first compare in CCMP.
- gen_ccmp_next expands the following compares.
Both hooks return a comparison with the CC register that is equivalent
to the value of the gimple comparison. This is used by the next CCMP
and in the final conditional store.
* We use cstorecc4 pattern to convert the CCmode intermediate to
the integer mode result that expand_normal is expecting.
Since the operands of the later compares might clobber CC reg, we do not
emit the insns during expand. We keep the insn sequences in two seq
* prep_seq, which includes all the insns to prepare the operands.
* gen_seq, which includes all the compare and conditional compares.
If all checks OK in expand_ccmp_expr, it emits insns in prep_seq, then
insns in gen_seq. */
/* Check whether G is a potential conditional compare candidate. */
static bool
ccmp_candidate_p (gimple *g)
{
tree rhs = gimple_assign_rhs_to_tree (g);
tree lhs, op0, op1;
gimple *gs0, *gs1;
tree_code tcode, tcode0, tcode1;
tcode = TREE_CODE (rhs);
if (tcode != BIT_AND_EXPR && tcode != BIT_IOR_EXPR)
return false;
lhs = gimple_assign_lhs (g);
op0 = TREE_OPERAND (rhs, 0);
op1 = TREE_OPERAND (rhs, 1);
if ((TREE_CODE (op0) != SSA_NAME) || (TREE_CODE (op1) != SSA_NAME)
|| !has_single_use (lhs))
return false;
gs0 = get_gimple_for_ssa_name (op0);
gs1 = get_gimple_for_ssa_name (op1);
if (!gs0 || !gs1 || !is_gimple_assign (gs0) || !is_gimple_assign (gs1)
/* g, gs0 and gs1 must be in the same basic block, since current stage
is out-of-ssa. We can not guarantee the correctness when forwording
the gs0 and gs1 into g whithout DATAFLOW analysis. */
|| gimple_bb (gs0) != gimple_bb (gs1)
|| gimple_bb (gs0) != gimple_bb (g))
return false;
tcode0 = gimple_assign_rhs_code (gs0);
tcode1 = gimple_assign_rhs_code (gs1);
if (TREE_CODE_CLASS (tcode0) == tcc_comparison
&& TREE_CODE_CLASS (tcode1) == tcc_comparison)
return true;
if (TREE_CODE_CLASS (tcode0) == tcc_comparison
&& ccmp_candidate_p (gs1))
return true;
else if (TREE_CODE_CLASS (tcode1) == tcc_comparison
&& ccmp_candidate_p (gs0))
return true;
/* We skip ccmp_candidate_p (gs1) && ccmp_candidate_p (gs0) since
there is no way to set the CC flag. */
return false;
}
/* PREV is a comparison with the CC register which represents the
result of the previous CMP or CCMP. The function expands the
next compare based on G which is ANDed/ORed with the previous
compare depending on CODE.
PREP_SEQ returns all insns to prepare opearands for compare.
GEN_SEQ returns all compare insns. */
static rtx
expand_ccmp_next (gimple *g, tree_code code, rtx prev,
rtx *prep_seq, rtx *gen_seq)
{
rtx_code rcode;
int unsignedp = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (g)));
gcc_assert (code == BIT_AND_EXPR || code == BIT_IOR_EXPR);
rcode = get_rtx_code (gimple_assign_rhs_code (g), unsignedp);
return targetm.gen_ccmp_next (prep_seq, gen_seq, prev, rcode,
gimple_assign_rhs1 (g),
gimple_assign_rhs2 (g),
get_rtx_code (code, 0));
}
/* Expand conditional compare gimple G. A typical CCMP sequence is like:
CC0 = CMP (a, b);
CC1 = CCMP (NE (CC0, 0), CMP (e, f));
...
CCn = CCMP (NE (CCn-1, 0), CMP (...));
hook gen_ccmp_first is used to expand the first compare.
hook gen_ccmp_next is used to expand the following CCMP.
PREP_SEQ returns all insns to prepare opearand.
GEN_SEQ returns all compare insns. */
static rtx
expand_ccmp_expr_1 (gimple *g, rtx *prep_seq, rtx *gen_seq)
{
rtx prep_seq_1, gen_seq_1;
rtx prep_seq_2, gen_seq_2;
tree exp = gimple_assign_rhs_to_tree (g);
tree_code code = TREE_CODE (exp);
gimple *gs0 = get_gimple_for_ssa_name (TREE_OPERAND (exp, 0));
gimple *gs1 = get_gimple_for_ssa_name (TREE_OPERAND (exp, 1));
rtx tmp;
tree_code code0 = gimple_assign_rhs_code (gs0);
tree_code code1 = gimple_assign_rhs_code (gs1);
gcc_assert (code == BIT_AND_EXPR || code == BIT_IOR_EXPR);
gcc_assert (gs0 && gs1 && is_gimple_assign (gs0) && is_gimple_assign (gs1));
if (TREE_CODE_CLASS (code0) == tcc_comparison)
{
if (TREE_CODE_CLASS (code1) == tcc_comparison)
{
int unsignedp0, unsignedp1;
rtx_code rcode0, rcode1;
int speed_p = optimize_insn_for_speed_p ();
rtx tmp2, ret = NULL_RTX, ret2 = NULL_RTX;
unsigned cost1 = MAX_COST;
unsigned cost2 = MAX_COST;
unsignedp0 = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (gs0)));
unsignedp1 = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (gs1)));
rcode0 = get_rtx_code (code0, unsignedp0);
rcode1 = get_rtx_code (code1, unsignedp1);
tmp = targetm.gen_ccmp_first (&prep_seq_1, &gen_seq_1, rcode0,
gimple_assign_rhs1 (gs0),
gimple_assign_rhs2 (gs0));
tmp2 = targetm.gen_ccmp_first (&prep_seq_2, &gen_seq_2, rcode1,
gimple_assign_rhs1 (gs1),
gimple_assign_rhs2 (gs1));
if (!tmp && !tmp2)
return NULL_RTX;
if (tmp != NULL)
{
ret = expand_ccmp_next (gs1, code, tmp, &prep_seq_1, &gen_seq_1);
cost1 = seq_cost (safe_as_a (prep_seq_1), speed_p);
cost1 += seq_cost (safe_as_a (gen_seq_1), speed_p);
}
if (tmp2 != NULL)
{
ret2 = expand_ccmp_next (gs0, code, tmp2, &prep_seq_2,
&gen_seq_2);
cost2 = seq_cost (safe_as_a (prep_seq_2), speed_p);
cost2 += seq_cost (safe_as_a (gen_seq_2), speed_p);
}
if (cost2 < cost1)
{
*prep_seq = prep_seq_2;
*gen_seq = gen_seq_2;
return ret2;
}
*prep_seq = prep_seq_1;
*gen_seq = gen_seq_1;
return ret;
}
else
{
tmp = expand_ccmp_expr_1 (gs1, prep_seq, gen_seq);
if (!tmp)
return NULL_RTX;
return expand_ccmp_next (gs0, code, tmp, prep_seq, gen_seq);
}
}
else
{
gcc_assert (gimple_assign_rhs_code (gs0) == BIT_AND_EXPR
|| gimple_assign_rhs_code (gs0) == BIT_IOR_EXPR);
if (TREE_CODE_CLASS (gimple_assign_rhs_code (gs1)) == tcc_comparison)
{
tmp = expand_ccmp_expr_1 (gs0, prep_seq, gen_seq);
if (!tmp)
return NULL_RTX;
return expand_ccmp_next (gs1, code, tmp, prep_seq, gen_seq);
}
else
{
gcc_assert (gimple_assign_rhs_code (gs1) == BIT_AND_EXPR
|| gimple_assign_rhs_code (gs1) == BIT_IOR_EXPR);
}
}
return NULL_RTX;
}
/* Main entry to expand conditional compare statement G.
Return NULL_RTX if G is not a legal candidate or expand fail.
Otherwise return the target. */
rtx
expand_ccmp_expr (gimple *g)
{
rtx_insn *last;
rtx tmp;
rtx prep_seq, gen_seq;
prep_seq = gen_seq = NULL_RTX;
if (!ccmp_candidate_p (g))
return NULL_RTX;
last = get_last_insn ();
tmp = expand_ccmp_expr_1 (g, &prep_seq, &gen_seq);
if (tmp)
{
insn_code icode;
machine_mode cc_mode = CCmode;
tree lhs = gimple_assign_lhs (g);
rtx_code cmp_code = GET_CODE (tmp);
#ifdef SELECT_CC_MODE
cc_mode = SELECT_CC_MODE (cmp_code, XEXP (tmp, 0), const0_rtx);
#endif
icode = optab_handler (cstore_optab, cc_mode);
if (icode != CODE_FOR_nothing)
{
machine_mode mode = TYPE_MODE (TREE_TYPE (lhs));
rtx target = gen_reg_rtx (mode);
emit_insn (prep_seq);
emit_insn (gen_seq);
tmp = emit_cstore (target, icode, cmp_code, cc_mode, cc_mode,
0, XEXP (tmp, 0), const0_rtx, 1, mode);
if (tmp)
return tmp;
}
}
/* Clean up. */
delete_insns_since (last);
return NULL_RTX;
}