New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Exception: CLaSH.Netlist(285): Unknown function: a3_227 #109

Closed
ggreif opened this Issue Jan 7, 2016 · 11 comments

Comments

Projects
None yet
2 participants
@ggreif
Contributor

ggreif commented Jan 7, 2016

While compiling my CAM design I found two CLaSH bugs. This is number one. I get

Loading dependencies took 0.449427s
Applied 268 transformations
Normalisation took 0.819746s
*** Exception: CLaSH.Netlist(285): Unknown function: a3_227

when compiling the attached file.

Writing the local function both with a catch-all pattern removes the problem.
CAM.txt

@christiaanb christiaanb added the bug label Jan 7, 2016

@christiaanb

This comment has been minimized.

Show comment
Hide comment
@christiaanb

christiaanb Jan 7, 2016

Contributor

I'm surprised your code works at all: you're storing functions in registers, right? I don't think the CLaSH compiler can handle that...

Contributor

christiaanb commented Jan 7, 2016

I'm surprised your code works at all: you're storing functions in registers, right? I don't think the CLaSH compiler can handle that...

@ggreif

This comment has been minimized.

Show comment
Hide comment
@ggreif

ggreif Jan 7, 2016

Contributor

Funny thing, it works! Just uncomment that line and it even generates VHDL. The power of defunctionalisation? Or rather the compiler detects that the signal can be eliminated because it is applied to another signal.

Contributor

ggreif commented Jan 7, 2016

Funny thing, it works! Just uncomment that line and it even generates VHDL. The power of defunctionalisation? Or rather the compiler detects that the signal can be eliminated because it is applied to another signal.

@christiaanb

This comment has been minimized.

Show comment
Hide comment
@christiaanb

christiaanb Jan 7, 2016

Contributor

I wonder if it is meaning-preserving.... does the VHDL even work?

Contributor

christiaanb commented Jan 7, 2016

I wonder if it is meaning-preserving.... does the VHDL even work?

@ggreif

This comment has been minimized.

Show comment
Hide comment
@ggreif

ggreif Jan 8, 2016

Contributor

I'll test it tomorrow.

Em sexta-feira, 8 de janeiro de 2016, Christiaan Baaij <
notifications@github.com> escreveu:

I wonder if it is meaning-preserving.... does the VHDL even work?


Reply to this email directly or view it on GitHub
#109 (comment)
.

Contributor

ggreif commented Jan 8, 2016

I'll test it tomorrow.

Em sexta-feira, 8 de janeiro de 2016, Christiaan Baaij <
notifications@github.com> escreveu:

I wonder if it is meaning-preserving.... does the VHDL even work?


Reply to this email directly or view it on GitHub
#109 (comment)
.

@ggreif

This comment has been minimized.

Show comment
Hide comment
@ggreif

ggreif Jan 8, 2016

Contributor

I get may errors from Vivado like this:

[Synth 8-2139] illegal identifier : __VOID__ ["vhdl/CAM/CAM_cam_zdscam_1.vhdl":123]

when synthesizing :vhdl from this:

cam :: forall k v n . (BlockRamAssoc k v, KnownNat n, KnownNat (2 ^ n)) => (k -> Unsigned n) -> Signal (Either k (k, v)) -> Signal (Maybe v)
cam f move = condUpdater ram out wr hash
  where ram = condSigWrite $ maybeWrite $ {- BUG #2 FIXME: readNew -}id (blockRamPow2 (initBuckets (undefined::k) (undefined::v)))
        out = const Nothing `register` (findColumn <$> key)
        wr :: Signal (Maybe v -> Maybe (Bucket k v -> Bucket k v))
        wr = liftA both (Nothing `register` pair)
        both (Just kv) Nothing = Just (augmentBucket kv)
        both _ _ = Nothing -- WORKS!
        --both _ Just{} = Nothing
        --both Nothing _ = Nothing -- BUG #1 : *** Exception: CLaSH.Netlist(285): Unknown function: a3_227
        hash :: Signal (Unsigned n)
        hash = f <$> key
        key = (\case Left k -> k; Right (k, _) -> k) <$> move
        pair = (\case Left _ -> Nothing; Right p -> Just p) <$> move
Contributor

ggreif commented Jan 8, 2016

I get may errors from Vivado like this:

[Synth 8-2139] illegal identifier : __VOID__ ["vhdl/CAM/CAM_cam_zdscam_1.vhdl":123]

when synthesizing :vhdl from this:

cam :: forall k v n . (BlockRamAssoc k v, KnownNat n, KnownNat (2 ^ n)) => (k -> Unsigned n) -> Signal (Either k (k, v)) -> Signal (Maybe v)
cam f move = condUpdater ram out wr hash
  where ram = condSigWrite $ maybeWrite $ {- BUG #2 FIXME: readNew -}id (blockRamPow2 (initBuckets (undefined::k) (undefined::v)))
        out = const Nothing `register` (findColumn <$> key)
        wr :: Signal (Maybe v -> Maybe (Bucket k v -> Bucket k v))
        wr = liftA both (Nothing `register` pair)
        both (Just kv) Nothing = Just (augmentBucket kv)
        both _ _ = Nothing -- WORKS!
        --both _ Just{} = Nothing
        --both Nothing _ = Nothing -- BUG #1 : *** Exception: CLaSH.Netlist(285): Unknown function: a3_227
        hash :: Signal (Unsigned n)
        hash = f <$> key
        key = (\case Left k -> k; Right (k, _) -> k) <$> move
        pair = (\case Left _ -> Nothing; Right p -> Just p) <$> move
@christiaanb

This comment has been minimized.

Show comment
Hide comment
@christiaanb

christiaanb Jan 8, 2016

Contributor

Yeah, that basically means that the compiler wasn't able to translate to VHDL. The compiler should error out instead of generating bogus VHDL.

Also, the compiler doesn't actually have a defunctionalisation pass. It has a higher-order specialization pass to get rid of the higher-order values. I guess I should also add a defunctionalisation pass to get rid of the remaining higher-order values.

Contributor

christiaanb commented Jan 8, 2016

Yeah, that basically means that the compiler wasn't able to translate to VHDL. The compiler should error out instead of generating bogus VHDL.

Also, the compiler doesn't actually have a defunctionalisation pass. It has a higher-order specialization pass to get rid of the higher-order values. I guess I should also add a defunctionalisation pass to get rid of the remaining higher-order values.

@ggreif

This comment has been minimized.

Show comment
Hide comment
@ggreif

ggreif Jan 8, 2016

Contributor

Good to hear that this is not a fundamental problem. This is a great
paper w.r.t. defunctionalisation:
http://www.diku.dk/~paba/pubs/entries/hutton16wf.html

I would love to be able to have signals of function type around. That
is where the power of FP comes from, after all!

I have a free weekend ahead, I can sink my teeth in it, too.

On 1/8/16, Christiaan Baaij notifications@github.com wrote:

Yeah, that basically means that the compiler wasn't able to translate to
VHDL. The compiler should error out instead of generating bogus VHDL.

Also, the compiler doesn't actually have a defunctionalisation pass. It has
a higher-order specialization pass to get rid of the higher-order values. I
guess I should also add a defunctionalisation pass to get rid of the
remaining higher-order values.


Reply to this email directly or view it on GitHub:
#109 (comment)

Contributor

ggreif commented Jan 8, 2016

Good to hear that this is not a fundamental problem. This is a great
paper w.r.t. defunctionalisation:
http://www.diku.dk/~paba/pubs/entries/hutton16wf.html

I would love to be able to have signals of function type around. That
is where the power of FP comes from, after all!

I have a free weekend ahead, I can sink my teeth in it, too.

On 1/8/16, Christiaan Baaij notifications@github.com wrote:

Yeah, that basically means that the compiler wasn't able to translate to
VHDL. The compiler should error out instead of generating bogus VHDL.

Also, the compiler doesn't actually have a defunctionalisation pass. It has
a higher-order specialization pass to get rid of the higher-order values. I
guess I should also add a defunctionalisation pass to get rid of the
remaining higher-order values.


Reply to this email directly or view it on GitHub:
#109 (comment)

@ggreif

This comment has been minimized.

Show comment
Hide comment
@ggreif

ggreif Jan 8, 2016

Contributor

But the original bug is not exactly the __VOID__ issue. There is something subtle going on with the three-clause pattern match. Both may be related, though.

Contributor

ggreif commented Jan 8, 2016

But the original bug is not exactly the __VOID__ issue. There is something subtle going on with the three-clause pattern match. Both may be related, though.

@christiaanb

This comment has been minimized.

Show comment
Hide comment
@christiaanb

christiaanb Jan 8, 2016

Contributor

They are related, but I don't have the time to explain as I'm attending the Dutch functional programming day. I'll elaborate tomorrow.

Contributor

christiaanb commented Jan 8, 2016

They are related, but I don't have the time to explain as I'm attending the Dutch functional programming day. I'll elaborate tomorrow.

@christiaanb

This comment has been minimized.

Show comment
Hide comment
@christiaanb

christiaanb Jan 10, 2016

Contributor

OK, so the haskell:

both (Just kv) Nothing = Just (augmentBucket kv)
both _ _ = Nothing

would be desugared to the following Core (by GHC):

both_a4XO
  :: forall t_a6bI k_a6bJ v_a6bK.
     BlockRamAssoc k_a6bJ v_a6bK =>
     Maybe (k_a6bJ, v_a6bK)
     -> Maybe t_a6bI
     -> Maybe (Bucket k_a6bJ v_a6bK -> Bucket k_a6bJ v_a6bK)
[LclId, Str=DmdType]
both_a4XO =
  \ (@ t_a6bN)
    (@ k_a6bO)
    (@ v_a6bP)
    ($dBlockRamAssoc_a6bQ :: BlockRamAssoc k_a6bO v_a6bP)
    (ds_dafp :: Maybe (k_a6bO, v_a6bP))
    (ds_dafq :: Maybe t_a6bN) ->
    let {
      fail_dafr
        :: GHC.Prim.Void#
           -> Maybe (Bucket k_a6bO v_a6bP -> Bucket k_a6bO v_a6bP)
      [LclId, Str=DmdType]
      fail_dafr =
        \ _ [Occ=Dead, OS=OneShot] ->
          GHC.Base.Nothing
            @ (Bucket k_a6bO v_a6bP -> Bucket k_a6bO v_a6bP) } in
    case ds_dafp of _ [Occ=Dead] {
      __DEFAULT -> fail_dafr GHC.Prim.void#;
      Just kv_a4YA ->
        case ds_dafq of _ [Occ=Dead] {
          __DEFAULT -> fail_dafr GHC.Prim.void#;
          Nothing ->
            GHC.Base.Just
              @ (Bucket k_a6bO v_a6bP -> Bucket k_a6bO v_a6bP)
              (augmentBucket @ k_a6bO @ v_a6bP $dBlockRamAssoc_a6bQ kv_a4YA)

Whilst the following Haskell:

 both (Just kv) Nothing = Just (augmentBucket kv)
 both _ Just{} = Nothing
 both Nothing _ = Nothing

Seems to be desugared to:

both_a4WP =
  \ (@ t_a6bb)
    (@ k_a6bc)
    (@ v_a6bd)
    ($dBlockRamAssoc_a6be :: BlockRamAssoc k_a6bc v_a6bd)
    (ds_daeN :: Maybe (k_a6bc, v_a6bd))
    (ds_daeO :: Maybe t_a6bb) ->
    let {
      fail_daeU
        :: GHC.Prim.Void#
           -> Maybe (Bucket k_a6bc v_a6bd -> Bucket k_a6bc v_a6bd)
      [LclId, Str=DmdType]
      fail_daeU =
        \ _ [Occ=Dead, OS=OneShot] ->
          case ds_daeO of _ [Occ=Dead] {
            __DEFAULT ->
              (\ _ [Occ=Dead, OS=OneShot] ->
                 case ds_daeN of _ [Occ=Dead] {
                   __DEFAULT ->
                     (\ _ [Occ=Dead, OS=OneShot] ->
                        Control.Exception.Base.patError
                          @ (Maybe (Bucket k_a6bc v_a6bd -> Bucket k_a6bc v_a6bd))
                          "examples/CAM.hs:(69,9)-(72,32)|function both"#)
                       GHC.Prim.void#;
                   Nothing ->
                     GHC.Base.Nothing @ (Bucket k_a6bc v_a6bd -> Bucket k_a6bc v_a6bd)
                 })
                GHC.Prim.void#;
            Just _ [Occ=Dead] ->
              GHC.Base.Nothing @ (Bucket k_a6bc v_a6bd -> Bucket k_a6bc v_a6bd)
          } } in
    case ds_daeN of _ [Occ=Dead] {
      __DEFAULT -> fail_daeU GHC.Prim.void#;
      Just kv_a4XG ->
        case ds_daeO of _ [Occ=Dead] {
          __DEFAULT -> fail_daeU GHC.Prim.void#;
          Nothing ->
            GHC.Base.Just
              @ (Bucket k_a6bc v_a6bd -> Bucket k_a6bc v_a6bd)
              (augmentBucket @ k_a6bc @ v_a6bd $dBlockRamAssoc_a6be kv_a4XG)

So the problem with the second version is the patError, through a series of transformation, CLaSH ends up with the following case-statement which it can (currently) not reduce any further:

case Control.Exception.Base.patError @ (Maybe (Bucket k_a6bc v_a6bd -> Bucket k_a6bc v_a6bd)) of
  ....

As a result, we we end up with a local (let-bound) function in this particular case (which we didn't get in the fall-through version of both). This is then the error you eventually see, a local (let-bound) function is applied, and the netlist generator is going to look for this function in the global namespace, because it operates under the assumption that all local functions have been eliminated.

Does it make sense?

So, having seen this bug I know what to do to fix it: if see any form of error as the subject/scrutinee of a case-expression, I replace that entire case-expression by the error. I'll fix it tomorrow when I'm back in the office. Of course, this doesn't fix the problem that CLaSH cannot handle functions stored inside a register, for that we'll still need a proper defunctionalisation pass.

Contributor

christiaanb commented Jan 10, 2016

OK, so the haskell:

both (Just kv) Nothing = Just (augmentBucket kv)
both _ _ = Nothing

would be desugared to the following Core (by GHC):

both_a4XO
  :: forall t_a6bI k_a6bJ v_a6bK.
     BlockRamAssoc k_a6bJ v_a6bK =>
     Maybe (k_a6bJ, v_a6bK)
     -> Maybe t_a6bI
     -> Maybe (Bucket k_a6bJ v_a6bK -> Bucket k_a6bJ v_a6bK)
[LclId, Str=DmdType]
both_a4XO =
  \ (@ t_a6bN)
    (@ k_a6bO)
    (@ v_a6bP)
    ($dBlockRamAssoc_a6bQ :: BlockRamAssoc k_a6bO v_a6bP)
    (ds_dafp :: Maybe (k_a6bO, v_a6bP))
    (ds_dafq :: Maybe t_a6bN) ->
    let {
      fail_dafr
        :: GHC.Prim.Void#
           -> Maybe (Bucket k_a6bO v_a6bP -> Bucket k_a6bO v_a6bP)
      [LclId, Str=DmdType]
      fail_dafr =
        \ _ [Occ=Dead, OS=OneShot] ->
          GHC.Base.Nothing
            @ (Bucket k_a6bO v_a6bP -> Bucket k_a6bO v_a6bP) } in
    case ds_dafp of _ [Occ=Dead] {
      __DEFAULT -> fail_dafr GHC.Prim.void#;
      Just kv_a4YA ->
        case ds_dafq of _ [Occ=Dead] {
          __DEFAULT -> fail_dafr GHC.Prim.void#;
          Nothing ->
            GHC.Base.Just
              @ (Bucket k_a6bO v_a6bP -> Bucket k_a6bO v_a6bP)
              (augmentBucket @ k_a6bO @ v_a6bP $dBlockRamAssoc_a6bQ kv_a4YA)

Whilst the following Haskell:

 both (Just kv) Nothing = Just (augmentBucket kv)
 both _ Just{} = Nothing
 both Nothing _ = Nothing

Seems to be desugared to:

both_a4WP =
  \ (@ t_a6bb)
    (@ k_a6bc)
    (@ v_a6bd)
    ($dBlockRamAssoc_a6be :: BlockRamAssoc k_a6bc v_a6bd)
    (ds_daeN :: Maybe (k_a6bc, v_a6bd))
    (ds_daeO :: Maybe t_a6bb) ->
    let {
      fail_daeU
        :: GHC.Prim.Void#
           -> Maybe (Bucket k_a6bc v_a6bd -> Bucket k_a6bc v_a6bd)
      [LclId, Str=DmdType]
      fail_daeU =
        \ _ [Occ=Dead, OS=OneShot] ->
          case ds_daeO of _ [Occ=Dead] {
            __DEFAULT ->
              (\ _ [Occ=Dead, OS=OneShot] ->
                 case ds_daeN of _ [Occ=Dead] {
                   __DEFAULT ->
                     (\ _ [Occ=Dead, OS=OneShot] ->
                        Control.Exception.Base.patError
                          @ (Maybe (Bucket k_a6bc v_a6bd -> Bucket k_a6bc v_a6bd))
                          "examples/CAM.hs:(69,9)-(72,32)|function both"#)
                       GHC.Prim.void#;
                   Nothing ->
                     GHC.Base.Nothing @ (Bucket k_a6bc v_a6bd -> Bucket k_a6bc v_a6bd)
                 })
                GHC.Prim.void#;
            Just _ [Occ=Dead] ->
              GHC.Base.Nothing @ (Bucket k_a6bc v_a6bd -> Bucket k_a6bc v_a6bd)
          } } in
    case ds_daeN of _ [Occ=Dead] {
      __DEFAULT -> fail_daeU GHC.Prim.void#;
      Just kv_a4XG ->
        case ds_daeO of _ [Occ=Dead] {
          __DEFAULT -> fail_daeU GHC.Prim.void#;
          Nothing ->
            GHC.Base.Just
              @ (Bucket k_a6bc v_a6bd -> Bucket k_a6bc v_a6bd)
              (augmentBucket @ k_a6bc @ v_a6bd $dBlockRamAssoc_a6be kv_a4XG)

So the problem with the second version is the patError, through a series of transformation, CLaSH ends up with the following case-statement which it can (currently) not reduce any further:

case Control.Exception.Base.patError @ (Maybe (Bucket k_a6bc v_a6bd -> Bucket k_a6bc v_a6bd)) of
  ....

As a result, we we end up with a local (let-bound) function in this particular case (which we didn't get in the fall-through version of both). This is then the error you eventually see, a local (let-bound) function is applied, and the netlist generator is going to look for this function in the global namespace, because it operates under the assumption that all local functions have been eliminated.

Does it make sense?

So, having seen this bug I know what to do to fix it: if see any form of error as the subject/scrutinee of a case-expression, I replace that entire case-expression by the error. I'll fix it tomorrow when I'm back in the office. Of course, this doesn't fix the problem that CLaSH cannot handle functions stored inside a register, for that we'll still need a proper defunctionalisation pass.

christiaanb added a commit that referenced this issue Sep 6, 2018

Ghc821 (#109)
* Disable worker/wrapper transformation globally in GHC 8.2

GHC 8.2 performs worker/wrapper on NONLINE-marked functions,
which will mark the wrapper $w as NOINLINE as well. Consquently,
all of CLaSH' primitive have become invisible to the CLaSH
compiler.

* Up criterion upper bound
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment