Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

LLVM's pivot element selection is bad for sparse switch statements #22636

Closed
llvmbot opened this issue Jan 19, 2015 · 5 comments
Closed

LLVM's pivot element selection is bad for sparse switch statements #22636

llvmbot opened this issue Jan 19, 2015 · 5 comments
Labels
bugzilla Issues migrated from bugzilla llvm:codegen

Comments

@llvmbot
Copy link
Member

llvmbot commented Jan 19, 2015

Bugzilla Link 22262
Resolution FIXED
Resolved on Jul 23, 2020 08:42
Version trunk
OS All
Reporter LLVM Bugzilla Contributor
CC @asl,@chandlerc,@majnemer,@echristo,@zmodem

Extended Description

Example:

void f(int v) {
switch (v) {
case 10: a(); break;
case 20: b(); break;
case 30: c(); break;
case 40: d(); break;
case 50: e(); break;
case 60: f(); break;
default: h();
}
}

in lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp, this correctly calls handleBTSplitSwitchCase in order to create a binary decision tree for the switch statement. However, the heuristic for selecting the pivot element tries to maximize the sum of the density of the left and the right half. This makes sense in order to split at "holes" leading to increased usage of jump tables later. However, if the density is uniformly distribute such as in the example, this will always pick a single element on the left or on the right as the density of the single element is 1 and far greater than any other density. Thus, the "binary tree" falls back to a linear check of all values.

In order to solve this, we can
a) Compute beforehand that we won't find any subrange to use a jump table for.
b) Precompute the ideal ranges for jump tables. This might actually turn out to find jump tables in cases where the current heuristic doesn't find them.
@llvmbot
Copy link
Member Author

llvmbot commented Jan 20, 2015

Your example can easily be transformed to a dense jump table by modifying the value by a multiplication with the inverse of 15 (0xeeeeeeef) and rotating right by 2. In this case the first entry is not used.
Early 2014 I had prepared a patch doing this special case but also applied perfect hashing early 2014 but was mostly ignored. Sigh.

See also the work of eeckstein, http://llvm.org/viewvc/llvm-project?view=revision&revision=222121.

@zmodem
Copy link
Collaborator

zmodem commented Jan 20, 2015

Your example can easily be transformed to a dense jump table by modifying
the value by a multiplication with the inverse of 15 (0xeeeeeeef) and
rotating right by 2. In this case the first entry is not used.
Early 2014 I had prepared a patch doing this special case but also applied
perfect hashing early 2014 but was mostly ignored. Sigh.

IIRC, the problem was the the patch was huge, not that anyone was against the idea of using perfect hashing for switches.

As you say, Daniel's specific example can be handled by dividing the case values by 10, which would be a cool thing to be able to do, but that doesn't fix the general issue of selecting a bad pivot.

Daniel, I like the sound of the b) approach, i.e. chunking together cases that can be used in jump tables first, and then doing the binary tree after.

@asl
Copy link
Collaborator

asl commented Jan 21, 2015

Daniel, I like the sound of the b) approach, i.e. chunking together cases
that can be used in jump tables first, and then doing the binary tree after.
+1. We'd just estimate the required density for the jump tables and cluster the switch cases into such intervals of case range.

@zmodem
Copy link
Collaborator

zmodem commented Apr 25, 2015

This was committed in r235560, with follow-ups in r235608 and r235729.

See the code review at http://reviews.llvm.org/D8649 for numbers and such.

@Kojoley
Copy link
Contributor

Kojoley commented Jul 23, 2020

*** Bug #18721 has been marked as a duplicate of this bug. ***

@llvmbot llvmbot transferred this issue from llvm/llvm-bugzilla-archive Dec 9, 2021
This issue was closed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
bugzilla Issues migrated from bugzilla llvm:codegen
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
4 participants
@asl @zmodem @Kojoley @llvmbot