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.

0 files changed, 0 insertions, 0 deletions