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.

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

Bad time complexity for VHDL, not Verilog #1557

Closed
DigitalBrains1 opened this issue Oct 22, 2020 · 2 comments · Fixed by #1842
Closed

Bad time complexity for VHDL, not Verilog #1557

DigitalBrains1 opened this issue Oct 22, 2020 · 2 comments · Fixed by #1842
Labels

Comments

@DigitalBrains1
Copy link
Member

The file below exposes bad time complexity in the normalization phase of generating VHDL, whereas Verilog is near-instant. With a vector of length 25 as below, the numbers are:
VDHL: Clash: Normalisation took 3.052s
Verilog: Clash: Normalisation took 0.027s
More lengths:

  • 30:
    VHDL: Clash: Normalisation took 6.543s
    Verilog: Clash: Normalisation took 0.031s
  • 35:
    VHDL: Clash: Normalisation took 12.721s
    Verilog: Clash: Normalisation took 0.034s
  • 40:
    VHDL: Clash: Normalisation took 22.088s
    Verilog: Clash: Normalisation took 0.037s

This is with CλaSH master. Using 1.2.4 seems to exhibit the same problem but less pronounced.

module LongVecCompl where

import Clash.Prelude

topEntity
  :: SystemClockResetEnable
  => Signal System (Bool, Unsigned 8)
{-# NOINLINE topEntity #-}
topEntity = f (packetVecToStreamVec $(listToVecTH [1 :: Unsigned 8 .. 25]))

f :: forall n
   . (SystemClockResetEnable, KnownNat n, 1 <= n)
  => Vec n (Bool, Unsigned 8)
  -> Signal System (Bool, Unsigned 8)
f is = (is!!) <$> sel
 where
  sel :: Signal System (Index n)
  sel = register 0 $ satSucc SatWrap <$> sel

packetVecToStreamVec pkt =    map (\e -> (True, e)) (init pkt)
                           :< (False, last pkt)
@DigitalBrains1
Copy link
Member Author

The code can be further reduced while keeping the problematic behaviour:

module LongVecCompl where

import Clash.Prelude

topEntity
  :: SystemClockResetEnable
  => Signal System (Unsigned 8)
  -> Signal System (Bool, Unsigned 8)
{-# NOINLINE topEntity #-}
topEntity = fmap (packetVecToStreamVec (replicate d25 0) !!)

packetVecToStreamVec pkt =    map (\e -> (True, e)) (init pkt)
                           :< (False, last pkt)

@leonschoorl
Copy link
Member

For some reason when compiling to Verilog the map isn't evaluated.
When compiling to VHDL or SystemVerilog it is evaluated.

@alex-mckenna alex-mckenna mentioned this issue Jun 3, 2021
3 tasks
christiaanb pushed a commit that referenced this issue Jun 4, 2021
Clash was incorrectly trying to force the evaluator to evaluate
the vector argument of the indexing operator in order to get
the special primitive rule for indexing in verilog to fire,
while it only needs the index argument to be evaluated to a
literal when possible.

Fixes #1557
christiaanb pushed a commit that referenced this issue Jun 4, 2021
Clash was incorrectly trying to force the evaluator to evaluate
the vector argument of the indexing operator in order to get
the special primitive rule for indexing in verilog to fire,
while it only needs the index argument to be evaluated to a
literal when possible.

Fixes #1557
mergify bot pushed a commit that referenced this issue Jul 31, 2021
Clash was incorrectly trying to force the evaluator to evaluate
the vector argument of the indexing operator in order to get
the special primitive rule for indexing in verilog to fire,
while it only needs the index argument to be evaluated to a
literal when possible.

Fixes #1557

(cherry picked from commit 5274238)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants