Finding the right loop breaker

This ticket reports a DPH-related optimisation problem.

Two files are attached. Repr.hs defines the type families and classes:

• PR is the class which defines basic operations (rep for replication and idx for indexing). It has only a fixed number of instance.
• PRepr a is the representation type of a. It must be an instance of PR
• PA is the class which defines conversions to and from representation types; all vectorised user-defined types are instances of PA
• repPA is an example of a generic operation: we convert the argument to its representation type, perform the PR operation on it and convert it back
• Wrap is a representation type which simply wraps a PA type; instance PA (a,b) is an example of how it is used

In Dict.hs, we define the recursive type S and its PA instance which basically looks exactly like what the vectoriser would generate. Note that we don't have to define a PR instance which is the whole point. This all works but if we look at the Core, we see that the PA dictionary of S is recursive:

Dict.$fPAS =
  Repr.D:PA
    @ Dict.S
    ($dPR_ad1 `cast` ...)
    $ctoPRepr_acn
    $cfromPRepr_acq
    $ctoArrPRepr_act
    $cfromArrPRepr_acG

$dPR_ad5 :: Repr.PR (Repr.Wrap Dict.S)
$dPR_ad5 = Repr.$fPRWrap @ Dict.S Dict.$fPAS

$dPR_ad1 [Occ=LoopBreaker]
  :: Repr.PR (GHC.Types.Double, Repr.Wrap Dict.S)
$dPR_ad1 =
  Repr.$fPR(,)
    @ GHC.Types.Double @ (Repr.Wrap Dict.S) Repr.$fPRDouble $dPR_ad5

Note that $dPR_ad1 is a loop breaker. This means that foo in Dict.hs can't be optimised properly:

Dict.foo =
  \ (s_ac0 :: Dict.S) (n_ac1 :: GHC.Types.Int) ->
    case (Repr.rep
            @ (Repr.PRepr Dict.S)
            ($dPR_ad1 `cast` ...)
            n_ac1
            (case s_ac0 of _ { Dict.S x_ac2 y_ac3 ->
             (x_ac2,
              y_ac3 `cast` ...) `cast` ...
             })) `cast` ...
    of _ { Repr.P2 xs_ac8 ds_ddJ ->
    case ds_ddJ `cast` ...
    of _ { Repr.PWrap ys_ac9 ->
    (Dict.PS xs_ac8 ys_ac9) `cast` ...
    }
    }

The (rep $dPR_ad1) call can't be resolved even though we know what it is. This is actually due to an unfortunate choice of loop breaker: $dPR_ad5 would work much better here. In general, we would perhaps like to say that we always want to pick PR (Wrap t) dictionaries as loop breakers in such cases.

Although what we'd really like is for foo itself to become a recursive function which can't happen with the current set up. I might have an idea how to do this but I need to think a bit more about it.

Trac metadata

Trac field	Value
Version	7.0.1
Type	Bug
TypeOfFailure	OtherFailure
Priority	normal
Resolution	Unresolved
Component	Compiler
Test case
Differential revisions
BlockedBy
Related
Blocking
CC
Operating system
Architecture