[Bug tree-optimization/109154] [13/14 regression] jump threading de-optimizes nested floating point comparisons

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

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

--- Comment #67 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Tamar Christina <tnfchris@gcc.gnu.org>:

https://gcc.gnu.org/g:9ed4fcfe47f28b36c73d74109898514ef4da00fb

commit r14-2517-g9ed4fcfe47f28b36c73d74109898514ef4da00fb
Author: Tamar Christina <tamar.christina@arm.com>
Date:   Fri Jul 14 11:21:46 2023 +0100

    ifcvt: Sort PHI arguments not only occurrences but also complexity
[PR109154]

    This patch builds on the previous patch by fixing another issue with the
    way ifcvt currently picks which branches to test.

    The issue with the current implementation is while it sorts for
    occurrences of the argument, it doesn't check for complexity of the
arguments.

    As an example:

      <bb 15> [local count: 528603100]:
      ...
      if (distbb_75 >= 0.0)
        goto <bb 17>; [59.00%]
      else
        goto <bb 16>; [41.00%]

      <bb 16> [local count: 216727269]:
      ...
      goto <bb 19>; [100.00%]

      <bb 17> [local count: 311875831]:
      ...
      if (distbb_75 < iftmp.0_98)
        goto <bb 18>; [20.00%]
      else
        goto <bb 19>; [80.00%]

      <bb 18> [local count: 62375167]:
      ...

      <bb 19> [local count: 528603100]:
      # prephitmp_175 = PHI <_173(18), 0.0(17), _174(16)>

    All tree arguments to the PHI have the same number of occurrences, namely
1,
    however it makes a big difference which comparison we test first.

    Sorting only on occurrences we'll pick the compares coming from BB 18 and
BB 17,
    This means we end up generating 4 comparisons, while 2 would have been
enough.

    By keeping track of the "complexity" of the COND in each BB, (i.e. the
number
    of comparisons needed to traverse from the start [BB 15] to end [BB 19])
and
    using a key tuple of <occurrences, complexity> we end up selecting the
compare
    from BB 16 and BB 18 first.  BB 16 only requires 1 compare, and BB 18,
after we
    test BB 16 also only requires one additional compare.  This change paired
with
    the one previous above results in the optimal 2 compares.

    For deep nesting, i.e. for

    ...
      _79 = vr_15 > 20;
      _80 = _68 & _79;
      _82 = vr_15 <= 20;
      _83 = _68 & _82;
      _84 = vr_15 < -20;
      _85 = _73 & _84;
      _87 = vr_15 >= -20;
      _88 = _73 & _87;
      _ifc__111 = _55 ? 10 : 12;
      _ifc__112 = _70 ? 7 : _ifc__111;
      _ifc__113 = _85 ? 8 : _ifc__112;
      _ifc__114 = _88 ? 9 : _ifc__113;
      _ifc__115 = _45 ? 1 : _ifc__114;
      _ifc__116 = _63 ? 3 : _ifc__115;
      _ifc__117 = _65 ? 4 : _ifc__116;
      _ifc__118 = _83 ? 6 : _ifc__117;
      _ifc__119 = _60 ? 2 : _ifc__118;
      _ifc__120 = _43 ? 13 : _ifc__119;
      _ifc__121 = _75 ? 11 : _ifc__120;
      vw_1 = _80 ? 5 : _ifc__121;

    Most of the comparisons are still needed because the chain of
    occurrences to not negate eachother. i.e. _80 is _73 & vr_15 >= -20 and
    _85 is _73 & vr_15 < -20.  clearly given _73 needs to be true in both
branches,
    the only additional test needed is on vr_15, where the one test is the
negation
    of the other.  So we don't need to do the comparison of _73 twice.

    The changes in the patch reduces the overall number of compares by one, but
has
    a bigger effect on the dependency chain.

    Previously we would generate 5 instructions chain:

            cmple   p7.s, p4/z, z29.s, z30.s
            cmpne   p7.s, p7/z, z29.s, #0
            cmple   p6.s, p7/z, z31.s, z30.s
            cmpge   p6.s, p6/z, z27.s, z25.s
            cmplt   p15.s, p6/z, z28.s, z21.s

    as the longest chain.  With this patch we generate 3:

            cmple   p7.s, p3/z, z27.s, z30.s
            cmpne   p7.s, p7/z, z27.s, #0
            cmpgt   p7.s, p7/z, z31.s, z30.s

    and I don't think (x <= y) && (x != 0) && (z > y) can be reduced further.

    gcc/ChangeLog:

            PR tree-optimization/109154
            * tree-if-conv.cc (INCLUDE_ALGORITHM): Include.
            (struct bb_predicate): Add no_predicate_stmts.
            (set_bb_predicate): Increase predicate count.
            (set_bb_predicate_gimplified_stmts): Conditionally initialize
            no_predicate_stmts.
            (get_bb_num_predicate_stmts): New.
            (init_bb_predicate): Initialzie no_predicate_stmts.
            (release_bb_predicate): Cleanup no_predicate_stmts.
            (insert_gimplified_predicates): Preserve no_predicate_stmts.

    gcc/testsuite/ChangeLog:

            PR tree-optimization/109154
            * gcc.dg/vect/vect-ifcvt-20.c: New test.