Re: Clustering switch cases

[Xinliang David Li <davidxl@google.com>]

Another main thing missing is to consider profile information (if
available) so that most frequent cases can be peeled out.

David

On Fri, Aug 27, 2010 at 8:03 AM, Richard Guenther
<richard.guenther@gmail.com> wrote:
> On Fri, Aug 27, 2010 at 4:47 PM, Ian Lance Taylor <iant@google.com> wrote:
>> "Paulo J. Matos" <pocmatos@gmail.com> writes:
>>
>>> In the first case, it generates a binary tree, and in the second two
>>> jump tables. The jump tables solution is much more elegant (at least
>>> in our situation), generating less code and being faster.
>>> Now, what I am wondering is the reason why GCC doesn't try to cluster
>>> the cases trying to find for clusters of contiguous values in the
>>> switch.
>>>
>>> If there is no specific reason then I would implement such pass, which
>>> would before expansion split switches according to value clustering,
>>> since I find it would be a good code improvement.
>>>
>>> Currently GCC seems to only use jump table is the range of the switch
>>> is not much bigger than its count, which works well in most cases
>>> except when you have big switches with clusters of contiguous values
>>> (like the first example I sent).
>>
>> I don't know of any specific reason not to look for clusters of switch
>> cases.  The main issue would be the affect on compilation time.  If you
>> can do it with an algorithm which is linear in the number of cases, then
>> I think it would be an acceptable optimization.
>
> In fact we might want to move switch optimization up to the tree level
> (just because it's way easier to deal with there).  Thus, lower switch
> to a mixture of binary tree & jump-tables (possibly using perfect
> hashing).
>
> Richard.
>