[4/10] expand ccmp

Hi,

This patch includes the main logic to expand ccmp instructions.

In the patch,
  * 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 gen_ccmp_first and gen_ccmp_next to generate CCMP instructions.

    During expanding, we must make sure that no instruction can clobber the
    CC reg except the compares.  So clobber_cc_p and check_clobber_cc are
    introduced to do the check.

  * If the final result is not used in a COND_EXPR (checked by function
    used_in_cond_stmt_p), it calls cstorecc4 pattern to store the CC to a
    general register.

Bootstrap and no make check regression on X86-64.

OK for trunk?

Thanks!
-Zhenqiang

ChangeLog:
2014-06-23  Zhenqiang Chen  <zhenqiang.chen@linaro.org>

        * ccmp.c (ccmp_candidate_p, used_in_cond_stmt_p, check_clobber_cc,
        clobber_cc_p, expand_ccmp_next, expand_ccmp_expr_1, expand_ccmp_expr):
        New functions to expand ccmp.
        * ccmp.h (expand_ccmp_expr): New prototype.
        * expr.c: #include "ccmp.h"
        (expand_expr_real_1): Try to expand ccmp.

              ops.op0 = gimple_assign_rhs1 (g);

On 23/06/14 07:59, Zhenqiang Chen wrote:
> Hi,
> 
> This patch includes the main logic to expand ccmp instructions.
> 
> In the patch,
>   * 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 gen_ccmp_first and gen_ccmp_next to generate CCMP instructions.
> 
>     During expanding, we must make sure that no instruction can clobber the
>     CC reg except the compares.  So clobber_cc_p and check_clobber_cc are
>     introduced to do the check.
> 
>   * If the final result is not used in a COND_EXPR (checked by function
>     used_in_cond_stmt_p), it calls cstorecc4 pattern to store the CC to a
>     general register.
> 
> Bootstrap and no make check regression on X86-64.
> 
> OK for trunk?
> 
> Thanks!
> -Zhenqiang
> 
> ChangeLog:
> 2014-06-23  Zhenqiang Chen  <zhenqiang.chen@linaro.org>
> 
>         * ccmp.c (ccmp_candidate_p, used_in_cond_stmt_p, check_clobber_cc,
>         clobber_cc_p, expand_ccmp_next, expand_ccmp_expr_1, expand_ccmp_expr):
>         New functions to expand ccmp.
>         * ccmp.h (expand_ccmp_expr): New prototype.
>         * expr.c: #include "ccmp.h"
>         (expand_expr_real_1): Try to expand ccmp.
> 
> diff --git a/gcc/ccmp.c b/gcc/ccmp.c
> index 665c2a5..97b3910 100644
> --- a/gcc/ccmp.c
> +++ b/gcc/ccmp.c
> @@ -47,6 +47,262 @@ along with GCC; see the file COPYING3.  If not see
>  #include "expmed.h"
>  #include "ccmp.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.
> +
> +       During expanding, we must make sure that no instruction can clobber the
> +       CC reg except the compares.  So clobber_cc_p and check_clobber_cc are
> +       introduced to do the check.
> +
> +     * If the final result is not used in a COND_EXPR (checked by function
> +       used_in_cond_stmt_p), it calls cstorecc4 pattern to store the CC to a
> +       general register.  */
> +
> +/* 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;
> +  enum 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;
> +
> +  if (!(INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (gs0)))
> +       || POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (gs0))))
> +      || !(INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (gs1)))
> +          || POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (gs1)))))
> +    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;
> +}
> +
> +/* Check whether EXP is used in a GIMPLE_COND statement or not.  */
> +static bool
> +used_in_cond_stmt_p (tree exp)
> +{
> +  bool expand_cond = false;
> +  imm_use_iterator ui;
> +  gimple use_stmt;
> +  FOR_EACH_IMM_USE_STMT (use_stmt, ui, exp)
> +    if (gimple_code (use_stmt) == GIMPLE_COND)
> +      {
> +       tree op1 = gimple_cond_rhs (use_stmt);
> +       if (integer_zerop (op1))
> +         expand_cond = true;
> +       BREAK_FROM_IMM_USE_STMT (ui);
> +      }
> +  return expand_cond;
> +}
> +
> +/* If SETTER clobber CC reg, set DATA to TRUE.  */
> +static void
> +check_clobber_cc (rtx reg, const_rtx setter, void *data)
> +{
> +  if (GET_CODE (setter) == CLOBBER && GET_MODE (reg) == CCmode)

You shouldn't assume that CC regs will only ever have mode CCmode.  It's
probably better to check for the mode class being MODE_CC.  Also, not
all architectures have a single CC register, so this test might be
unduly restrictive on targets with multiple predicate registers.


> +    *(bool *)data = true;
> +}
> +
> +/* Check whether INSN and all its NEXT_INSN clobber CC reg or not.  */
> +static bool
> +clobber_cc_p (rtx insn)
> +{
> +  bool clobber = false;
> +  for (; insn; insn = NEXT_INSN (insn))
> +    {
> +      note_stores (PATTERN (insn), check_clobber_cc, &clobber);
> +      if (clobber)
> +       return true;
> +    }
> +  return false;
> +}
> +
> +/* Help function to generate conditional compare.  PREV is the result of
> +   GEN_CCMP_FIRST or GEN_CCMP_NEXT.  G is the next compare.
> +   CODE is BIT_AND_EXPR or BIT_IOR_EXPR.  */
> +static rtx
> +expand_ccmp_next (rtx prev, gimple g, enum tree_code code)
> +{
> +  rtx op0, op1;
> +  int unsignedp = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (g)));
> +  enum rtx_code rcode = get_rtx_code (gimple_assign_rhs_code (g), unsignedp);
> +  rtx last = get_last_insn ();
> +
> +  expand_operands (gimple_assign_rhs1 (g),
> +                  gimple_assign_rhs2 (g),
> +                  NULL_RTX, &op0, &op1, EXPAND_NORMAL);
> +
> +  /* If any operand clobbers CC reg, we will give up.  */
> +  if (clobber_cc_p (NEXT_INSN (last)))
> +    return NULL_RTX;
> +

I suspect it might be better to just hoist any preparation operations
above the entire conditional compare sequence, so that by the time we
start the ccmp expansion we're dealing with operands that are in the
'natural' sizes for the machine (breaking up the conditional compare
sequence for what are almost side-effect operationssounds like a source
of potential bugs).  This would also ensure that the back-end can safely
re-order at least some comparison operations if this leads a workable
conditional compare sequence.

For example, in ARM

  (a < b && c <= d)

has to be computed as
  cmp	c, d
  cmple a, b
  ...lt true-op
  ...ge false-op

since the sequence
  cmp	a, b
  cmplt	c, d
  ...le true-op

would lead to the wrong behaviour when a == b and c == d.


> +  return targetm.gen_ccmp_next (prev, rcode, op0, op1, 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.  */
> +static rtx
> +expand_ccmp_expr_1 (gimple g)
> +{
> +  tree exp = gimple_assign_rhs_to_tree (g);
> +  enum 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;
> +  enum tree_code code0 = gimple_assign_rhs_code (gs0);
> +  enum 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;
> +         enum rtx_code rcode0, rcode1;
> +         rtx op0, op1, op2, op3, tmp;
> +
> +         unsignedp0 = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (gs0)));
> +         rcode0 = get_rtx_code (code0, unsignedp0);
> +         unsignedp1 = TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (gs1)));
> +         rcode1 = get_rtx_code (code1, unsignedp1);
> +
> +         expand_operands (gimple_assign_rhs1 (gs0),
> +                          gimple_assign_rhs2 (gs0),
> +                          NULL_RTX, &op0, &op1, EXPAND_NORMAL);
> +
> +         /* Since the operands of GS1 might clobber CC reg, we expand the
> +            operands of GS1 before GEN_CCMP_FIRST.  */
> +         expand_operands (gimple_assign_rhs1 (gs1),
> +                          gimple_assign_rhs2 (gs1),
> +                          NULL_RTX, &op2, &op3, EXPAND_NORMAL);
> +         tmp = targetm.gen_ccmp_first (rcode0, op0, op1);
> +         if (!tmp)
> +           return NULL_RTX;
> +
> +         return targetm.gen_ccmp_next (tmp, rcode1, op2, op3,
> +                                       get_rtx_code (code, 0));
> +       }
> +      else
> +       {
> +         gcc_assert (code1 == BIT_AND_EXPR || code1 == BIT_IOR_EXPR);
> +
> +         /* Note: We swap the order to make the recursive function work.  */
> +         tmp = expand_ccmp_expr_1 (gs1);
> +         if (tmp)
> +           return expand_ccmp_next (tmp, gs0, code);
> +       }
> +    }
> +  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);
> +         if (tmp)
> +           return expand_ccmp_next (tmp, gs1, code);
> +       }
> +      else
> +       {
> +         gcc_assert (gimple_assign_rhs_code (gs1) == BIT_AND_EXPR
> +                     || gimple_assign_rhs_code (gs1) == BIT_IOR_EXPR);
> +       }
> +    }
> +
> +  return NULL_RTX;
> +}
> +
> +rtx
> +expand_ccmp_expr (gimple g)
> +{
> +  rtx last, tmp;
> +
> +  if (!ccmp_candidate_p (g))
> +    return NULL_RTX;
> +
> +  last = get_last_insn ();
> +  tmp = expand_ccmp_expr_1 (g);
> +
> +  if (tmp)
> +    {
> +      enum insn_code icode;
> +      tree lhs = gimple_assign_lhs (g);
> +      /* TMP should be CC.  If it is used in a GIMPLE_COND, just return it.
> +        Note: Target needs to define "cbranchcc4".  */
> +      if (used_in_cond_stmt_p (lhs))
> +       return tmp;
> +
> +      /* If TMP is not used in a GIMPLE_COND, store it with a csctorecc4_optab.
> +        Note: Target needs to define "cstorecc4".  */
> +      icode = optab_handler (cstore_optab, CCmode);

I think you should be using SELECT_CC_MODE here.

> +      if (icode != CODE_FOR_nothing)
> +       {
> +         rtx target = gen_reg_rtx (word_mode);
> +         tmp = emit_cstore (target, icode, NE, CCmode, CCmode,
> +                            0, tmp, const0_rtx, 1, word_mode);
> +         if (tmp)
> +           return tmp;
> +       }
> +    }
> +
> +  /* Clean up.  */
> +  delete_insns_since (last);
> +  return NULL_RTX;
> +}
> +
>  bool
>  ccmp_insn_p (rtx object)
>  {
> diff --git a/gcc/ccmp.h b/gcc/ccmp.h
> index 7e139aa..56f3ac2 100644
> --- a/gcc/ccmp.h
> +++ b/gcc/ccmp.h
> @@ -20,6 +20,8 @@ along with GCC; see the file COPYING3.  If not see
>  #ifndef GCC_CCMP_H
>  #define GCC_CCMP_H
> 
> +extern rtx expand_ccmp_expr (gimple);
> +
>  extern bool ccmp_insn_p (rtx);
> 
>  #endif  /* GCC_CCMP_H  */
> diff --git a/gcc/expr.c b/gcc/expr.c
> index 04cf56e..4c31521 100644
> --- a/gcc/expr.c
> +++ b/gcc/expr.c
> @@ -68,6 +68,7 @@ along with GCC; see the file COPYING3.  If not see
>  #include "tree-ssa-address.h"
>  #include "cfgexpand.h"
>  #include "builtins.h"
> +#include "ccmp.h"
> 
>  #ifndef STACK_PUSH_CODE
>  #ifdef STACK_GROWS_DOWNWARD
> @@ -9379,6 +9380,15 @@ expand_expr_real_1 (tree exp, rtx target, enum
> machine_mode tmode,
>               /* Fallthru */
>             case GIMPLE_BINARY_RHS:
>               ops.op1 = gimple_assign_rhs2 (g);
> +
> +             /* Try to expand conditonal compare.  */
> +             if (targetm.gen_ccmp_first != NULL)
> +               {
> +                 gcc_checking_assert (targetm.gen_ccmp_next != NULL);
> +                 r = expand_ccmp_expr (g);
> +                 if (r)
> +                   break;
> +               }
>               /* Fallthru */
>             case GIMPLE_UNARY_RHS:
>               ops.op0 = gimple_assign_rhs1 (g);
>