[Bug middle-end/109849] suboptimal code for vector walking loop

["cvs-commit at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>]

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

--- Comment #20 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jan Hubicka <hubicka@gcc.gnu.org>:

https://gcc.gnu.org/g:eab57b825bcc350e9ff44eb2fa739a80199d9bb1

commit r14-2219-geab57b825bcc350e9ff44eb2fa739a80199d9bb1
Author: Jan Hubicka <jh@suse.cz>
Date:   Fri Jun 30 16:27:27 2023 +0200

    Fix handling of __builtin_expect_with_probability and improve first-match
heuristics

    While looking into the std::vector _M_realloc_insert codegen I noticed that
    call of __throw_bad_alloc is predicted with 10% probability. This is
because
    the conditional guarding it has __builtin_expect (cond, 0) on it.  This
    incorrectly takes precedence over more reliable heuristics predicting that
call
    to cold noreturn is likely not going to happen.

    So I reordered the predictors so __builtin_expect_with_probability comes
first
    after predictors that never makes a mistake (so user can use it to always
    specify the outcome by hand).  I also downgraded malloc predictor since I
do
    think user-defined malloc functions & new operators may behave funny ways
and
    moved usual __builtin_expect after the noreturn cold predictor.

    This triggered latent bug in expr_expected_value_1 where

              if (*predictor < predictor2)
                *predictor = predictor2;

    should be:

              if (predictor2 < *predictor)
                *predictor = predictor2;

    which eventually triggered an ICE on combining heuristics.  This made me
notice
    that we can do slightly better while combining expected values in case only
    one of the parameters (such as in a*b when we expect a==0) can determine
    overall result.

    Note that the new code may pick weaker heuristics in case that both values
are
    predicted.  Not sure if this scenario is worth the extra CPU time: there is
    not correct way to combine the probabilities anyway since we do not know if
    the predictions are independent, so I think users should not rely on it.

    Fixing this issue uncovered another problem.  In 2018 Martin Liska added
    code predicting that MALLOC returns non-NULL but instead of that he
predicts
    that it returns true (boolean 1).  This sort of works for testcase testing
     malloc (10) != NULL
    but, for example, we will predict
     malloc (10) == malloc (10)
    as true, which is not right and such comparsion may happen in real code

    I think proper way is to update expr_expected_value_1 to work with value
    ranges, but that needs greater surgery so I decided to postpone this and
    only add FIXME and fill PR110499.

    gcc/ChangeLog:

            PR middle-end/109849
            * predict.cc (estimate_bb_frequencies): Turn to static function.
            (expr_expected_value_1): Fix handling of binary expressions with
            predicted values.
            * predict.def (PRED_MALLOC_NONNULL): Move later in the priority
queue.
            (PRED_BUILTIN_EXPECT_WITH_PROBABILITY): Move to almost top of the
priority
            queue.
            * predict.h (estimate_bb_frequencies): No longer declare it.

    gcc/testsuite/ChangeLog:

            PR middle-end/109849
            * gcc.dg/predict-18.c: Improve testcase.