[PATCH] Optimise sqrt reciprocal multiplications

Kyrill Tkachov kyrylo.tkachov@foss.arm.com
Wed Sep 5 11:38:00 GMT 2018


On 04/09/18 17:52, Kyrill Tkachov wrote:
 >
 > On 04/09/18 15:31, Richard Biener wrote:
 >> On Tue, 4 Sep 2018, Kyrill Tkachov wrote:
 >>> Hi Richard,
 >>>
 >>> On 31/08/18 12:07, Richard Biener wrote:
 >>>> On Thu, 30 Aug 2018, Kyrill Tkachov wrote:
 >>>>> Ping.
 >>>>>
 >>>>> https://gcc.gnu.org/ml/gcc-patches/2018-08/msg01496.html
 >>>>>
 >>>>> Thanks,
 >>>>> Kyrill
 >>>>>
 >>>>> On 23/08/18 18:09, Kyrill Tkachov wrote:
 >>>>>> Hi Richard,
 >>>>>>
 >>>>>> On 23/08/18 11:13, Richard Sandiford wrote:
 >>>>>>> Kyrill  Tkachov <kyrylo.tkachov@foss.arm.com> writes:
 >>>>>>>> Hi all,
 >>>>>>>>
 >>>>>>>> This patch aims to optimise sequences involving uses of 1.0 / sqrt (a)
 >>>>>>>> under -freciprocal-math and -funsafe-math-optimizations.
 >>>>>>>> In particular consider:
 >>>>>>>>
 >>>>>>>> x = 1.0 / sqrt (a);
 >>>>>>>> r1 = x * x;  // same as 1.0 / a
 >>>>>>>> r2 = a * x; // same as sqrt (a)
 >>>>>>>>
 >>>>>>>> If x, r1 and r2 are all used further on in the code, this can be
 >>>>>>>> transformed into:
 >>>>>>>> tmp1 = 1.0 / a
 >>>>>>>> tmp2 = sqrt (a)
 >>>>>>>> tmp3 = tmp1 * tmp2
 >>>>>>>> x = tmp3
 >>>>>>>> r1 = tmp1
 >>>>>>>> r2 = tmp2
 >>>>>>> Nice optimisation :-)  Someone who knows the pass better should review,
 >>>>>>> but:
 >>>>>> Thanks for the review.
 >>>>>>> There seems to be an implicit assumption that this is a win even
 >>>>>>> when the r1 and r2 assignments are only conditionally executed.
 >>>>>>> That's probably true, but it might be worth saying explicitly.
 >>>>>> I'll admit I had not considered that case.
 >>>>>> I think it won't make a difference in practice, as the really expensive
 >>>>>> operations here
 >>>>>> are the sqrt and the division and they are on the executed path in either
 >>>>>> case and them
 >>>>>> becoming independent should be a benefit of its own.
 >>>>>>>> +/* Return TRUE if USE_STMT is a multiplication of DEF by A.  */
 >>>>>>>> +
 >>>>>>>> +static inline bool
 >>>>>>>> +is_mult_by (gimple *use_stmt, tree def, tree a)
 >>>>>>>> +{
 >>>>>>>> +  if (gimple_code (use_stmt) == GIMPLE_ASSIGN
 >>>>>>>> +      && gimple_assign_rhs_code (use_stmt) == MULT_EXPR)
 >>>>>>>> +    {
 >>>>>>>> +      tree op0 = gimple_assign_rhs1 (use_stmt);
 >>>>>>>> +      tree op1 = gimple_assign_rhs2 (use_stmt);
 >>>>>>>> +
 >>>>>>>> +      return (op0 == def && op1 == a)
 >>>>>>>> +          || (op0 == a && op1 == def);
 >>>>>>>> +    }
 >>>>>>>> +  return 0;
 >>>>>>>> +}
 >>>>>>> Seems like is_square_of could now be a light-weight wrapper around this.
 >>>>>> Indeed, I've done the wrapping now.
 >>>>>>>> @@ -652,6 +669,180 @@ execute_cse_reciprocals_1 (gimple_stmt_iterator
 >>>>>>>> *def_gsi, tree def)
 >>>>>>>>      occ_head = NULL;
 >>>>>>>>    }
 >>>>>>>>    +/* Transform sequences like
 >>>>>>>> +   x = 1.0 / sqrt (a);
 >>>>>>>> +   r1 = x * x;
 >>>>>>>> +   r2 = a * x;
 >>>>>>>> +   into:
 >>>>>>>> +   tmp1 = 1.0 / a;
 >>>>>>>> +   tmp2 = sqrt (a);
 >>>>>>>> +   tmp3 = tmp1 * tmp2;
 >>>>>>>> +   x = tmp3;
 >>>>>>>> +   r1 = tmp1;
 >>>>>>>> +   r2 = tmp2;
 >>>>>>>> +   depending on the uses of x, r1, r2.  This removes one multiplication
 >>>>>>>> and
 >>>>>>>> +   allows the sqrt and division operations to execute in parallel.
 >>>>>>>> +   DEF_GSI is the gsi of the initial division by sqrt that defines
 >>>>>>>> +   DEF (x in the example abovs). */
 >>>>>>>> +
 >>>>>>>> +static void
 >>>>>>>> +optimize_recip_sqrt (gimple_stmt_iterator *def_gsi, tree def)
 >>>>>>>> +{
 >>>>>>>> +  use_operand_p use_p;
 >>>>>>>> +  imm_use_iterator use_iter;
 >>>>>>>> +  gimple *stmt = gsi_stmt (*def_gsi);
 >>>>>>>> +  tree x = def;
 >>>>>>>> +  tree orig_sqrt_ssa_name = gimple_assign_rhs2 (stmt);
 >>>>>>>> +  tree div_rhs1 = gimple_assign_rhs1 (stmt);
 >>>>>>>> +
 >>>>>>>> +  if (TREE_CODE (orig_sqrt_ssa_name) != SSA_NAME
 >>>>>>>> +      || TREE_CODE (div_rhs1) != REAL_CST
 >>>>>>>> +      || !real_equal (&TREE_REAL_CST (div_rhs1), &dconst1))
 >>>>>>>> +    return;
 >>>>>>>> +
 >>>>>>>> +  gimple *sqrt_stmt = SSA_NAME_DEF_STMT (orig_sqrt_ssa_name);
 >>>>>>>> +  if (!is_gimple_call (sqrt_stmt)
 >>>>>>>> +      || !gimple_call_lhs (sqrt_stmt))
 >>>>>>>> +    return;
 >>>>>>>> +
 >>>>>>>> +  gcall *call = as_a <gcall *> (sqrt_stmt);
 >>>>>>> Very minor, but:
 >>>>>>>
 >>>>>>>     gcall *sqrt_stmt
 >>>>>>>       = dyn_cast <gcall *> (SSA_NAME_DEF_STMT (orig_sqrt_ssa_name));
 >>>>>>>     if (!sqrt_stmt || !gimple_call_lhs (sqrt_stmt))
 >>>>>>>       return;
 >>>>>>>
 >>>>>>> would avoid the need for the separate as_a<>, and would mean that
 >>>>>>> we only call gimple_call_* on gcalls.
 >>>>>> Ok.
 >>>>>>>> +  if (has_other_use)
 >>>>>>>> +    {
 >>>>>>>> +      /* Using the two temporaries tmp1, tmp2 from above
 >>>>>>>> +     the original x is now:
 >>>>>>>> +     x = tmp1 * tmp2.  */
 >>>>>>>> +      gcc_assert (mult_ssa_name);
 >>>>>>>> +      gcc_assert (sqr_ssa_name);
 >>>>>>>> +      gimple_stmt_iterator gsi2 = gsi_for_stmt (stmt);
 >>>>>>>> +
 >>>>>>>> +      tree new_ssa_name
 >>>>>>>> +    = make_temp_ssa_name (TREE_TYPE (a), NULL,
 >>>>>>>> "recip_sqrt_transformed");
 >>>>>>>> +      gimple *new_stmt
 >>>>>>>> +    = gimple_build_assign (new_ssa_name, MULT_EXPR,
 >>>>>>>> +                   mult_ssa_name, sqr_ssa_name);
 >>>>>>>> +      gsi_insert_before (&gsi2, new_stmt, GSI_SAME_STMT);
 >>>>>>>> +      gcc_assert (gsi_stmt (gsi2) == stmt);
 >>>>>>>> + gimple_assign_set_rhs_from_tree (&gsi2, new_ssa_name);
 >>>>>>>> +      fold_stmt (&gsi2);
 >>>>>>>> +      update_stmt (stmt);
 >>>>>>> In this case we're replacing the statement in its original position,
 >>>>>>> so there's no real need to use a temporary.  It seems better to
 >>>>>>> change the rhs_code, rhs1 and rhs2 of stmt in-place, with the same
 >>>>>>> lhs as before.
 >>>>>> Yes, that's cleaner.
 >>>>>>>> @@ -762,6 +953,23 @@ pass_cse_reciprocals::execute (function *fun)
 >>>>>>>>          if (optimize_bb_for_size_p (bb))
 >>>>>>>>            continue;
 >>>>>>> Seems unnecessary to skip the new optimisation when optimising for size.
 >>>>>>> Like you say, it saves a multiplication overall. Also:
 >>>>>> Indeed.
 >>>>>>>> +      if (flag_unsafe_math_optimizations)
 >>>>>>>> +    {
 >>>>>>>> +      for (gimple_stmt_iterator gsi = gsi_after_labels (bb);
 >>>>>>>> +           !gsi_end_p (gsi);
 >>>>>>>> +           gsi_next (&gsi))
 >>>>>>>> +        {
 >>>>>>>> +          gimple *stmt = gsi_stmt (gsi);
 >>>>>>>> +
 >>>>>>>> +          if (gimple_has_lhs (stmt)
 >>>>>>>> +          && (def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF)) != NULL
 >>>>>>>> +          && FLOAT_TYPE_P (TREE_TYPE (def))
 >>>>>>>> +          && TREE_CODE (def) == SSA_NAME
 >>>>>>>> +          && is_gimple_assign (stmt)
 >>>>>>>> +          && gimple_assign_rhs_code (stmt) == RDIV_EXPR)
 >>>>>>>> +        optimize_recip_sqrt (&gsi, def);
 >>>>>>>> +        }
 >>>>>>>> +    }
 >>>>>>> It looks like this could safely be done in one of the existing walks
 >>>>>>> (e.g. the execute_cse_reciprocals_1 one, if we do this when optimising
 >>>>>>> for size).
 >>>>>> You're right. I've moved this into one of the walks above this.
 >>>>>>
 >>>>>> Bootstrapped and tested on aarch64-none-linux-gnu and
 >>>>>> x86_64-unknown-linux-gnu.
 >>>>>> CC'ing richi as he's reviewed these kinds of patches in the past.
 >>>>>>
 >>>>>> Is this ok for trunk?
 >>>> I wonder how it interacts with execute_cse_reciprocals_1 given it
 >>>> introduces a division 1.0 / a which will be not processed by
 >>>> execute_cse_reciprocals_1 given that operates by walking uses of 'a'.
 >>>> That may be just a missed optimization of course.
 >>> Hmm, I believe right now it doesn't interact with execute_cse_reciprocals_1 as
 >>> it's either one or the other.
 >>> I've left it as it is for now, but would you like us to call
 >>> execute_cse_reciprocals_1 on the potentially transformed division?
 >> I think that wouldn't "fix" it given execute_cse_reciprocals_1 works by
 >> seeing all reciprocal uses of 'a' so it may have alrady seen two and
 >> you introduced the third.  But we can leave "solving" this for
 >> future enhacements (I'd avoid doing two passes over the IL just because
 >> of said possibility right now).
 >>>> +  if (has_other_use)
 >>>> +    {
 >>>> +      /* Using the two temporaries tmp1, tmp2 from above
 >>>> +        the original x is now:
 >>>> +        x = tmp1 * tmp2.  */
 >>>> +      gcc_assert (mult_ssa_name);
 >>>> +      gcc_assert (sqr_ssa_name);
 >>>> +
 >>>> +      gimple_assign_set_rhs1 (stmt, mult_ssa_name);
 >>>> +      gimple_assign_set_rhs2 (stmt, sqr_ssa_name);
 >>>> +      gimple_assign_set_rhs_code (stmt, MULT_EXPR);
 >>>> +      fold_stmt_inplace (def_gsi);
 >>>> +      update_stmt (stmt);
 >>>> +    }
 >>>>
 >>>> so you are leaving the original stmt in place unchanged even if it is
 >>>> not used?  Why?  Note that with -fno-call-exceptions this stmt may
 >>>> throw, so you should arrange to code-generate 1./a in place of the
 >>>> original division to preserve EH behavior.  Watch out because then
 >>>> with other uses you have to find a place to insert its computation.
 >>> Ok. These are oversights on my part. I've updated the patch to modify the
 >>> original division in place. The multiplication is placed after it.
 >> If the division throws internally you can't insert after it, you
 >> have to insert on the single non-EH edge outgoing from the BB
 >> with the division.  Just try a C++ testcase with -fnon-call-exceptions
 >> and a try {} catch(...) {} around.
 >>
 >> Not sure if it's worth to handle so bailing out if
 >> stmt_can_throw_internal (stmt) would be an option as well.
 >>>> +      if (is_square_of (stmt2, x))
 >>>> +       {
 >>>> +         if (!sqr_stmts.contains (stmt2))
 >>>> +           sqr_stmts.safe_push (stmt2);
 >>>> +       }
 >>>>
 >>>> this is quadratic in the number of square stmts... please consider
 >>>> making sqr_stmts a bitmap of SSA defs (so the stmt you have now
 >>>> is then SSA_NAME_DEF_STMT (ssa_name (bitmap-element))).
 >>> Done. In practice I didn't see there being more than one such use, I expect
 >>> them
 >>> to be CSE'd, but maybe if they're in different basic blocks...
 >> Oh, it just occured to me you could use FOR_EACH_IMM_USE_STMT ()
 >> which will only get you each stmt once... ;)  Sorry for the misleading
 >> bitmap suggestion.
 >>>> You do not seem to restrict placement of the use stmts but insert
 >>>> before the 1/sqrt(a) stmt.  That possibly hoists the multiplications
 >>>> where they are not needed.  Consider
 >>>>
 >>>>    x = 1./sqrt(a);
 >>>>    if (l)
 >>>>      l1 = x * 3.;
 >>>>    else if (l2)
 >>>>      l1 = x * x;
 >>>>    else if (l3)
 >>>>      l1 = a * x;
 >>>>
 >>>> or similar where on the path to x * 3. you now perform two extra
 >>>> multiplications.
 >>> Ok, I've restricted the optimisation somewhat.
 >>> Now if there's an other use it won't perform the transformation unless there
 >>> is already
 >>> a multiplication present on the main path. That way it won't introduce
 >>> multiplications
 >>> on paths where there aren't any.
 >> OK.
 >>>> Your testcases do not cover the case of other uses at all.  Or of
 >>>> EH.
 >>> gcc.dg/recip_sqrt_mult_1.c should handle the other uses case as tmp is a
 >>> global
 >>> being written to. I've added more testcases involving uses in different basic
 >>> blocks
 >>> and a g++.dg testcase with -fnon-call-exceptions.
 >>> I'm not sure what functionality to test though apart from that it doesn't ICE
 >>> and does
 >>> the transformations I expect.
 >> That's good enough I guess.  I see you do have a testcase with
 >> try/catch so I wonder why foo4 doesn't ICE when you insert after
 >> the throwing stmt...  maybe it doesn't throw?  Ah - they probably
 >> fail your new mult_on_main_path test?
 >
 > Yeah. I did manage to reproduce an ICE eventually by removing that check
 > and enabling -ftrapping-math.
 >
 > I think I'll just not enter this at all if stmt_can_throw_internal (stmt) like you suggested.


And here is the version that does that. It also reverts to using a vector for the sqr_stmts for consistency
and uses FOR_EACH_IMM_USE_STMT to iterate over the use statements.

Bootstrapped and tested on aarch64-none-linux-gnu.

Ok?

Thanks,
Kyrill

2018-09-03  Kyrylo Tkachov  <kyrylo.tkachov@arm.com>

     * tree-ssa-math-opts.c (is_mult_by): New function.
     (is_square_of): Use the above.
     (optimize_recip_sqrt): New function.
     (pass_cse_reciprocals::execute): Use the above.

2018-09-03  Kyrylo Tkachov  <kyrylo.tkachov@arm.com>

     * gcc.dg/recip_sqrt_mult_1.c: New test.
     * gcc.dg/recip_sqrt_mult_2.c: Likewise.
     * gcc.dg/recip_sqrt_mult_3.c: Likewise.
     * gcc.dg/recip_sqrt_mult_4.c: Likewise.
     * gcc.dg/recip_sqrt_mult_5.c: Likewise.
     * g++.dg/recip_sqrt_mult_1.C: Likewise.
     * g++.dg/recip_sqrt_mult_2.C: Likewise.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: recip-sqrt-3.patch
Type: text/x-patch
Size: 13174 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20180905/d5c1a119/attachment.bin>


More information about the Gcc-patches mailing list