Opened 9 years ago

Last modified 4 years ago

#4833 new bug

Finding the right loop breaker

Reported by: simonpj Owned by:
Priority: low Milestone:
Component: Compiler Version: 7.0.1
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

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.

Attachments (2)

Repr.hs (2.2 KB) - added by simonpj 9 years ago.
Repr.hs
Dict.hs (857 bytes) - added by simonpj 9 years ago.
Dict.hs

Download all attachments as: .zip

Change History (10)

Changed 9 years ago by simonpj

Attachment: Repr.hs added

Repr.hs

Changed 9 years ago by simonpj

Attachment: Dict.hs added

Dict.hs

comment:1 Changed 9 years ago by igloo

Milestone: 7.2.1

comment:2 Changed 8 years ago by igloo

Milestone: 7.4.17.6.1
Priority: normallow

comment:3 Changed 7 years ago by igloo

Milestone: 7.6.17.6.2

comment:4 Changed 5 years ago by thoughtpolice

Milestone: 7.6.27.10.1

Moving to 7.10.1.

comment:5 Changed 5 years ago by thomie

difficulty: Unknown
Type of failure: None/UnknownRuntime performance bug

comment:6 Changed 5 years ago by thoughtpolice

Milestone: 7.10.17.12.1

Moving to 7.12.1 milestone; if you feel this is an error and should be addressed sooner, please move it back to the 7.10.1 milestone.

comment:7 Changed 4 years ago by thoughtpolice

Milestone: 7.12.18.0.1

Milestone renamed

comment:8 Changed 4 years ago by thomie

Milestone: 8.0.1
Note: See TracTickets for help on using tickets.