Opened 2 years ago

Last modified 8 months ago

#14259 new feature request

Worker/Wrapper for sum return

Reported by: jheek Owned by:
Priority: normal Milestone:
Component: Compiler Version: 8.2.1
Keywords: UnboxedSums, CPRAnalysis, DemandAnalysis Cc: osa1, maoe, sgraf
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: #12364 Differential Rev(s):
Wiki Page:

Description

GHC version 8.2 introduces Unboxed Sum types. It would be great if the worker/wrapper transformation could make use of this new functionality.

For clarification I would expect a function like this:

maybeEven :: Int -> Maybe Int
maybeEven n = case even n of
  True  -> Just n
  False -> Nothing

to be transformed into (the core equivalent) of

maybeEven :: Int -> Maybe Int
MaybeEven (I# n#) = case workerMaybeEven n# of
  (# | x #)    -> Just x
  (# (# #) | #) -> Nothing

workerMaybeEven :: Int# -> (# (# #) | Int #)
{-# NOINLINE workerMaybeEven #-}
workerMaybeEven n# = case even (I# n#) of
  True  -> (# | I# n# #)
  False -> (# (# #) | #)

Currently the core output for the maybeEven worker is:

Main.$wmaybeEven :: Int# -> Maybe Int
Main.$wmaybeEven
  = \ (ww_s4WH :: Int#) ->
      case remInt# ww_s4WH 2# of {
        __DEFAULT -> GHC.Base.Nothing @ Int;
        0# -> GHC.Base.Just @ Int (GHC.Types.I# ww_s4WH)
      }

Change History (10)

comment:1 Changed 2 years ago by bgamari

Cc: osa1 added

Note that osa1 had some work in the direction. See Phab:D2436.

I should also mention Phab:D2424, which is also a bit of unboxed sums work that is in limbo.

osa1, perhaps you would care to say a few words about the status of these?

comment:2 Changed 2 years ago by bgamari

Keywords: UnboxedSums added

Also relevant is #12364.

comment:3 Changed 2 years ago by osa1

osa1, perhaps you would care to say a few words about the status of these?

Sure. CPR and worker/wrapper are easy to implement and I even have patches for these. (all of which should be up on phabricator)

Demand analysis on the other hand is not that easy to extend (conceptually) and implement. We had some work on this too but we couldn't finish it (after several weeks of work) and these days I unfortunately don't have time & energy to work on this ;-(

comment:4 Changed 10 months ago by maoe

Cc: maoe added

comment:5 Changed 8 months ago by andrewthad

Even only having CPR analysis (and not demand analysis) working with UnboxedSums is rather useful to me. I have some libraries where several functions look like this:

data MyExceptionType = ... -- many constructors
foo :: Int -> Int -> IO (Either MyExceptionType Int)

Crucially, foo is to large to inline, and I expect that the user is going to case on the result immediately (directly or by using something than inlines like either). If Phab:D2436 is correct, I'd be happy to rebase it and stick it behind a flag (maybe -fcpr-small-sums) that would cause this to happen for types with three or fewer data constructors (so MyExceptionType above doesn't get worker-wrappered). Hopefully, I could get this core:

foo :: Int -> Int -> IO (Either MyExceptionType Int)
fooInner :: Int# -> Int# -> State# RealWorld -> (# State# RealWorld, (# MyExceptionType | Int# #) #)

Since this does not reduce allocations in general, it has to be behind a flag. I don't know what a good name would be.

comment:6 Changed 8 months ago by simonpj

Cc: sgraf added

Sebastian is working in this territory.

comment:7 Changed 8 months ago by simonpj

Keywords: CPRAnalysis DemandAnalysis added

comment:8 Changed 8 months ago by andrewthad

Is there a merge request or differential with Sebastian's work?

comment:9 Changed 8 months ago by sgraf

Not yet, but it's high on my todo list. See https://phabricator.haskell.org/D4244#126311 for the last attempt; I'll prepare a wiki page with a proper motivation for why I think it's best to split off CPR analysis and then reimplement the nested CPR idea on top.

Actually, the CPRing sums idea is rather orthogonal, so I can probably cook that up first...

comment:10 in reply to:  9 Changed 8 months ago by sgraf

Replying to sgraf:

Actually, the CPRing sums idea is rather orthogonal, so I can probably cook that up first...

Nope, I realised that a useful CPR for sums needs CPR of depth > 1, so I'll pursue the nested CPR idea and all that comes with it first.

The wiki page for why splitting off CPR is a good thing is wiki:NestedCPR/SplitOffCPR.

Note: See TracTickets for help on using tickets.