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
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.
Another fun thing we could do: http://www.cs.princeton.edu/software/lcc/doc/mrst.pdf
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 http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20070402/046811.html http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20070402/046812.html http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20070402/046813.html Now we don't discriminate cases 0-6 in such example. However, here much more funny will be shift-and stuff. It's planned to be next.
Next stage: http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20070409/047077.html http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20070409/047078.html http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20070409/047079.html Implemented shift-and and some other heuristics.
What is left on this old bug?