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 <tnfch...@gcc.gnu.org>: https://gcc.gnu.org/g:9ed4fcfe47f28b36c73d74109898514ef4da00fb commit r14-2517-g9ed4fcfe47f28b36c73d74109898514ef4da00fb Author: Tamar Christina <tamar.christ...@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.
