WebHome
- Education Page
- Literature
- Schedule
- Assignments

Center
Master Program
1 L

Eifl
<verbatim>
type Tag = Int
type Count = Int
</verbatim>

<verbatim>
-- 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
</verbatim>

I didn't test things yet, but when I began implementing things I found out that we probably want a somewhat simpler type :)
<verbatim>
-- 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
</verbatim>
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.

-- Main.RemiTurk - 21 Jan 2008

----+++ Comments

How do we go from constructors (EQ, or GHC.Base.EQ) to int's (required by the 1L)?

-- Main.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.

-- Main.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:
<verbatim>
case Expr of
  0    -> Alt1 {- TICKNR  32 -}
  1    -> Alt2 {- TICKNR  54 -}
  5    -> Alt3 {- TICKNR 120 -}
  DEF  -> Alt4 {- TICKNR 326 -}
</verbatim>
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:

<verbatim>
data X = A Int | B | C | D | E -- Assuming this yields tags 0 .. 4
case .. of { A i -> print i ; _ -> return () }
</verbatim>

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.

-- Main.RemiTurk - 19 Jan 2008

----+++ Related pages

[[HpcProfiling][Hpc Profiling]]

[[0Cubs][Optimizing CUBS]]