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.
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
sdisel switch lowering can be improved #1298
Comments
Fixed the first, easy part where it creates a "jmp" to the next block. http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20061016/038759.html The more interesting bit is yet to be done. |
Another fun thing we could do: |
LLVM-to-LLVM pass implemented in: http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20070226/045250.html |
Mine. First part here: http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20070319/046002.html |
Second step here: http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20070402/046810.html Now we don't discriminate cases 0-6 in such example. However, here much more |
Next stage: http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20070409/047077.html Implemented shift-and and some other heuristics. |
What is left on this old bug? |
llvm#1298 スケッドモデルをオリジナルに戻す See merge request a64fx-swpl/llvm-project!27
Extended Description
First, the trivial thing: a switch lowered to a series of conditional branches always results in an explicit
"fallthrough" uncond branch to the next block from the initial block. This is probably a minor book-
keeping bug:
*** jmp LBB1_15 #entry
LBB1_15: #entry
More significantly, we should change the heuristic of the switch lowering a bit. Specifically, right now,
at the top level, we decide whether to lower the switch to a series of branches or to a table jump. I
think we should always go through the "branch sequence" code path, but make it a bit more
sophisticated.
In particular, the worklist should start out with a single record with all the case ranges on it. Each time
through the loop, a range is popped off. If the range satisfies the conditions for a tbljmp, emit one.
Otherwise, split in half and emit a branch to choose between the two.
This would allow us to handle switches with dense portions that are spread out (e.g. 0...100 +
2000...2100) as two separate tbljump pieces.
This would also make it more natural to plug in other heuristics. For example, perlbmk has a switch
that looks like this:
switch uint %tmp158, label %bb336 [
uint 0, label %bb338
uint 1, label %bb338
uint 2, label %bb338
uint 3, label %bb338
uint 4, label %bb338
uint 5, label %bb338
uint 6, label %bb338
uint 7, label %bb
uint 8, label %bb338
uint 9, label %bb322
uint 10, label %bb324
uint 11, label %bb326
uint 12, label %bb328
uint 13, label %bb330
uint 14, label %bb332
uint 15, label %bb334
...
When emitted as a branch tree, the leaves end up doing lots of work to discriminate between the 0->6
cases, when they all go to the same place.
Another nice xform is to do the "shift/and" technique for switches.
-Chris
The text was updated successfully, but these errors were encountered: