For some reason, recently fixed if-conversion (PR79389) does not trigger in PGO case. There is still a jump with -O2:

	mulsd	%xmm0, %xmm5
	mulsd	%xmm2, %xmm2
	addsd	%xmm2, %xmm5
	ucomisd	%xmm5, %xmm4
	jb	.L17
.L16:
	addl	$1, %ebp
.L17:
	addl	$1, %edi
	cmpl	%edi, %ebx
	je	.L5

Since this asm corresponds to random operands, the jump can't be predicted:

        for (count=0; count<Num_samples; count++)
        {
            double x= Random_nextDouble(R);
            double y= Random_nextDouble(R);

            if ( x*x + y*y <= 1.0)
                 under_curve ++;
            
        }

Based on the discussion in PR79389, and the fact that -O2 and -O3 both compile to a jump, I suspect that loop splitting cost model should be fine tuned to also handle PGO case. Note that

Adding some CCs.

On Mon, 27 Mar 2017, ubizjak at gmail dot com wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80197
> 
> Uroš Bizjak <ubizjak at gmail dot com> changed:
> 
>            What    |Removed                     |Added
> ----------------------------------------------------------------------------
>              Status|UNCONFIRMED                 |NEW
>    Last reconfirmed|                            |2017-03-27
>                  CC|                            |jakub at gcc dot gnu.org,
>                    |                            |rguenth at gcc dot gnu.org
>      Ever confirmed|0                           |1
> 
> --- Comment #1 from Uroš Bizjak <ubizjak at gmail dot com> ---
> For some reason, recently fixed if-conversion (PR79389) does not trigger in PGO
> case. There is still a jump with -O2:
> 
>         mulsd   %xmm0, %xmm5
>         mulsd   %xmm2, %xmm2
>         addsd   %xmm2, %xmm5
>         ucomisd %xmm5, %xmm4
>         jb      .L17
> .L16:
>         addl    $1, %ebp
> .L17:
>         addl    $1, %edi
>         cmpl    %edi, %ebx
>         je      .L5
> 
> Since this asm corresponds to random operands, the jump can't be predicted:
> 
>         for (count=0; count<Num_samples; count++)
>         {
>             double x= Random_nextDouble(R);
>             double y= Random_nextDouble(R);
> 
>             if ( x*x + y*y <= 1.0)
>                  under_curve ++;
> 
>         }
> 
> Based on the discussion in PR79389, and the fact that -O2 and -O3 both compile
> to a jump, I suspect that loop splitting cost model should be fine tuned to
> also handle PGO case. Note that
> 
> Adding some CCs.

Not sure - loop splitting isn't done here and doing it would remove
the if-conversion opportunity.

I think that if FDO says either the true or false edge is very likely
then not if-converting the loop is best?  Or is a well-predicted
conditional move as good as a well-predicted if?  10% missed branches
would be more than

/* When branch is predicted to be taken with probability lower than this
   threshold (in percent), then it is considered well predictable. */
DEFPARAM (PARAM_PREDICTABLE_BRANCH_OUTCOME,
          "predictable-branch-outcome",
          "Maximal estimated outcome of branch considered predictable.",
          2, 0, 50)

so it shouldn't affect if-conversion...

Are we sure we're not hitting some architectural limitation here?  Like
disabling the loop stream cache because of size or the CFG?
(otoh we have calls in the loop(?)).

(In reply to rguenther@suse.de from comment #2)

> I think that if FDO says either the true or false edge is very likely
> then not if-converting the loop is best?  Or is a well-predicted
> conditional move as good as a well-predicted if?  10% missed branches
> would be more than

Please note that when if-conversion succeeded through noce_try_addcc, we don't care about prediction anymore. The conversion converts:

	ucomisd	%xmm5, %xmm4
	jb	.L17
.L16:
	addl	$1, %ebp
.L17:

to:

	ucomisd	%xmm0, %xmm3	# 195	*cmpiudf/2	[length = 4]
	sbbl	$-1, %ebx	# 196	subsi3_carry/1	[length = 3]

IMO, this conversion should always be performed, as it is always a win.

According to my analysis, this is mostly caused by different inlining decisions with regards to inlining new_Random_seed into MonteCarlo_integrate.  Inlining happens at profile-generate time, but does not happen at profile-use time.  This appears to throw off edge probabilities, and also prevents the compiler from seeing that R->haveRange accessed in Random_nextDouble (which is inlined) is always 0.

Declaring new_Random_seed (which is called once) as 'inline __attribute__((always_inline))' makes code generation sane again.

On trunk, manually fixing up inlining is not enough: trunk additionally needs -fno-tracer, otherwise crucial if-conversion of 'if (k < 0) k += m1;' is prevented.

On Tue, 28 Mar 2017, amonakov at gcc dot gnu.org wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80197
> 
> --- Comment #5 from Alexander Monakov <amonakov at gcc dot gnu.org> ---
> On trunk, manually fixing up inlining is not enough: trunk additionally needs
> -fno-tracer, otherwise crucial if-conversion of 'if (k < 0) k += m1;' is
> prevented.

That means -ftracer has similar issues as path splitting.  -ftracer
simply looks for a path with high probability so supposedly the
distorted profile might be the reason for this?

No, with fixed-up inlining -ftracer sees reasonable edge probabilities. The reason tracer makes things worse here, is that it clones the path leading to a 50%/50% conditional branch (and correctly stops at that branch), making the tiny BB under that branch ineligible(?) for if-conversion. We go from

<BB0>
if (!cond) goto <BB2>
  <BBcond>
  var = VAL;   // this can eventually become a cmov
<BB2>

to

<BB0_1>
if (!cond) goto <BB2>
goto <BBcond>

...

<BB0_2>
if (!cond) goto <BB2>
  <BBcond>
  var = VAL;  // this doesn't become a cmov
<BB2>


I think in principle if-conversion could still do its job here by duplicating the conditional var=VAL assignment under BB0_1.

Here's a silly compile-only sample where -O2 -ftracer is worse than -O2 due to this effect:

void f(long n, signed char *x)
{
  for (; n; n--) {
    long a=x[n], b;
    if (!a)
      a = 42;
    b = x[a];
    if (b < 0)
      b += a;
    x[b] = 0;
  }
}

On Wed, 29 Mar 2017, amonakov at gcc dot gnu.org wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80197
> 
> --- Comment #7 from Alexander Monakov <amonakov at gcc dot gnu.org> ---
> No, with fixed-up inlining -ftracer sees reasonable edge probabilities. The
> reason tracer makes things worse here, is that it clones the path leading to a
> 50%/50% conditional branch (and correctly stops at that branch), making the
> tiny BB under that branch ineligible(?) for if-conversion. We go from
> 
> <BB0>
> if (!cond) goto <BB2>
>   <BBcond>
>   var = VAL;   // this can eventually become a cmov
> <BB2>
> 
> to
> 
> <BB0_1>
> if (!cond) goto <BB2>
> goto <BBcond>
> 
> ...
> 
> <BB0_2>
> if (!cond) goto <BB2>
>   <BBcond>
>   var = VAL;  // this doesn't become a cmov
> <BB2>
> 
> 
> I think in principle if-conversion could still do its job here by duplicating
> the conditional var=VAL assignment under BB0_1.
> 
> Here's a silly compile-only sample where -O2 -ftracer is worse than -O2 due to
> this effect:
> 
> void f(long n, signed char *x)
> {
>   for (; n; n--) {
>     long a=x[n], b;
>     if (!a)
>       a = 42;
>     b = x[a];
>     if (b < 0)
>       b += a;
>     x[b] = 0;
>   }
> }

It's hard for tracer to predict followup optimization opportunities
in the isolated path and weight that against missed if-conversion
opportunities.

Of course the fact that late phiopt runs after tracer / split-paths
doesn't help, nor that phiopt doesn't catch this kind of
if-conversion (the idea was that the RTL pass can do _much_ better
in assessing if-conversion const/benefit).

Tracer doesn't have a very sophisticated cost model either.

The original idea of tracing was that we can pro-actively duplicate tails and rely on crossjumping to merge the paths back if they did not trigger context sensitive optimizations.  Nowdays crossjumping much weaker than it used to be because it does not handle well RTL genertated from SSA and we do not do any gimple level tail merging after tracer which we probably should.