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.

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

Open
lattner opened this issue Sep 27, 2006 · 7 comments
Open

sdisel switch lowering can be improved #1298

lattner opened this issue Sep 27, 2006 · 7 comments
Labels
bugzilla Issues migrated from bugzilla code-quality confirmed Verified by a second party llvm:codegen llvm:SelectionDAG SelectionDAGISel as well

Comments

@lattner
Copy link
Collaborator

lattner commented Sep 27, 2006

Bugzilla Link 926
Version 1.8
OS All
CC @asl,@lattner

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:

    cmpl $6, %eax
    jl LBB1_20      #entry

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

@isanbard
Copy link
Contributor

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
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20061016/038760.html

The more interesting bit is yet to be done.

@lattner
Copy link
Collaborator Author

lattner commented Nov 29, 2006

Another fun thing we could do:
http://www.cs.princeton.edu/software/lcc/doc/mrst.pdf

@asl
Copy link
Collaborator

asl commented Feb 28, 2007

@asl
Copy link
Collaborator

asl commented Mar 20, 2007

@asl
Copy link
Collaborator

asl commented Apr 5, 2007

@lattner
Copy link
Collaborator Author

lattner commented Dec 2, 2010

What is left on this old bug?

@llvmbot llvmbot transferred this issue from llvm/llvm-bugzilla-archive Dec 3, 2021
@llvmbot llvmbot added the confirmed Verified by a second party label Jan 26, 2022
kitano-metro pushed a commit to RIKEN-RCCS/llvm-project that referenced this issue Feb 14, 2023
kitano-metro pushed a commit to RIKEN-RCCS/llvm-project that referenced this issue Feb 14, 2023
llvm#1298 スケッドモデルをオリジナルに戻す

See merge request a64fx-swpl/llvm-project!27
@arsenm arsenm added the llvm:SelectionDAG SelectionDAGISel as well label Aug 17, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bugzilla Issues migrated from bugzilla code-quality confirmed Verified by a second party llvm:codegen llvm:SelectionDAG SelectionDAGISel as well
Projects
None yet
Development

No branches or pull requests

5 participants