Skip to content
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.

Sign up for GitHub

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

Jump to bottom

Callgraph after normalization contains recursive components #2839

Closed
DigitalBrains1 opened this issue Nov 3, 2024 · 3 comments · Fixed by #2844
Closed

Callgraph after normalization contains recursive components #2839

DigitalBrains1 opened this issue Nov 3, 2024 · 3 comments · Fixed by #2844

Comments

@DigitalBrains1
Copy link
Member

DigitalBrains1 commented Nov 3, 2024 •
edited
Loading

Probably related to my reproducers in #2570.

Using GHC 9.8.2, the following code:

module Rec where

import Clash.Explicit.Prelude
import Clash.Explicit.Testbench

topEntity ::
  Signal System (Unsigned 8)
topEntity = register clk noReset enableGen 100 0
 where
  cntr = register clk noReset enableGen (0 :: Unsigned 8) 0
  done = (== 100) <$> cntr
  clk = tbClockGen $ not <$> done

gives

Clash.Normalize(187): Expr belonging to bndr: topEntity_clk (:: Clock "System") remains recursive after normalization:
letrec
  v1 :: Unsigned 8
  = register# @"System" @(Unsigned 8) (removedArg @(KnownDomain "System")) (removedArg @(NFDataX (Unsigned 8))) topEntity_clk[GlobalId]
      (unsafeToReset @"System" (removedArg @(KnownDomain "System")) False)
      (Enable @"System" True)
      (fromInteger# @8 8 0)
      (fromInteger# @8 8 0)
      (fromInteger# @8 8 0)
  result :: Clock "System"
  = tbClockGen @"System" (removedArg @(KnownDomain "System")) (not (eq# @8 v1[LocalId] (fromInteger# @8 8 100)))
in result[LocalId]
Full output 
Clash: Compiling Rec.topEntity
Clash.Normalize(187): Expr belonging to bndr: topEntity_clk (:: Clock "System") remains recursive after normalization:
letrec
  v1 :: Unsigned 8
  = register# @"System" @(Unsigned 8) (removedArg @(KnownDomain "System")) (removedArg @(NFDataX (Unsigned 8))) topEntity_clk[GlobalId]
      (unsafeToReset @"System" (removedArg @(KnownDomain "System")) False)
      (Enable @"System" True)
      (fromInteger# @8 8 0)
      (fromInteger# @8 8 0)
      (fromInteger# @8 8 0)
  result :: Clock "System"
  = tbClockGen @"System" (removedArg @(KnownDomain "System")) (not (eq# @8 v1[LocalId] (fromInteger# @8 8 100)))
in result[LocalId]

<no location info>: error:
    Clash error call:
    Clash.Normalize(230): Callgraph after normalization contains following recursive components: Rec.topEntity_clk[8214565720323804629] :: Clash.Signal.Internal.Clock[8214565720323789999]
                                                "System"letrec
                                                          v1[4755801206503243778] :: Clash.Sized.Internal.Unsigned.Unsigned[8214565720323790099]
                                                                                       8
                                                          = Clash.Signal.Internal.register#
                                                              @"System"
                                                              @(Clash.Sized.Internal.Unsigned.Unsigned[8214565720323790099]
                                                                  8)
                                                              (Clash.Normalize.Primitives.removedArg
                                                                 @(Clash.Signal.Internal.KnownDomain[8214565720323790028]
                                                                     "System"))
                                                              (Clash.Normalize.Primitives.removedArg
                                                                 @(Clash.XException.NFDataX[8214565720323790111]
                                                                     (Clash.Sized.Internal.Unsigned.Unsigned[8214565720323790099]
                                                                        8)))
                                                              Rec.topEntity_clk[8214565720323804629][GlobalId]
                                                              (Clash.Signal.Internal.unsafeToReset
                                                                 @"System"
                                                                 (Clash.Normalize.Primitives.removedArg
                                                                    @(Clash.Signal.Internal.KnownDomain[8214565720323790028]
                                                                        "System"))
                                                                 <prefixName>"noReset2"
                                                                 GHC.Types.False[3891110078048108556])
                                                              <prefixName>"enableGen"
                                                              (Clash.Signal.Internal.Enable[8214565720323790215]
                                                                 @"System"
                                                                 <prefixName>"clockGen1"
                                                                 GHC.Types.True[3891110078048108586])
                                                              (Clash.Sized.Internal.Unsigned.fromInteger#
                                                                 @8
                                                                 8
                                                                 0)
                                                              (Clash.Sized.Internal.Unsigned.fromInteger#
                                                                 @8
                                                                 8
                                                                 0)
                                                              (Clash.Sized.Internal.Unsigned.fromInteger#
                                                                 @8
                                                                 8
                                                                 0)
                                                          result[4869] :: Clash.Signal.Internal.Clock[8214565720323789999]
                                                                            "System"
                                                          = Clash.Signal.Internal.tbClockGen
                                                              @"System"
                                                              (Clash.Normalize.Primitives.removedArg
                                                                 @(Clash.Signal.Internal.KnownDomain[8214565720323790028]
                                                                     "System"))
                                                              (<prefixName>"not"
                                                                 GHC.Classes.not
                                                                 (Clash.Sized.Internal.Unsigned.eq#
                                                                    @8
                                                                    v1[4755801206503243778][LocalId]
                                                                    (Clash.Sized.Internal.Unsigned.fromInteger#
                                                                       @8
                                                                       8
                                                                       100)))
    in result[4869][LocalId]
    CallStack (from HasCallStack):
      error, called at src/Clash/Normalize.hs:230:10 in clash-lib-1.9.0-inplace:Clash.Normalize
@christiaanb
Copy link
Member

After GHC desugaring we get:

topEntity
  = let { $dKnownNat_a4TQ = (NS 8##) `cast` <Co:7> :: ... } in
    let { $dNum_a4T6 = $fNumUnsigned $dKnownNat_a4TQ } in
    letrec {
      clk_a4QC
        = $ (tbClockGen $fKnownDomain"System")
            (<$>
               $fFunctorSignal
               not
               (<$>
                  $fFunctorSignal
                  (let { v_B1 = == $fEqUnsigned } in
                   let { v_B3 = fromInteger $dNum_a4T6 (IS 100#) } in
                   \ v_B2 -> v_B1 v_B2 v_B3)
                  (register
                     $fKnownDomain"System"
                     $fNFDataXUnsigned
                     clk_a4QC
                     (noReset $fKnownDomain"System")
                     enableGen
                     (fromInteger $dNum_a4T6 (IS 0#))
                     (fromInteger ($fNumSignal $dNum_a4T6) (IS 0#))))); } in
    register
      $fKnownDomain"System"
      $fNFDataXUnsigned
      clk_a4QC
      (noReset $fKnownDomain"System")
      enableGen
      (fromInteger $dNum_a4Y0 (IS 100#))
      (fromInteger ($fNumSignal $dNum_a4Y0) (IS 0#))

but then after GHC optimisation we get:

Rec {
topEntity_clk
  = tbClockGen
      $fKnownDomain"System"
      (mapSignal#
         not
         (mapSignal#
            (let {
               v_B3
                 = fromInteger# (topEntity2 `cast` <Co:7> :: ...) (IS 100#) } in
             \ v1_B2 -> eq# v1_B2 v_B3)
            (let {
               initial_X1
                 = fromInteger# (topEntity2 `cast` <Co:7> :: ...) (IS 0#) } in
             register#
               $fKnownDomain"System"
               $fNFDataXUnsigned
               topEntity_clk
               (unsafeToReset $fKnownDomain"System" noReset2)
               enableGen
               initial_X1
               initial_X1
               (signal#
                  (fromInteger# (topEntity2 `cast` <Co:7> :: ...) (IS 0#))))))
end Rec }

topEntity_initial
  = fromInteger# (topEntity1 `cast` <Co:7> :: ...) (IS 100#)

topEntity
  = register#
      $fKnownDomain"System"
      $fNFDataXUnsigned
      topEntity_clk
      (unsafeToReset $fKnownDomain"System" noReset2)
      enableGen
      topEntity_initial
      topEntity_initial
      (signal# (fromInteger# (topEntity1 `cast` <Co:7> :: ...) (IS 0#)))

The best that Clash can currently do is:

Rec.topEntity_clk[8214565720323804625] after normalization:

letrec
  v1[4755801206503243778] :: Clash.Sized.Internal.Unsigned.Unsigned[8214565720323790099]
                               8
  = Clash.Signal.Internal.register# @"System"
      @(Clash.Sized.Internal.Unsigned.Unsigned[8214565720323790099]
          8)
      (Clash.Normalize.Primitives.removedArg
         @(Clash.Signal.Internal.KnownDomain[8214565720323790028]
             "System"))
      (Clash.Normalize.Primitives.removedArg
         @(Clash.XException.NFDataX[8214565720323790111]
             (Clash.Sized.Internal.Unsigned.Unsigned[8214565720323790099]
                8)))
      Rec.topEntity_clk[8214565720323804625][GlobalId]
      c$v1_app_arg[4865][LocalId]
      <prefixName>"enableGen"
      (Clash.Signal.Internal.Enable[8214565720323790215]
         @"System"
         <prefixName>"clockGen1"
         GHC.Types.True[3891110078048108586])
      (Clash.Sized.Internal.Unsigned.fromInteger# @8 8
         0)
      (Clash.Sized.Internal.Unsigned.fromInteger# @8 8
         0)
      (Clash.Sized.Internal.Unsigned.fromInteger# @8 8
         0)
  c$v1_app_arg[4865] :: Clash.Signal.Internal.Reset[8214565720323790036]
                          "System"
  = Clash.Signal.Internal.unsafeToReset @"System"
      (Clash.Normalize.Primitives.removedArg
         @(Clash.Signal.Internal.KnownDomain[8214565720323790028]
             "System"))
      <prefixName>"noReset2"
      GHC.Types.False[3891110078048108556]
  result[4868] :: Clash.Signal.Internal.Clock[8214565720323789999]
                    "System"
  = Clash.Signal.Internal.tbClockGen @"System"
      (Clash.Normalize.Primitives.removedArg
         @(Clash.Signal.Internal.KnownDomain[8214565720323790028]
             "System"))
      (<prefixName>"not"
         GHC.Classes.not
         (Clash.Sized.Internal.Unsigned.eq# @8
            v1[4755801206503243778][LocalId]
            (Clash.Sized.Internal.Unsigned.fromInteger# @8 8
               100)))
in result[4868][LocalId]

Where the recToLetrec transformation

clash-compiler/clash-lib/src/Clash/Normalize/Transformations/Letrec.hs

Lines 266 to 270 in 10f26ff

-- | Turn a normalized recursive function, where the recursive calls only pass
-- along the unchanged original arguments, into let-recursive function. This
-- means that all recursive calls are replaced by the same variable reference as
-- found in the body of the top-level let-expression.
recToLetRec :: HasCallStack => NormRewrite
will only replace the recursive calls when they occur in the function position (and only if they are let-bound). I guess the way to go is to further special-case the ANF transformation to also let-bind global self-recursive calls. This is probably fine as the ANF transformation already has a couple of special cases anyhow.

@christiaanb
Copy link
Member

Actually, it seems ANF already does the right thing:

ANF {39}
Changes when applying rewrite to:
Clash.Signal.Internal.tbClockGen @"System"
  (Clash.Normalize.Primitives.removedArg
     @(Clash.Signal.Internal.KnownDomain[8214565720323790028]
         "System"))
  (<prefixName>"not"
     GHC.Classes.not
     (letrec
        v1[4755801206503243778] :: Clash.Sized.Internal.Unsigned.Unsigned[8214565720323790099]
                                     8
        = Clash.Signal.Internal.register# @"System"
            @(Clash.Sized.Internal.Unsigned.Unsigned[8214565720323790099]
                8)
            (Clash.Normalize.Primitives.removedArg
               @(Clash.Signal.Internal.KnownDomain[8214565720323790028]
                   "System"))
            (Clash.Normalize.Primitives.removedArg
               @(Clash.XException.NFDataX[8214565720323790111]
                   (Clash.Sized.Internal.Unsigned.Unsigned[8214565720323790099]
                      8)))
            Rec.topEntity_clk[8214565720323804625][GlobalId]
            (Clash.Signal.Internal.unsafeToReset @"System"
               (Clash.Normalize.Primitives.removedArg
                  @(Clash.Signal.Internal.KnownDomain[8214565720323790028]
                      "System"))
               <prefixName>"noReset2"
               GHC.Types.False[3891110078048108556])
            <prefixName>"enableGen"
            (Clash.Signal.Internal.Enable[8214565720323790215]
               @"System"
               <prefixName>"clockGen1"
               GHC.Types.True[3891110078048108586])
            (Clash.Sized.Internal.Unsigned.fromInteger# @8
               (GHC.Num.Natural.NS 8##)
               (GHC.Num.Integer.IS 0#))
            (Clash.Sized.Internal.Unsigned.fromInteger# @8
               (GHC.Num.Natural.NS 8##)
               (GHC.Num.Integer.IS 0#))
            (Clash.Sized.Internal.Unsigned.fromInteger# @8
               (GHC.Num.Natural.NS 8##)
               (GHC.Num.Integer.IS 0#))
     in Clash.Sized.Internal.Unsigned.eq# @8
          v1[4755801206503243778][LocalId]
          (Clash.Sized.Internal.Unsigned.fromInteger# @8
             (GHC.Num.Natural.NS 8##)
             (GHC.Num.Integer.IS 100#))))
Result:
letrec
  c$app_arg[4867] :: GHC.Types.Bool[3674937295934324744]
  = <prefixName>"not"
      GHC.Classes.not
      result[4866][LocalId]
  v1[4755801206503243778] :: Clash.Sized.Internal.Unsigned.Unsigned[8214565720323790099]
                               8
  = Clash.Signal.Internal.register# @"System"
      @(Clash.Sized.Internal.Unsigned.Unsigned[8214565720323790099]
          8)
      (Clash.Normalize.Primitives.removedArg
         @(Clash.Signal.Internal.KnownDomain[8214565720323790028]
             "System"))
      (Clash.Normalize.Primitives.removedArg
         @(Clash.XException.NFDataX[8214565720323790111]
             (Clash.Sized.Internal.Unsigned.Unsigned[8214565720323790099]
                8)))
      c$v1_app_arg[4864][LocalId]
      c$v1_app_arg[4865][LocalId]
      <prefixName>"enableGen"
      (Clash.Signal.Internal.Enable[8214565720323790215]
         @"System"
         <prefixName>"clockGen1"
         GHC.Types.True[3891110078048108586])
      (Clash.Sized.Internal.Unsigned.fromInteger# @8
         (GHC.Num.Natural.NS 8##)
         (GHC.Num.Integer.IS 0#))
      (Clash.Sized.Internal.Unsigned.fromInteger# @8
         (GHC.Num.Natural.NS 8##)
         (GHC.Num.Integer.IS 0#))
      (Clash.Sized.Internal.Unsigned.fromInteger# @8
         (GHC.Num.Natural.NS 8##)
         (GHC.Num.Integer.IS 0#))
  result[4866] :: GHC.Types.Bool[3674937295934324744]
  = Clash.Sized.Internal.Unsigned.eq# @8
      v1[4755801206503243778][LocalId]
      (Clash.Sized.Internal.Unsigned.fromInteger# @8
         (GHC.Num.Natural.NS 8##)
         (GHC.Num.Integer.IS 100#))
  c$v1_app_arg[4865] :: Clash.Signal.Internal.Reset[8214565720323790036]
                          "System"
  = Clash.Signal.Internal.unsafeToReset @"System"
      (Clash.Normalize.Primitives.removedArg
         @(Clash.Signal.Internal.KnownDomain[8214565720323790028]
             "System"))
      <prefixName>"noReset2"
      GHC.Types.False[3891110078048108556]
  c$v1_app_arg[4864] :: Clash.Signal.Internal.Clock[8214565720323789999]
                          "System"
  = Rec.topEntity_clk[8214565720323804625][GlobalId]
in Clash.Signal.Internal.tbClockGen @"System"
     (Clash.Normalize.Primitives.removedArg
        @(Clash.Signal.Internal.KnownDomain[8214565720323790028]
            "System"))
     c$app_arg[4867][LocalId]

It's the subsequent bindConstantVar transformation that "messes it up":

bindConstantVar {40}
Changes when applying rewrite to:
letrec
  c$app_arg[4867] :: GHC.Types.Bool[3674937295934324744]
  = <prefixName>"not"
      GHC.Classes.not
      result[4866][LocalId]
  v1[4755801206503243778] :: Clash.Sized.Internal.Unsigned.Unsigned[8214565720323790099]
                               8
  = Clash.Signal.Internal.register# @"System"
      @(Clash.Sized.Internal.Unsigned.Unsigned[8214565720323790099]
          8)
      (Clash.Normalize.Primitives.removedArg
         @(Clash.Signal.Internal.KnownDomain[8214565720323790028]
             "System"))
      (Clash.Normalize.Primitives.removedArg
         @(Clash.XException.NFDataX[8214565720323790111]
             (Clash.Sized.Internal.Unsigned.Unsigned[8214565720323790099]
                8)))
      c$v1_app_arg[4864][LocalId]
      c$v1_app_arg[4865][LocalId]
      <prefixName>"enableGen"
      (Clash.Signal.Internal.Enable[8214565720323790215]
         @"System"
         <prefixName>"clockGen1"
         GHC.Types.True[3891110078048108586])
      (Clash.Sized.Internal.Unsigned.fromInteger# @8
         (GHC.Num.Natural.NS 8##)
         (GHC.Num.Integer.IS 0#))
      (Clash.Sized.Internal.Unsigned.fromInteger# @8
         (GHC.Num.Natural.NS 8##)
         (GHC.Num.Integer.IS 0#))
      (Clash.Sized.Internal.Unsigned.fromInteger# @8
         (GHC.Num.Natural.NS 8##)
         (GHC.Num.Integer.IS 0#))
  result[4866] :: GHC.Types.Bool[3674937295934324744]
  = Clash.Sized.Internal.Unsigned.eq# @8
      v1[4755801206503243778][LocalId]
      (Clash.Sized.Internal.Unsigned.fromInteger# @8
         (GHC.Num.Natural.NS 8##)
         (GHC.Num.Integer.IS 100#))
  c$v1_app_arg[4865] :: Clash.Signal.Internal.Reset[8214565720323790036]
                          "System"
  = Clash.Signal.Internal.unsafeToReset @"System"
      (Clash.Normalize.Primitives.removedArg
         @(Clash.Signal.Internal.KnownDomain[8214565720323790028]
             "System"))
      <prefixName>"noReset2"
      GHC.Types.False[3891110078048108556]
  c$v1_app_arg[4864] :: Clash.Signal.Internal.Clock[8214565720323789999]
                          "System"
  = Rec.topEntity_clk[8214565720323804625][GlobalId]
in Clash.Signal.Internal.tbClockGen @"System"
     (Clash.Normalize.Primitives.removedArg
        @(Clash.Signal.Internal.KnownDomain[8214565720323790028]
            "System"))
     c$app_arg[4867][LocalId]
Result:
letrec
  c$app_arg[4867] :: GHC.Types.Bool[3674937295934324744]
  = <prefixName>"not"
      GHC.Classes.not
      result[4866][LocalId]
  v1[4755801206503243778] :: Clash.Sized.Internal.Unsigned.Unsigned[8214565720323790099]
                               8
  = Clash.Signal.Internal.register# @"System"
      @(Clash.Sized.Internal.Unsigned.Unsigned[8214565720323790099]
          8)
      (Clash.Normalize.Primitives.removedArg
         @(Clash.Signal.Internal.KnownDomain[8214565720323790028]
             "System"))
      (Clash.Normalize.Primitives.removedArg
         @(Clash.XException.NFDataX[8214565720323790111]
             (Clash.Sized.Internal.Unsigned.Unsigned[8214565720323790099]
                8)))
      Rec.topEntity_clk[8214565720323804625][GlobalId]
      c$v1_app_arg[4865][LocalId]
      <prefixName>"enableGen"
      (Clash.Signal.Internal.Enable[8214565720323790215]
         @"System"
         <prefixName>"clockGen1"
         GHC.Types.True[3891110078048108586])
      (Clash.Sized.Internal.Unsigned.fromInteger# @8
         (GHC.Num.Natural.NS 8##)
         (GHC.Num.Integer.IS 0#))
      (Clash.Sized.Internal.Unsigned.fromInteger# @8
         (GHC.Num.Natural.NS 8##)
         (GHC.Num.Integer.IS 0#))
      (Clash.Sized.Internal.Unsigned.fromInteger# @8
         (GHC.Num.Natural.NS 8##)
         (GHC.Num.Integer.IS 0#))
  result[4866] :: GHC.Types.Bool[3674937295934324744]
  = Clash.Sized.Internal.Unsigned.eq# @8
      v1[4755801206503243778][LocalId]
      (Clash.Sized.Internal.Unsigned.fromInteger# @8
         (GHC.Num.Natural.NS 8##)
         (GHC.Num.Integer.IS 100#))
  c$v1_app_arg[4865] :: Clash.Signal.Internal.Reset[8214565720323790036]
                          "System"
  = Clash.Signal.Internal.unsafeToReset @"System"
      (Clash.Normalize.Primitives.removedArg
         @(Clash.Signal.Internal.KnownDomain[8214565720323790028]
             "System"))
      <prefixName>"noReset2"
      GHC.Types.False[3891110078048108556]
in Clash.Signal.Internal.tbClockGen @"System"
     (Clash.Normalize.Primitives.removedArg
        @(Clash.Signal.Internal.KnownDomain[8214565720323790028]
            "System"))
     c$app_arg[4867][LocalId]

christiaanb added a commit that referenced this issue Nov 18, 2024
@christiaanb
Do not inline let-bound recursive calls
fd263bd 
This prevents `recToLetRec` from turning a globally recursive
function into a local let-bound recursive function which can
be synthesized to hardware.

Fixes #2839
@christiaanb christiaanb mentioned this issue Nov 18, 2024
Merged
2 tasks
christiaanb added a commit that referenced this issue Nov 18, 2024
@christiaanb
Do not inline let-bound recursive calls
f08d0ad 
This prevents `recToLetRec` from turning a globally recursive
function into a local let-bound recursive function which can
be synthesized to hardware.

Fixes #2839
mergify bot pushed a commit that referenced this issue Nov 26, 2024
@christiaanb @mergify
Do not inline let-bound recursive calls
76f4d27 
This prevents `recToLetRec` from turning a globally recursive
function into a local let-bound recursive function which can
be synthesized to hardware.

Fixes #2839

(cherry picked from commit 0072241)

# Conflicts:
#	tests/Main.hs
@mergify mergify bot mentioned this issue Nov 26, 2024
Merged
2 tasks
christiaanb added a commit that referenced this issue Nov 26, 2024
@christiaanb
Do not inline let-bound recursive calls
68b6dc7 
This prevents `recToLetRec` from turning a globally recursive
function into a local let-bound recursive function which can
be synthesized to hardware.

Fixes #2839

(cherry picked from commit 0072241)
@christiaanb
Copy link
Member

We've released v1.8.2, which includes a fix for this issue.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Do not inline let-bound recursive calls clash-lang/clash-compiler
2 participants
@christiaanb @DigitalBrains1