[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  changed:

   What|Removed |Added

 Status|NEW |RESOLVED
 Resolution|--- |FIXED

--- Comment #10 from Martin Liška  ---
It's kind of doable, but will be quite some work. So let close the PR as I'm
not planning to back port the patch to active branches.

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

[glisse at gcc dot gnu.org]

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

--- Comment #9 from Marc Glisse  ---
I think we can close it, you fixed the main issue (thanks!). Were you leaving
it open so someone might investigate alternate versions of the nonzero
predictor?

[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  changed:

   What|Removed |Added

   Assignee|marxin at gcc dot gnu.org  |unassigned at gcc dot 
gnu.org

--- Comment #8 from Martin Liška  ---
Partially improved, as both return statements are properly assigned 'early
return' predictors. Making this sample even probability. As mentioned in my
previous comment, nonzero predictor is not much successful. Thus leaving the PR
not assigned to me ;)

[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

--- Comment #7 from Martin Liška  ---
Author: marxin
Date: Wed Jun 21 12:51:46 2017
New Revision: 249450

URL: https://gcc.gnu.org/viewcvs?rev=249450=gcc=rev
Log:
Make early return predictor more precise.

2017-06-21  Martin Liska  

PR tree-optimization/79489
* gimplify.c (maybe_add_early_return_predict_stmt): New
function.
(gimplify_return_expr): Call the function.
* predict.c (tree_estimate_probability_bb): Remove handling
of early return.
* predict.def: Update comment about early return predictor.
* gimple-predict.h (is_gimple_predict): New function.
* predict.def: Change default value of early return to 66.
* tree-tailcall.c (find_tail_calls): Skip GIMPLE_PREDICT
statements.
* passes.def: Put pass_strip_predict_hints to the beginning of
IPA passes.

Modified:
trunk/gcc/ChangeLog
trunk/gcc/gimple-low.c
trunk/gcc/gimple-predict.h
trunk/gcc/gimplify.c
trunk/gcc/passes.def
trunk/gcc/predict.c
trunk/gcc/predict.def
trunk/gcc/tree-tailcall.c

[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

--- Comment #6 from Martin Liška  ---
(In reply to Martin Liška from comment #5)
> Author: marxin
> Date: Tue May  2 15:00:47 2017
> New Revision: 247501
> 
> URL: https://gcc.gnu.org/viewcvs?rev=247501=gcc=rev
> Log:
> Remove LTO_STREAMER_DEBUG (PR lto/79489).
> 
> 2017-05-02  Martin Liska  
> 
>   PR lto/79489.
>   * lto-streamer-in.c (lto_read_tree_1): Remove
>   LTO_STREAMER_DEBUG.
>   * lto-streamer.c (struct tree_hash_entry): Likewise.
>   (struct tree_entry_hasher): Likewise.
>   (tree_entry_hasher::hash): Likewise.
>   (tree_entry_hasher::equal): Likewise.
>   (lto_streamer_init): Likewise.
>   (lto_orig_address_map): Likewise.
>   (lto_orig_address_get): Likewise.
>   (lto_orig_address_remove): Likewise.
>   * lto-streamer.h: Likewise.
>   * tree-streamer-in.c (streamer_alloc_tree): Likewise.
>   * tree-streamer-out.c (streamer_write_tree_header): Likewise.
> 
> Modified:
> trunk/gcc/ChangeLog
> trunk/gcc/lto-streamer-in.c
> trunk/gcc/lto-streamer.c
> trunk/gcc/lto-streamer.h
> trunk/gcc/tree-streamer-in.c
> trunk/gcc/tree-streamer-out.c

Sorry, invalid reference.

[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

--- Comment #5 from Martin Liška  ---
Author: marxin
Date: Tue May  2 15:00:47 2017
New Revision: 247501

URL: https://gcc.gnu.org/viewcvs?rev=247501=gcc=rev
Log:
Remove LTO_STREAMER_DEBUG (PR lto/79489).

2017-05-02  Martin Liska  

PR lto/79489.
* lto-streamer-in.c (lto_read_tree_1): Remove
LTO_STREAMER_DEBUG.
* lto-streamer.c (struct tree_hash_entry): Likewise.
(struct tree_entry_hasher): Likewise.
(tree_entry_hasher::hash): Likewise.
(tree_entry_hasher::equal): Likewise.
(lto_streamer_init): Likewise.
(lto_orig_address_map): Likewise.
(lto_orig_address_get): Likewise.
(lto_orig_address_remove): Likewise.
* lto-streamer.h: Likewise.
* tree-streamer-in.c (streamer_alloc_tree): Likewise.
* tree-streamer-out.c (streamer_write_tree_header): Likewise.

Modified:
trunk/gcc/ChangeLog
trunk/gcc/lto-streamer-in.c
trunk/gcc/lto-streamer.c
trunk/gcc/lto-streamer.h
trunk/gcc/tree-streamer-in.c
trunk/gcc/tree-streamer-out.c

[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

--- Comment #4 from Martin Liška  ---
Created attachment 40746
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=40746=edit
Patch for nonzero on non-boolean types

With the patch, I get following numbers for CPU2006 SPEC:

HEURISTICS   BRANCHES  (REL)  BR. HITRATE  
 HITRATE   COVERAGE COVERAGE  (REL)
nonzero (on trees)   9230  20.3%   49.43%   54.40%
/  83.05%51413332496   51.41G   4.7%

As mentioned by Honza, it's quite poor (54.4%). We can measure speed
improvement in next stage1.

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

[hubicka at ucw dot cz]

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

--- Comment #3 from Jan Hubicka  ---
> 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)

True, the problem here is that we used to have multiple return statements in
the gimple
bodies and then it was possible to match what is first one.  Now we merge them
into single
return statement and lose information about original placement.  I think we
could
keep there predict_stmts to handle the info.

This can be done by FE or by gimplifier.

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

I think it is reasonable thing to do.  You can try to invent new PRED_NONZERO
heuristics and see what hitrate it is.  I remember I did it long time ago and
it did not seem to be very useful.  Perhaps things has changed.

Perhaps we can get bit smarter and recognize boolean comparsions. Consider:
t(int a, int b)
{
  if (a==7||b==1)
test();
}

which is seen by predict.c as:

  _3 = a_2(D) == 7;
  _5 = b_4(D) == 1;
  _6 = _3 | _5;
  if (_6 != 0)
goto ;
  else
goto ;

so predict.c does not really see that there are two independent conditions and
interpret it as comparsion of _6 being non-zero.   We could easily look into
cases comparsion operator is SSA name which is a result of boolean operation
and behave smarter. It would make sense to predict independently the value of
_3 and _5 and combine it.  For that we however would need to have
infrastructure for predictions on values and then combine them same way as
predictions on edges.

This would be also more systematic way of handling builtin_expect.

Honza

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

[glisse at gcc dot gnu.org]

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

--- Comment #2 from Marc Glisse  ---
(In reply to Martin Liška from comment #1)
> 1) we wrongly match early return heuristics.

Ah, right, that seems like an important heuristic, but it is very eager, it
applies even if both branches lead to return in equivalent ways. Adding another
function call before return 0 is not enough to disable it, I need to add an
if... On the other hand, I guess that in a less reduced testcase, after
inlining and everything, this may not be such a common case.

> 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.  */

Ah, right, I hadn't thought about this C misfeature :-( I doubt it would make
sense to look at the source language to tweak this heuristic for languages that
use a real 'bool' type... Actually, C uses int, C++ uses a prec=1 type, are
there other cases? Maybe ignoring !=0 could be limited to those 2 types, so at
least long would not be affected?

> 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)
> {
>[100.00%]:
>   if (n_2(D) != 0)
> goto ; [46.00%]
>   else
> goto ; [54.00%]
> 
> is same to:
> 
>[100.00%]:
>   if (n_2(D) == 0)
> goto ; [46.00%]
>   else
> goto ; [54.00%]

Well, in both cases the "else" branch has higher probability than the "then"
branch... But I understand your point.

Thank you for the detailed analysis, very helpful :-)

[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  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  ---
(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)
{
   [100.00%]:
  if (n_2(D) != 0)
goto ; [46.00%]
  else
goto ; [54.00%]

is same to:

   [100.00%]:
  if (n_2(D) == 0)
goto ; [46.00%]
  else
goto ; [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!