SPECIALISE pragmas for derived instances

In package ghc-prim, in GHC.Classes we have

instance (Eq a) => Eq [a] where
    {-# SPECIALISE instance Eq [[Char]] #-}
    {-# SPECIALISE instance Eq [Char] #-}
    {-# SPECIALISE instance Eq [Int] #-}
    []     == []     = True
    (x:xs) == (y:ys) = x == y && xs == ys
    _xs    == _ys    = False

The SPECIALISE instance pragmas instantiate the code for these commonly-used types.

But for tuples we use deriving:

deriving instance (Eq  a, Eq  b) => Eq  (a, b)

and many more similar. There is no way to add a SPECIALISE instance pragma for a derived instance. This is bad, because they are heavily used.

You can see the lossage from messages lie

WARNING: file compiler/specialise/Specialise.lhs, line 673
    specImport discarding:
      GHC.Classes.$w$c== :: forall a b. (Eq a, Eq b) => a -> b -> a -> b -> Bool
        @ Module.Module @ Module.Module Module.$fEqModule Module.$fEqModule

which says that we will end up calling $w$c== for pairs of modules, passing dictionaries to compare the modules for equality. These messages show up when compiling the libraries if you build your stage1 compiler with -DDEBUG.

It should probably be possible to have a top-level

{-# SPECIALISE instance Eq (Int, Bool) #-}

even in another module (as we can now do for functions. To do this right, we'd need to make the code for derived methods INLINEALBE.

changed weight to 5

added Tbug Trac import labels

changed the description

Trac metadata

Trac field	Value
Type	Bug → FeatureRequest
TypeOfFailure	OtherFailure → RuntimePerformance

added deriving label

added Pnormal label

added newcomer label

I optimistically applied the newcomer label to this issue, thinking that it wouldn't be too difficult to implement—after all, derived instances are just particular kinds of instances, so it seems like it would be straightforward to make SPECIALISE instance pragmas support them. Of course, things are rarely as simple as they first appear. In particular, how should GHC match up a SPECIALISE instance pragma to a derived instance, which can appear at the top level? You might have something like this:

{-# SPECIALISE instance C (Bool, Char) #-}
deriving instance C (Int,  b)
deriving instance C (Bool, b) 

The SPECIALISE instance pragma is associated with the second deriving instance declaration, not the first. Because instances are unnamed, GHC must determine this by looking at the types involved.

The way that SPECIALISE instance pragmas for hand-written instances work is that when you write this:

instance C (Bool, b) where
  {-# SPECIALISE instance C (Bool, Char) #-}
  -- ...

GHC will unify C (Bool, Char) with C (Bool, b) (see here) to ensure that the types match up. Of course, it's clear from the nesting of the pragma within the instance that we must unify C (Bool, Char) with C (Bool, b). The situation is less clear in the derived instance case:

{-# SPECIALISE instance C (Bool, Char) #-}
deriving instance C (Int,  b)
deriving instance C (Bool, b) 

It's posible that the SPECIALISE instance pragma could match either of those instances, so the only way to know for sure would be to attempt to unify the SPECIALISE instance type with of the derived instance types until we found a match. (I'm not sure what we would do if there are multiple instances that would unify—perhaps that should constitute an error.)

I do think this could be doable for a sufficiently motivated newcomer, but do be aware that you'll need to dig a bit into how unification works to accomplish this.

added typechecker label

Here is another way that Jolly Well ought to work.

Suppose we have

deriving instance Ord b => C (Int,  b)  -- $fCInt :: forall b. Ord b => C (Int, b)
deriving instance Eq b  => C (Bool, b)  -- $fCBool :: forall b. Eq b => C (Bool b)

as you say. The comments give the type of the dictionary functions associate with the derived instances.

Now suppose we have

{-# SPECIALISE instance C (Bool, Char) #-}

Suppose that all that the {-# SPECIALISE instance ... #-} does is to produce a constraint

[W] d77 : C (Bool,Char)

The constraint solver will get to work and solve it, producing something like

d77 = $fCBool @Char $fEqChar

Now the type-class specialiser will get to work, and generate a specialised copy of $fCBool, speicalised for b=Char. Bingo. This will happen even if the SPECIALISE instance is in a different module.

As you say, we'd need to make sure that the derived methods were INLINEABLE so they too get specialised.

That seems simple enough! No messing with unification etc. One slightly tricky point is that this d77 Wanted constraint must be an Exported Id, else it'll simply be discarded as dead code before specialiser ever sees it.

marked this issue as related to #17037

Ah, I hadn't considered using the constraint solver to implement this. (That's rather different from how SPECIALISE instance pragmas for hand-written instances work, correct?)

Admittedly, this is getting into territory that even I'm not familiar with. Would you mind providing some more pointers on where someone would look to implement this? In particular:

• How does one produce a constraint of the form [W] d77 : C (Bool,Char)?
• How would one modify the constraint solver to notice d77 and specialize instances using it?
• How would one make d77 an Exported Id?
• How would one make derived methods INLINEABLE? (See also #17037.)

That's rather different from how SPECIALISE instance pragmas for hand-written instances work, correct?

Yes it is. SPECIALISE pragmas are currently handled in the desugarer. I think that might be a mistake .. there is a lot of overlap with what the main Specialiser does.

How does one produce a constraint of the form [W] d77 : C (Bool,Char)?

I think you want emitWanted.

How would one modify the constraint solver to notice d77 and specialize instances using it?

emitWanted will put it in the WantedConstraints to be solved, so the constraint solver will see it.

How would one make d77 an Exported Id?

I suppose either you'd have to change emitWanted (which makes a non-exported LocalId). Or you could take the d77 returned by emitWanted and make a new dummy binding

exported_id = d77

where exported_id is fresh, and is exported (use mkExportedLocalId).

How would one make derived methods INLINEABLE? (See also #17037.)

Actually if this is done in the same module that the instances are defined, they don't need to be INLINEABLE. The latter is needed only for cross-module specialisation