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.guent...@gmail.com> wrote: > On Fri, Aug 27, 2010 at 4:47 PM, Ian Lance Taylor <i...@google.com> wrote: >> "Paulo J. Matos" <pocma...@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. >
