1 L
Eifl
type Tag = Int type Count = Int
-- Case ((Un)Balanced) Search Tree
data CaseST
= Test Ordering Int -- Divide the alternatives into two parts
CaseST
CaseST
| Range Int Int -- A constructor range we don't care about
| Default -- The default alternative
optCUBS :: [(Maybe Tag, Count)] -> CaseST
I didn't test things yet, but when I began implementing things I found out that we probably want a somewhat simpler type 
-- Case ((Un)Balanced) Search Tree
data CaseST
= Test Test Int -- Divide the alternatives into two parts
(Maybe CaseST) -- If the test succeeded
(Maybe CaseST) -- Or failed
data Test = Ne | Eq | Lt | Gt | Ge
optCUBS :: Int -> Int -> [(Maybe Tag, Count)] -> Maybe CaseST
Why? Because it turns out that when generating code we already have all the information about ranges and defaults, so we'd either have to ignore that information and risk creating an incorrect program, or we'd have to painstakenly verify whether the parameters are correct and panic if they're not. The simpler option seems not to generate that duplicate information at all...
A Nothing anywhere in a Maybe CaseST means that optCUBS doesn't have anything interesting to say about it, probably either because it doesn't have a preference for any alternative, or because there are <= 2 alternatives.
In optCUBS argument there may be exactly one Nothing, for the default-alternative.
Yups. I added something to optCUBS once more: I just realized that optCUBS will need to know what minimum and maximal values the tag may turn out to be at runtime.
-- RemiTurk - 21 Jan 2008
Comments
How do we go from constructors (EQ, or GHC.Base.EQ) to int's (required by the 1L)? -- JeielSchalkwijk - 15 Jan 2008 In GHC there is a function getTag which returns the required int. I suppose you could also just look at the data definition and take the ordering from there. I believe they start at 0, although in some cases it's a bit vague if that's really the case (True & False, for example). Anyway, that's none of your concern (hopefully). So try using getTag (if that's an option) and otherwise just number them as they appear in the data definition, starting with 0. -- MarkStobbe - 16 Jan 2008 *thinking out aloud* getTag isn't what we want: It's for things like automatically derived Eq and Enum instances, and not for retrieving tag-numbers. (As Mark said, "small types" apparently start with tag 1 instead of 0, even though getTag always starts at 0) But besides that, we are not actually interested in constructors at all. Oh, and we're not actually interested in the tick numbers for cases either *1-0 for tunnel vision*: The original case number stuff was only meant as a quick hack to be able to tell GHC to do something with some particular case expression. Just for testing. What we are interested in are the tick numbers of case expression alternatives. (Which means you should read my latest mail with some strategically inserted grains of salt.) Then, when we're going to generate C-- we'll have STG code somewhat like this:
case Expr of
0 -> Alt1 {- TICKNR 32 -}
1 -> Alt2 {- TICKNR 54 -}
5 -> Alt3 {- TICKNR 120 -}
DEF -> Alt4 {- TICKNR 326 -}
At that point, GHC needs to be able to get the counters for those numbers (say, tagCounts = [(0, 10), (1, 10000), (5, 0), (DEF, 10)]) and call a function optCUBS : TagCounts -> CaseST
So CaseST isn't actually anything like an intermediate language at all, but some internal GHC datatype It is, however, a clearly seperated subproject to define this optCUBS function.
And finally, contrary to what I said earlier, an incorrect CaseST definitely can yield incorrect results. Or most certainly even crash the compiler and/or compiled program, so the optCUBS function (that's a working name, don't really name it like that, please 
) had better be careful not to give incorrect results.
As a quick example:
data X = A Int | B | C | D | E -- Assuming this yields tags 0 .. 4
case .. of { A i -> print i ; _ -> return () }
Now, if optCUBS [(0, 100), (DEF, 0)] == Range 0 0, the compiled program will segfault if in the next program run there actually are non-A X's.
-- RemiTurk - 19 Jan 2008