[Bug tree-optimization/106617] [13 Regression] gcc is very slow at ternary expressions since r13-322-g7f04b0d786e13ff5

[rguenth at gcc dot gnu.org via Gcc-bugs]

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

--- Comment #12 from Richard Biener <rguenth at gcc dot gnu.org> ---
Btw, just for reference the original looks like

 fc_cpu_order = ( __builtin_constant_p(( __builtin_constant_p(nr_cpu_ids) ? (
((nr_cpu_ids) == 1) ? 1 : (1UL << (( __builtin_constant_p((nr_cpu_ids) - 1) ? (
__builtin_constant_p((nr_cpu_ids) - 1) ? ( ((nr_cpu_ids) - 1) < 2 ? 0 :
((nr_cpu_ids) - 1) & (1ULL << 63) ? 63 : ((nr_cpu_ids) - 1) & (1ULL << 62) ? 62
: ((nr_cpu_ids) - 1) & (1ULL << 61) ? 61 : ((nr_cpu_ids) - 1) & (1ULL << 60) ?
60 : ((nr_cpu_ids) - 1) & (1ULL << 59) ? 59 : ((nr_cpu_ids) - 1) & (1ULL << 58)
? 58 : ((nr_cpu_ids) - 1) & (1ULL << 57) ? ...

so some fancy ceil_log2.

If you take a simplified

unsigned long fc_setup_exch_mgr(int nr_cpu_ids_m1)
{
  return ((((nr_cpu_ids_m1)) & (1<<21) ? 21
                  : ((nr_cpu_ids_m1)) & (1<<20) ? 20
                  : ((nr_cpu_ids_m1)) & (1<<19) ? 19
                  : ((nr_cpu_ids_m1)) & (1<<18) ? 18
                  : ((nr_cpu_ids_m1)) & (1<<17) ? 17
                  : ((nr_cpu_ids_m1)) & (1<<16) ? 16
                  : ((nr_cpu_ids_m1)) & (1<<15) ? 15
                  : ((nr_cpu_ids_m1)) & (1<<14) ? 14
                  : ((nr_cpu_ids_m1)) & (1<<13) ? 13
                  : ((nr_cpu_ids_m1)) & (1<<12) ? 12
                  : ((nr_cpu_ids_m1)) & (1<<11) ? 11  /* THIS */
                  : ((nr_cpu_ids_m1)) & (1<<9)  ? 9
                  : ((nr_cpu_ids_m1)) & (1<<8)  ? 8
                  : ((nr_cpu_ids_m1)) & (1<<7)  ? 7
                  : ((nr_cpu_ids_m1)) & (1<<6)  ? 6
                  : ((nr_cpu_ids_m1)) & (1<<5)  ? 5
                  : ((nr_cpu_ids_m1)) & (1<<4)  ? 4
                  : ((nr_cpu_ids_m1)) & (1<<3) ? 3
                  : 0)) != 11;
}

I see

./cc1 -quiet t2.c -fdump-tree-original-folding; grep 'Applying'
t2.c.005t.original  | sort -u ; grep 'Applying' t2.c.005t.original  | wc -l
Applying pattern match.pd:4778, generic-match.cc:95676
Applying pattern match.pd:5809, generic-match.cc:24025
16383

but when I just remove the marked line it becomes

./cc1 -quiet t2.c -fdump-tree-original-folding; grep 'Applying'
t2.c.005t.original  | sort -u ; grep 'Applying' t2.c.005t.original  | wc -l
Applying pattern match.pd:4778, generic-match.cc:95676
Applying pattern match.pd:5809, generic-match.cc:24025
34

hmm, and the issue is probably that we have this pattern both in
fold-const.cc and match.pd and thus when the pattern applies recursively,
like for

 (a ? (b ? d : e) : f) > g

and the original fold implementation would simplify because one of the
braches simplifes:

  /* Check that we have simplified at least one of the branches.  */
  if (!TREE_CONSTANT (arg) && !TREE_CONSTANT (lhs) && !TREE_CONSTANT (rhs))
    return NULL_TREE;

so it goes all the way, recursively to "simple".  But then the match.pd
variant rejects the result because it is EXPR_P for the lhs (but not
for the rhs).  We always first try the match.pd path but then will
try fold_binary_op_with_conditional_arg anyway which makes this effectively
at least quadratic.

This was all done to avoid regressing the COND_EXPR gimple IL refactoring.
One possibility to avoid the recursion with fold-const is to disable the
match.pd pattern for GENERIC.