[PATCH] Replace conditional_replacement with match and simplify

Andrew Pinski pinskia@gmail.com
Wed Jun 2 09:34:48 GMT 2021


On Wed, Jun 2, 2021 at 2:12 AM Andrew Pinski <pinskia@gmail.com> wrote:
>
> On Wed, Jun 2, 2021 at 1:37 AM Christophe Lyon via Gcc-patches
> <gcc-patches@gcc.gnu.org> wrote:
> >
> > On Tue, 1 Jun 2021 at 08:06, apinski--- via Gcc-patches
> > <gcc-patches@gcc.gnu.org> wrote:
> > >
> > > From: Andrew Pinski <apinski@marvell.com>
> > >
> > > This is the first of series of patches to simplify phi-opt
> > > to use match and simplify in many cases.  This simplification
> > > will more things to optimize.
> > >
> > > This is what Richard requested in
> > > https://gcc.gnu.org/pipermail/gcc-patches/2021-May/571197.html
> > > and I think it is the right thing to do too.
> > >
> > > OK? Bootstrapped and tested on x86_64-linux-gnu with no regressions.
> > >
> > > gcc/ChangeLog:
> > >
> > >         * tree-ssa-phiopt.c (match_simplify_replacement):
> > >         New function.
> > >         (tree_ssa_phiopt_worker): Use match_simplify_replacement.
> > >         (two_value_replacement): Change the comment about
> > >         conditional_replacement.
> > >         (conditional_replacement): Delete.
> >
> > Hi Andrew,
> >
> > This patch caused a regression on aarch64:
> > FAIL: gcc.target/aarch64/subs_compare_2.c scan-assembler-not
> > cmp\\tw[0-9]+, w[0-9]+
> > FAIL: gcc.target/aarch64/subs_compare_2.c scan-assembler-times
> > subs\\tw[0-9]+, w[0-9]+, [#]?4 1
> >
> > Can you check?
>
> Yes because it simplified the code to being on the gimple level to:
>   _5 = MIN_EXPR <a_2(D), 4>;
>   _6 = _5 + -4;
>
> Which is the same as:
> int f(int a)
> {
>   if (a >= 4) a = 4;
>   return a - 4;
> }
> Which is correct also.

I filed this as PR 100874 with two extra testcases which show the
problem before hand even.

Thanks,
Andrew

>
> So the back-end needs to be improved slightly.
> It could match:
> (set (reg/i:SI 0 x0)
>     (plus:SI (smin:SI (reg/v:SI 94 [ a ])
>             (const_int 4 [0x4]))
>         (const_int -4 [0xfffffffffffffffc])))
>
> Which then splits to:
> (insn:TI 51 41 18 (parallel [
>             (set (reg:CC 66 cc)
>                 (compare:CC (reg/v:SI 0 x0 [orig:93 a ] [93])
>                     (const_int 4 [0x4])))
>             (set (reg:SI 0 x0 [95])
>                 (plus:SI (reg/v:SI 0 x0 [orig:93 a ] [93])
>                     (const_int -4 [0xfffffffffffffffc])))
>         ]) "t.c":9:7 283 {subsi3_compare1_imm}
>      (nil))
> (insn:TI 18 51 19 (set (reg/i:SI 0 x0)
>         (if_then_else:SI (lt (reg:CC 66 cc)
>                 (const_int 0 [0]))
>             (reg:SI 0 x0 [95])
>             (const_int 0 [0]))) "t.c":12:1 455 {*cmovsi_insn}
>      (expr_list:REG_DEAD (reg:CC 66 cc)
>         (nil)))
>
> We could also change the testcase return a different value such as doing:
> int
> foo (int a, int b)
> {
>   int x = a - 4;
>   if (a < 4)
>     return x;
>   else
>     return b;
> }
> Such that foo does not do a MIN :).
>
> Thanks,
> Andrew Pinski
>
> >
> > Thanks
> >
> > Christophe
> >
> > > ---
> > >  gcc/tree-ssa-phiopt.c | 144 ++++++++++++------------------------------
> > >  1 file changed, 39 insertions(+), 105 deletions(-)
> > >
> > > diff --git a/gcc/tree-ssa-phiopt.c b/gcc/tree-ssa-phiopt.c
> > > index e3bd18023a0..969b868397e 100644
> > > --- a/gcc/tree-ssa-phiopt.c
> > > +++ b/gcc/tree-ssa-phiopt.c
> > > @@ -53,8 +53,8 @@ along with GCC; see the file COPYING3.  If not see
> > >  static unsigned int tree_ssa_phiopt_worker (bool, bool, bool);
> > >  static bool two_value_replacement (basic_block, basic_block, edge, gphi *,
> > >                                    tree, tree);
> > > -static bool conditional_replacement (basic_block, basic_block,
> > > -                                    edge, edge, gphi *, tree, tree);
> > > +static bool match_simplify_replacement (basic_block, basic_block,
> > > +                                       edge, edge, gphi *, tree, tree);
> > >  static gphi *factor_out_conditional_conversion (edge, edge, gphi *, tree, tree,
> > >                                                 gimple *);
> > >  static int value_replacement (basic_block, basic_block,
> > > @@ -347,8 +347,8 @@ tree_ssa_phiopt_worker (bool do_store_elim, bool do_hoist_loads, bool early_p)
> > >           if (!early_p && two_value_replacement (bb, bb1, e2, phi, arg0, arg1))
> > >             cfgchanged = true;
> > >           else if (!early_p
> > > -                  && conditional_replacement (bb, bb1, e1, e2, phi,
> > > -                                              arg0, arg1))
> > > +                  && match_simplify_replacement (bb, bb1, e1, e2, phi,
> > > +                                                 arg0, arg1))
> > >             cfgchanged = true;
> > >           else if (abs_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
> > >             cfgchanged = true;
> > > @@ -675,7 +675,7 @@ two_value_replacement (basic_block cond_bb, basic_block middle_bb,
> > >      }
> > >
> > >    /* Defer boolean x ? 0 : {1,-1} or x ? {1,-1} : 0 to
> > > -     conditional_replacement.  */
> > > +     match_simplify_replacement.  */
> > >    if (TREE_CODE (TREE_TYPE (lhs)) == BOOLEAN_TYPE
> > >        && (integer_zerop (arg0)
> > >           || integer_zerop (arg1)
> > > @@ -784,137 +784,71 @@ two_value_replacement (basic_block cond_bb, basic_block middle_bb,
> > >    return true;
> > >  }
> > >
> > > -/*  The function conditional_replacement does the main work of doing the
> > > -    conditional replacement.  Return true if the replacement is done.
> > > +/*  The function match_simplify_replacement does the main work of doing the
> > > +    replacement using match and simplify.  Return true if the replacement is done.
> > >      Otherwise return false.
> > >      BB is the basic block where the replacement is going to be done on.  ARG0
> > >      is argument 0 from PHI.  Likewise for ARG1.  */
> > >
> > >  static bool
> > > -conditional_replacement (basic_block cond_bb, basic_block middle_bb,
> > > -                        edge e0, edge e1, gphi *phi,
> > > -                        tree arg0, tree arg1)
> > > +match_simplify_replacement (basic_block cond_bb, basic_block middle_bb,
> > > +                           edge e0, edge e1, gphi *phi,
> > > +                           tree arg0, tree arg1)
> > >  {
> > > -  tree result;
> > >    gimple *stmt;
> > > -  gassign *new_stmt;
> > >    tree cond;
> > >    gimple_stmt_iterator gsi;
> > >    edge true_edge, false_edge;
> > > -  tree new_var, new_var2;
> > > -  bool neg = false;
> > > -  int shift = 0;
> > > -  tree nonzero_arg;
> > > -
> > > -  /* FIXME: Gimplification of complex type is too hard for now.  */
> > > -  /* We aren't prepared to handle vectors either (and it is a question
> > > -     if it would be worthwhile anyway).  */
> > > -  if (!(INTEGRAL_TYPE_P (TREE_TYPE (arg0))
> > > -       || POINTER_TYPE_P (TREE_TYPE (arg0)))
> > > -      || !(INTEGRAL_TYPE_P (TREE_TYPE (arg1))
> > > -          || POINTER_TYPE_P (TREE_TYPE (arg1))))
> > > -    return false;
> > > +  gimple_seq seq = NULL;
> > > +  tree result;
> > >
> > > -  /* The PHI arguments have the constants 0 and 1, or 0 and -1 or
> > > -     0 and (1 << cst), then convert it to the conditional.  */
> > > -  if (integer_zerop (arg0))
> > > -    nonzero_arg = arg1;
> > > -  else if (integer_zerop (arg1))
> > > -    nonzero_arg = arg0;
> > > -  else
> > > -    return false;
> > > -  if (integer_pow2p (nonzero_arg))
> > > -    {
> > > -      shift = tree_log2 (nonzero_arg);
> > > -      if (shift && POINTER_TYPE_P (TREE_TYPE (nonzero_arg)))
> > > -       return false;
> > > -    }
> > > -  else if (integer_all_onesp (nonzero_arg))
> > > -    neg = true;
> > > -  else
> > > +  if (!empty_block_p (middle_bb))
> > >      return false;
> > >
> > > -  if (!empty_block_p (middle_bb))
> > > +  /* Special case A ? B : B as this will always simplify to B. */
> > > +  if (operand_equal_for_phi_arg_p (arg0, arg1))
> > >      return false;
> > >
> > > -  /* At this point we know we have a GIMPLE_COND with two successors.
> > > +    /* At this point we know we have a GIMPLE_COND with two successors.
> > >       One successor is BB, the other successor is an empty block which
> > >       falls through into BB.
> > >
> > > -     There is a single PHI node at the join point (BB) and its arguments
> > > -     are constants (0, 1) or (0, -1) or (0, (1 << shift)).
> > > -
> > > -     So, given the condition COND, and the two PHI arguments, we can
> > > -     rewrite this PHI into non-branching code:
> > > -
> > > -       dest = (COND) or dest = COND' or dest = (COND) << shift
> > > +     There is a single PHI node at the join point (BB).
> > >
> > > -     We use the condition as-is if the argument associated with the
> > > -     true edge has the value one or the argument associated with the
> > > -     false edge as the value zero.  Note that those conditions are not
> > > -     the same since only one of the outgoing edges from the GIMPLE_COND
> > > -     will directly reach BB and thus be associated with an argument.  */
> > > +     So, given the condition COND, and the two PHI arguments, match and simplify
> > > +     can happen on (COND) ? arg0 : arg1. */
> > >
> > >    stmt = last_stmt (cond_bb);
> > > -  result = PHI_RESULT (phi);
> > >
> > >    /* To handle special cases like floating point comparison, it is easier and
> > >       less error-prone to build a tree and gimplify it on the fly though it is
> > > -     less efficient.  */
> > > -  cond = fold_build2_loc (gimple_location (stmt),
> > > -                         gimple_cond_code (stmt), boolean_type_node,
> > > -                         gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
> > > +     less efficient.
> > > +     Don't use fold_build2 here as that might create (bool)a instead of just
> > > +     "a != 0".  */
> > > +  cond = build2_loc (gimple_location (stmt),
> > > +                    gimple_cond_code (stmt), boolean_type_node,
> > > +                    gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
> > >
> > >    /* We need to know which is the true edge and which is the false
> > >       edge so that we know when to invert the condition below.  */
> > >    extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
> > > -  if ((e0 == true_edge && integer_zerop (arg0))
> > > -      || (e0 == false_edge && !integer_zerop (arg0))
> > > -      || (e1 == true_edge && integer_zerop (arg1))
> > > -      || (e1 == false_edge && !integer_zerop (arg1)))
> > > -    cond = fold_build1_loc (gimple_location (stmt),
> > > -                            TRUTH_NOT_EXPR, TREE_TYPE (cond), cond);
> > > -
> > > -  if (neg)
> > > -    {
> > > -      cond = fold_convert_loc (gimple_location (stmt),
> > > -                               TREE_TYPE (result), cond);
> > > -      cond = fold_build1_loc (gimple_location (stmt),
> > > -                              NEGATE_EXPR, TREE_TYPE (cond), cond);
> > > -    }
> > > -  else if (shift)
> > > -    {
> > > -      cond = fold_convert_loc (gimple_location (stmt),
> > > -                              TREE_TYPE (result), cond);
> > > -      cond = fold_build2_loc (gimple_location (stmt),
> > > -                             LSHIFT_EXPR, TREE_TYPE (cond), cond,
> > > -                             build_int_cst (integer_type_node, shift));
> > > -    }
> > > -
> > > -  /* Insert our new statements at the end of conditional block before the
> > > -     COND_STMT.  */
> > > -  gsi = gsi_for_stmt (stmt);
> > > -  new_var = force_gimple_operand_gsi (&gsi, cond, true, NULL, true,
> > > -                                     GSI_SAME_STMT);
> > > +  if (e1 == true_edge || e0 == false_edge)
> > > +    std::swap (arg0, arg1);
> > >
> > > -  if (!useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (new_var)))
> > > -    {
> > > -      location_t locus_0, locus_1;
> > > +  tree type = TREE_TYPE (gimple_phi_result (phi));
> > > +  result = gimple_simplify (COND_EXPR, type,
> > > +                           cond,
> > > +                           arg0, arg1,
> > > +                           &seq, NULL);
> > > +  if (!result)
> > > +    return false;
> > >
> > > -      new_var2 = make_ssa_name (TREE_TYPE (result));
> > > -      new_stmt = gimple_build_assign (new_var2, CONVERT_EXPR, new_var);
> > > -      gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
> > > -      new_var = new_var2;
> > > +  gsi = gsi_last_bb (cond_bb);
> > >
> > > -      /* Set the locus to the first argument, unless is doesn't have one.  */
> > > -      locus_0 = gimple_phi_arg_location (phi, 0);
> > > -      locus_1 = gimple_phi_arg_location (phi, 1);
> > > -      if (locus_0 == UNKNOWN_LOCATION)
> > > -        locus_0 = locus_1;
> > > -      gimple_set_location (new_stmt, locus_0);
> > > -    }
> > > +  if (seq)
> > > +    gsi_insert_seq_before (&gsi, seq, GSI_SAME_STMT);
> > >
> > > -  replace_phi_edge_with_variable (cond_bb, e1, phi, new_var);
> > > +  replace_phi_edge_with_variable (cond_bb, e1, phi, result);
> > >
> > >    /* Note that we optimized this PHI.  */
> > >    return true;
> > > @@ -3627,7 +3561,7 @@ gate_hoist_loads (void)
> > >     Conditional Replacement
> > >     -----------------------
> > >
> > > -   This transformation, implemented in conditional_replacement,
> > > +   This transformation, implemented in match_simplify_replacement,
> > >     replaces
> > >
> > >       bb0:
> > > --
> > > 2.17.1
> > >


More information about the Gcc-patches mailing list