... | ... | @@ -40,126 +40,125 @@ This representation saves one word and one indirection compared to the packed re |
|
|
|
|
|
## Implementation
|
|
|
|
|
|
### Computing the representation
|
|
|
|
|
|
The implementation proceeds by adding a new type for unboxed sums and then using that in the unpacking of sum types.
|
|
|
|
|
|
There are several possible representations we could chose from. Briefly they are:
|
|
|
### Core
|
|
|
|
|
|
- Store a constructor tag and the union of all the fields.
|
|
|
- Store a constructor tag and the maximum number of needed pointer and non-pointer fields.
|
|
|
|
|
|
We add a new primitive type constructor for the family of unboxed sums:
|
|
|
|
|
|
The former is simpler, especially when it comes to represent the types of the fields (since there's no aliasing), but the latter is more efficient. We will use the former for now.
|
|
|
```wiki
|
|
|
|# t_1 | ... | t_n #|_n
|
|
|
```
|
|
|
|
|
|
|
|
|
Given
|
|
|
This gets added to [compiler/prelude/TysWiredIn.hs](/trac/ghc/browser/ghc/compiler/prelude/TysWiredIn.hs), just like for unboxed tuples.
|
|
|
|
|
|
```wiki
|
|
|
data T1 = C1 x_1..x_n | C2 y_1..y_n
|
|
|
data T2 = C {-# UNPACK #-} !T1
|
|
|
```
|
|
|
|
|
|
There's an construction and elimination form.
|
|
|
|
|
|
computing the representation of `C` is quite simple. We just splice in the union of the fields of all the constructors of `T1`.
|
|
|
|
|
|
<table><tr><th> Info table pointer </th>
|
|
|
<th> T1 constructor tag </th>
|
|
|
<th> x_1..x_n </th>
|
|
|
<th> y_1..y_n
|
|
|
</th></tr></table>
|
|
|
Construction:
|
|
|
|
|
|
```wiki
|
|
|
|# x #|_i_n
|
|
|
```
|
|
|
|
|
|
(In practice we might group pointers and non-pointers fields in the actual heap object representation.)
|
|
|
|
|
|
### Populating the constructor
|
|
|
This creates the *i*th option of an n-ary sum.
|
|
|
|
|
|
|
|
|
Given
|
|
|
Elimination:
|
|
|
|
|
|
```wiki
|
|
|
data T1 = C1 x_1..x_n | C2 y_1..y_n
|
|
|
data T2 = C {-# UNPACK #-} !T1
|
|
|
case x of
|
|
|
|# x_1 #|_i_n -> ...
|
|
|
```
|
|
|
|
|
|
|
|
|
and the representation
|
|
|
This matches against the *i*th option of an n-ary sum.
|
|
|
|
|
|
### Core to STG
|
|
|
|
|
|
<table><tr><th> Info table pointer </th>
|
|
|
<th> T1 constructor tag </th>
|
|
|
<th> x_1..x_n </th>
|
|
|
<th> y_1..y_n
|
|
|
</th></tr></table>
|
|
|
|
|
|
When going to STG we need to eliminate the unboxed sums. This can be done in [compiler/simplStg/UnariseStg.hs](/trac/ghc/browser/ghc/compiler/simplStg/UnariseStg.hs), just like for tuples.
|
|
|
|
|
|
we must figure out what values to write write for e.g. the fields of `C2` when creating a `C1` value:
|
|
|
|
|
|
Given the Core function
|
|
|
|
|
|
```wiki
|
|
|
mkC (C1 x_1..x_n) = C c1_tag# x_1..x_n ???
|
|
|
f :: |# t_1 | ... | t_n #| -> ...
|
|
|
```
|
|
|
|
|
|
|
|
|
At the very least we need to write something into those y_1..y_n fields that contain pointers, or the GC will crash when traversing constructor. For now we will just write a pointer to `bottom` in those fields.
|
|
|
we convert it to a call to STG which includes the tag and the maximum number of pointer and non-pointer arguments we might need. Example:
|
|
|
|
|
|
<table><tr><th> Core </th>
|
|
|
<th> STG
|
|
|
</th></tr>
|
|
|
<tr><th>` f :: |# Int#, Bool #|_n -> ... `</th>
|
|
|
<th>` f :: Word -> Word -> Pointer -> ... `</th></tr>
|
|
|
<tr><th>` f :: |# Int#, Word# #|_n -> ... `</th>
|
|
|
<th>` f :: Word -> Word -> ... `</th></tr></table>
|
|
|
|
|
|
### Code generation
|
|
|
|
|
|
TODO This needs to be expanded on. Writing something in the unused fields in easy in the code gen, but at the core level we might need to conjure up some values of the right type to put in all fields.
|
|
|
|
|
|
### Avoiding reboxing in case statements
|
|
|
We need to make sure we generate closure types for the constructors we unpack into. This is done in [compiler/codeGen/StgCmmCon.hs](/trac/ghc/browser/ghc/compiler/codeGen/StgCmmCon.hs).
|
|
|
|
|
|
|
|
|
We use the same algorithm as is used in the Core to STG step to compute the maximum number of pointer and non-pointer fields we might need.
|
|
|
|
|
|
### Unpacking
|
|
|
|
|
|
|
|
|
Given
|
|
|
|
|
|
```wiki
|
|
|
data T1 = C1 x_1..x_n | C2 y_1..y_n
|
|
|
data T2 = C {-# UNPACK #-} !T1
|
|
|
data T1 a = Some a | None
|
|
|
data T2 a = C !(T1 a) -- Cannot UNPACK here
|
|
|
```
|
|
|
|
|
|
|
|
|
we might worried that doing
|
|
|
we generate a "worker" constructor
|
|
|
|
|
|
```wiki
|
|
|
case t2 of
|
|
|
C t1 -> case t1 of
|
|
|
C1 x_1..x_n -> ...
|
|
|
C2 y_1..y_n -> ...
|
|
|
C |# a, (# #) #|_2
|
|
|
```
|
|
|
|
|
|
|
|
|
would require that we need to allocate a `C1` or `C2` constructor just to deconstruct it again. Fortunately we should be able to avoid that because when we construct either `C1` or `C2` from the unpacked representation in `C` we'd do that we a case, like so:
|
|
|
(`(# #)` playing the role of void.)
|
|
|
|
|
|
|
|
|
We then translate the construction of `C` as follows:
|
|
|
|
|
|
```wiki
|
|
|
unpack (C tag# x_1..x_n y_1..y_n) = case tag# of
|
|
|
0# -> C1 x_1..x_n
|
|
|
1# -> C2 y_1..y_n
|
|
|
C x
|
|
|
|
|
|
===> (translates to)
|
|
|
|
|
|
case x of
|
|
|
Some y -> C (|# #|_1_2 y)
|
|
|
None -> C (|# #|_2_2 (# #))
|
|
|
```
|
|
|
|
|
|
|
|
|
This gives us
|
|
|
We then translate the elimination of `C` as follows:
|
|
|
|
|
|
```wiki
|
|
|
case t2 of
|
|
|
C t1 -> case t1 of
|
|
|
C1 x_1..x_n -> ... x_1..x_n ...
|
|
|
C2 y_1..y_n -> ... y_1..y_n ...
|
|
|
|
|
|
===>
|
|
|
|
|
|
case t2 of
|
|
|
C t1 -> case unpack t2 of
|
|
|
C1 x_1..x_n -> ... x_1..x_n ...
|
|
|
C2 y_1..y_n -> ... y_1..y_n ...
|
|
|
|
|
|
===> (inline unpack)
|
|
|
|
|
|
case t2 of
|
|
|
C tag# x_1..x_n y_1..y_n -> case (case tag# of
|
|
|
0# -> C1 x_1..x_n
|
|
|
1# -> C2 y_1..y_n) of
|
|
|
C1 x_1..x_n -> ... x_1..x_n ...
|
|
|
C2 y_1..y_n -> ... y_1..y_n ...
|
|
|
|
|
|
===> (case-of-case and case of known constructor)
|
|
|
|
|
|
case t2 of
|
|
|
C tag# x_1..x_n y_1..y_n -> case tag# of
|
|
|
0# -> ... x_1..x_n ...
|
|
|
1# -> ... y_1..y_n ...
|
|
|
``` |
|
|
\ No newline at end of file |
|
|
case e of
|
|
|
C x -> ... x ...
|
|
|
|
|
|
===> (translates to)
|
|
|
|
|
|
case e of
|
|
|
C x' ->
|
|
|
let x = case x' of
|
|
|
|# #|_1_2 y -> Some y
|
|
|
|# #|_2_2 _ -> None
|
|
|
in ... x ...
|
|
|
```
|
|
|
|
|
|
|
|
|
This above reboxing will go away, using case-of-case and case-of-known-constructor, if we scrutinize `x` again. |