> On 16 Jul 2026, at 04:05, Andrea Pinski <[email protected]>
> wrote:
>
> On Wed, Jul 15, 2026 at 6:31 PM Andrea Pinski
> <[email protected]> wrote:
>>
>> On Wed, Jul 15, 2026 at 2:09 AM <[email protected]> wrote:
>>>
>>> From: Kyrylo Tkachov <[email protected]>
>>>
>>> average_cost subtracts its unsigned operands before converting the result
>>> to signed int. When THEN_COST is less than ELSE_COST, this relies on an
>>> implementation-defined conversion.
>>
>> Yes and no but only pre-c++20 and C++20 (and C23) require it to be
>> defined in the same way as GCC already does; two complements. We have
>> been assuming that in GCC code for a long time now.
>>
>>
>>> profile_probability::apply also rounds
>>> by adding half the denominator, which is not correct for negative inputs.
>>
>> Now this might be the bigger issue here.
>>
>>>
>>> Use the cheaper arm as the base and scale the nonnegative cost difference
>>> by the probability of executing the more expensive arm. Cast the
>>> expensive arm cost to gcov_type before subtracting the cheaper arm cost.
>>> This keeps the result between the two arm costs and gives the same estimate
>>> when the arms and probability are reversed.
>>>
>>> Add an x86 test with the same costs and probabilities expressed using
>>> reversed CFG arms. Both forms must make the same profitability decision.
>>> This symmetry is also needed when the PR125557 diamond conversion chooses
>>> either CFG arm as its primary arm.
>>>
>>> Bootstrapped and regression tested on aarch64-none-linux-gnu and
>>> x86_64-pc-linux-gnu.
>>>
>>> Ok for trunk?
>>> Thanks,
>>> Kyrill
>>>
>>> gcc/ChangeLog:
>>>
>>> PR tree-optimization/125557
>>> * ifcvt.cc (average_cost): Scale a nonnegative cost difference using
>>> the probability of the more expensive arm.
>>>
>>> gcc/testsuite/ChangeLog:
>>>
>>> PR tree-optimization/125557
>>> * gcc.target/i386/ifcvt-average-cost-1.c: New test.
>>>
>>> Signed-off-by: Kyrylo Tkachov <[email protected]>
>>> ---
>>> gcc/ifcvt.cc | 7 ++++-
>>> .../gcc.target/i386/ifcvt-average-cost-1.c | 31 +++++++++++++++++++
>>> 2 files changed, 37 insertions(+), 1 deletion(-)
>>> create mode 100644 gcc/testsuite/gcc.target/i386/ifcvt-average-cost-1.c
>>>
>>> diff --git a/gcc/ifcvt.cc b/gcc/ifcvt.cc
>>> index d75f1a8ed26..03d9a4c6ab3 100644
>>> --- a/gcc/ifcvt.cc
>>> +++ b/gcc/ifcvt.cc
>>> @@ -4311,7 +4311,12 @@ bb_ok_for_noce_convert_multiple_sets (basic_block
>>> test_bb, unsigned *cost)
>>> static unsigned
>>> average_cost (unsigned then_cost, unsigned else_cost, edge e)
>>> {
>>> - return else_cost + e->probability.apply ((signed) (then_cost -
>>> else_cost));
>>> + if (then_cost < else_cost)
>>> + return then_cost
>>> + + e->probability.invert ().apply ((gcov_type) else_cost - then_cost);
>>> +
>>> + return else_cost
>>> + + e->probability.apply ((gcov_type) then_cost - else_cost);
>>
>> Hmm,
>> /* Compute average of two given costs weighted by relative probabilities
>> of respective basic blocks in an IF-THEN-ELSE. E is the IF-THEN edge.
>> With P as the probability to take the IF-THEN branch, return
>> P * THEN_COST + (1 - P) * ELSE_COST. */
>>
>> So reading this comment makes your patch not do what you think it does.
>> No it is the if then edge:
>> if_info->original_cost += average_cost (then_cost, else_cost,
>> find_edge (test_bb, then_bb));
>>
>> So definitely without updating the comment in the front makes the
>> comment and the code out of sync.
>> So the question is what are we trying to do here.
>> In the case of non-speed we have:
>> if_info->original_cost += then_cost + else_cost;
>>
>> The way I understand this is trying to weight the cost by the
>> probability of the one edge (the other edge will be just 1-probability
>> anyways).
>> So the min of the costs seems wrong here.
>>
>> What we are trying to do is:
>> then_cost*then_prob + else_cost*else_prob
>>
>> where else_prob is (1 - then_prob).
>>
>> So we get:
>> then_cost*then_prob + else_cost*(1 - then_prob)
>> Which is exactly what is in the comment.
>> And with some refactoring we get:
>> else_cost + then_prob*(then_cost-else_cost)
>>
>> Which is exactly what the code does.
>> Now you mentioned that `then_prob*` has a rounding issue for negative case.
>> so obvious to solve that you need.
>>
>> So then this should be the costing:
>> ```
>> signed diff = then_cost - else_cost;
>> /* Avoid the incorrect rounding for negative values. */
>> unsigned other_cost = e->probability.invert ().apply (std::abs (diff));
> Woops this should just be `e->probability.apply (std::abs (diff));`
>
>> if (diff < 0)
>> return else_cost - other_cost;
>> return else_cost + other_cost;
>> ```
>> This is slightly easier to understand than your change (it is correct
>> but harder to correspond to why it is doing what it is doing).
>> And does not explain why you want to use non-negative numbers here.
>
> But maybe the fix really should be in profile_probability::apply.
>
> Currently it does:
> ```
> gcov_type apply (gcov_type val) const
> {
> if (*this == uninitialized ())
> return val / 2;
> return RDIV (val * m_val, max_probability);
> }
>
> #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
>
> static const int n_bits = 29;
> /* We can technically use ((uint32_t) 1 << (n_bits - 1)) - 2 but that
> will lead to harder multiplication sequences. */
> static const uint32_t max_probability = (uint32_t) 1 << (n_bits - 2);
> ```
>
> So maybe it should be:
> ```
> gcov_type apply (gcov_type val) const
> {
> if (*this == uninitialized ())
> return val / 2;
> if (val > 0)
> return RDIV (val * m_val, max_probability);
> return -RDIV (-val * m_val, max_probability);
> }
> ```
> Which will fix the rounding issue. This is the only place which uses
> profile_probability::apply in the whole GCC code base so fixing apply
> would be best.
>
Thanks for the analysis. I’ve split this into two patches. I’ve adjusted this
to handle undefined overflow for INT64_MIN and for large val * m_val.
Thanks,
Kyrill
> Thanks,
> Andrea
>
>
>>
>> Thanks,
>> Andrea
>>
>>> + if (then_cost < else_cost)
>>> + return then_cost
>>> + + e->probability.invert ().apply ((gcov_type) else_cost - then_cost);
>>> +
>>> + return else_cost
>>> + + e->probability.apply ((gcov_type) then_cost - else_cost);
>>
>>
>>> }
>>>
>>> /* Given a simple IF-THEN-JOIN or IF-THEN-ELSE-JOIN block, attempt to
>>> convert
>>> diff --git a/gcc/testsuite/gcc.target/i386/ifcvt-average-cost-1.c
>>> b/gcc/testsuite/gcc.target/i386/ifcvt-average-cost-1.c
>>> new file mode 100644
>>> index 00000000000..2e70cde06be
>>> --- /dev/null
>>> +++ b/gcc/testsuite/gcc.target/i386/ifcvt-average-cost-1.c
>>> @@ -0,0 +1,31 @@
>>> +/* { dg-do compile } */
>>> +/* { dg-require-effective-target lp64 } */
>>> +/* { dg-options "-O2 -mtune=generic
>>> --param=max-rtl-if-conversion-unpredictable-cost=0 -fdump-rtl-ce1" } */
>>> +
>>> +/* These functions describe the same branch probabilities and arm costs
>>> with
>>> + the arms reversed. */
>>> +long
>>> +then_cheaper (long c, long a, long b)
>>> +{
>>> + long x;
>>> + if (__builtin_expect_with_probability (c != 0, 0, 0.90))
>>> + x = a ^ b;
>>> + else
>>> + x = b * 3 + 1;
>>> + return x;
>>> +}
>>> +
>>> +long
>>> +then_costlier (long c, long a, long b)
>>> +{
>>> + long x;
>>> + if (__builtin_expect_with_probability (c == 0, 1, 0.90))
>>> + x = b * 3 + 1;
>>> + else
>>> + x = a ^ b;
>>> + return x;
>>> +}
>>> +
>>> +/* { dg-final { scan-rtl-dump-not "if-conversion succeeded through
>>> noce_try_cmove_arith" "ce1" } } */
>>> +/* { dg-final { scan-assembler-not {\tcmov} } } */
>>> +/* { dg-final { scan-assembler-times {\tj(e|ne)\t} 2 } } */
>>> --
>>> 2.50.1 (Apple Git-155)
