Use top-level instances to solve superclasses where possible

This patch introduces a new flag `-fsolve-constant-dicts` which makes the
constraint solver solve super class constraints with available dictionaries if
possible. The flag is enabled by `-O1`.

The motivation of this patch is that the compiler can produce more efficient
code if the constraint solver used top-level instance declarations to solve
constraints that are currently solved givens and their superclasses. In
particular, as it currently stands, the compiler imposes a performance penalty
on the common use-case where superclasses are bundled together for user
convenience. The performance penalty applies to constraint synonyms as
well. This example illustrates the issue:

```
{-# LANGUAGE ConstraintKinds, MultiParamTypeClasses, FlexibleContexts #-}
module B where

class M a b where m :: a -> b

type C a b = (Num a, M a b)

f :: C Int b => b -> Int -> Int
f _ x = x + 1
```

Output without the patch, notice that we get the instance for `Num Int` by
using the class selector `p1`.

```
f :: forall b_arz. C Int b_arz => b_arz -> Int -> Int
f =
  \ (@ b_a1EB) ($d(%,%)_a1EC :: C Int b_a1EB) _ (eta1_B1 :: Int) ->
    + @ Int
      (GHC.Classes.$p1(%,%) @ (Num Int) @ (M Int b_a1EB) $d(%,%)_a1EC)
      eta1_B1
      B.f1
```

Output with the patch, nicely optimised code!

```
f :: forall b. C Int b => b -> Int -> Int
f =
  \ (@ b) _ _ (x_azg :: Int) ->
    case x_azg of { GHC.Types.I# x1_a1DP ->
    GHC.Types.I# (GHC.Prim.+# x1_a1DP 1#)
    }
```

Reviewers: simonpj, bgamari, austin

Reviewed By: simonpj

Subscribers: mpickering, rwbarton, thomie

Differential Revision: https://phabricator.haskell.org/D2714

GHC Trac Issues: #12791, #5835

1 files changed, 31 insertions, 0 deletions

diff --git a/docs/users_guide/using-optimisation.rst b/docs/users_guide/using-optimisation.rst
index 48c1e6f3bb..123d74bc8f 100644
--- a/docs/users_guide/using-optimisation.rst
+++ b/docs/users_guide/using-optimisation.rst
@@ -599,6 +599,37 @@ list.
     which they are called in this module. Note that specialisation must be
     enabled (by ``-fspecialise``) for this to have any effect.
 
+.. ghc-flag:: -fsolve-constant-dicts
+
+    :default on
+
+    When solving constraints, try to eagerly solve
+    super classes using availible dictionaries.
+
+    For example::
+
+      class M a b where m :: a -> b
+
+      type C a b = (Num a, M a b)
+
+      f :: C Int b => b -> Int -> Int
+      f _ x = x + 1
+
+    The body of `f` requires a `Num Int` instance. We could solve this
+    constraint from the context  because we have `C Int b` and that provides us
+    a
+    solution for `Num Int`. However, we can often produce much better code
+    by directly solving for an availible `Num Int` dictionary we might have at
+    hand. This removes potentially many layers of indirection and crucially
+    allows other optimisations to fire as the dictionary will be statically
+    known and selector functions can be inlined.
+
+    The optimisation also works for GADTs which bind dictionaries. If we
+    statically know which class dictionary we need then we will solve it
+    directly rather than indirectly using the one passed in at run time.
+
+
+
 .. ghc-flag:: -fstatic-argument-transformation
 
     Turn on the static argument transformation, which turns a recursive