On Fri, Nov 15, 2024 at 10:43:57AM +0100, Filip Kastl wrote:
> Hi,
>
> Andi's greedy bit test finding algorithm was reverted. I found a fix for the
> problem that caused the revert. I made this patch to reintroduce the greedy
> alg into GCC. However I think we should keep the old slow but more powerful
> algorithm so I added a limit on the number of cases of the switch statement
> that decides which of the two algorithms to use.
Do we actually have a case where the DP algorithm is better?
In the bootstrap comparison greedy does produce less or the same clusters
> + k = 0;
> + while (i + k < l)
> + {
> + cluster *end_cluster = clusters[i + k];
> +
> + /* Does value range fit into the BITS_PER_WORD window? */
> + HOST_WIDE_INT w = cluster::get_range (start_cluster->get_low (),
> + end_cluster->get_high ());
> + if (w == 0 || w > BITS_PER_WORD)
> + break;
> +
> + /* Check for max # of targets. */
> + if (targets.elements () == m_max_case_bit_tests
> + && !targets.contains (end_cluster->m_case_bb))
> + break;
> +
> + targets.add (end_cluster->m_case_bb);
> + k++;
> + }
>
> + if (is_beneficial (k, targets.elements ()))
Equivalent to the old test in DP would be k + 1
I'm not sure it makes a lot of difference though.
-Andi
