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 andidx
for indexing). It has only a fixed number of instance. -
PRepr a
is the representation type ofa
. It must be an instance ofPR
-
PA
is the class which defines conversions to and from representation types; all vectorised user-defined types are instances ofPA
-
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 aPA
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 |