This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Clustering switch cases


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.
>


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]