#4833: Finding the right loop breaker
---------------------------------+------------------------------------------
Reporter: simonpj | Owner:
Type: bug | Status: new
Priority: normal | Milestone:
Component: Compiler | Version: 7.0.1
Keywords: | Testcase:
Blockedby: | Difficulty:
Os: Unknown/Multiple | Blocking:
Architecture: Unknown/Multiple | Failure: None/Unknown
---------------------------------+------------------------------------------
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.
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/4833>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
