Re: [PATCH] Optimise sqrt reciprocal multiplications

["H.J. Lu" <hjl dot tools at gmail dot com>]

On Wed, Sep 5, 2018 at 4:38 AM, Kyrill  Tkachov
<kyrylo.tkachov@foss.arm.com> wrote:
> 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.

This caused:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87283

-- 
H.J.