[Bug tree-optimization/79489] Strange static branch prediction for n != 0

[marxin at gcc dot gnu.org]

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

Martin Liška <marxin at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2017-02-14
                 CC|                            |hubicka at ucw dot cz
           Assignee|unassigned at gcc dot gnu.org      |marxin at gcc dot gnu.org
     Ever confirmed|0                           |1

--- Comment #1 from Martin Liška <marxin at gcc dot gnu.org> ---
(In reply to Marc Glisse from comment #0)
> http://stackoverflow.com/q/41880779/1918193
> 
> extern void foo();
> extern void bar();
> 
> int some_func(int n)
> {
>     if (n) {
>         foo();
>     }
>     else {
>         bar();
>     }
>     return 0;
> }
> 
> gcc's profile_estimate guesses (DS theory heuristics) that n is 0 with
> probability 54%. This seems strange, as other parts of the compiler predict
> == as more likely false (at least for types with precision > 1).

Huh, there are various (in my opinion real) issue that mix together.

Predictions for bb 2
  call heuristics of edge 2->4 (edge pair duplicate): 33.0%
  call heuristics of edge 2->3 (edge pair duplicate): 33.0%
  DS theory heuristics: 46.0%
  combined heuristics: 46.0%
  early return (on trees) heuristics of edge 2->3: 46.0%

1) we wrongly match early return heuristics. It's a known issue as mentioned in
predict.def:

/* Branch causing function to terminate is probably not taken. 
   FIXME: early return currently predicts code:
   int foo (int a)
   {
      if (a)
        bar();
      else
        bar2();
   }
   even though there is no return statement involved.  We probably want to
track
   this from FE or retire the predictor.  */
DEF_PREDICTOR (PRED_TREE_EARLY_RETURN, "early return (on trees)", HITRATE (54),
0)

2) We completely ignore 'n != 0' comparison as we consider it useless due to:

        /* Comparisons with 0 are often used for booleans and there is
           nothing useful to predict about them.  */
        else if (integer_zerop (op0)
                 || integer_zerop (op1))
          ;

> 
> Also, we may want to document somewhere that gcc tends to consider the
> "else" branch as more likely (or at least does not particularly favor the
> "then" branch), since there is quite a bit of information on the web that
> recommends writing conditions the other way around. But the heuristics are
> complicated enough that it is hard to come up with a statement that is true
> without being uselessly vague.

Yep, sometimes mixture of predictors result in strange results. However we do
not prefer
'else' as more likely compared to 'then' branch. It all depends on the
predictors, e.g.

some_func (int n)
{
  <bb 2> [100.00%]:
  if (n_2(D) != 0)
    goto <bb 3>; [46.00%]
  else
    goto <bb 4>; [54.00%]

is same to:

  <bb 2> [100.00%]:
  if (n_2(D) == 0)
    goto <bb 3>; [46.00%]
  else
    goto <bb 4>; [54.00%]

> 
> (I won't be surprised if this ends up as invalid or wontfix, but it felt
> worth forwarding)

I'm planning to discuss that with Honza and it should be done for GCC 8.

Thanks for report!