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,
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)
> >
