( ESNUG 516 Item 4 ) -------------------------------------------- [12/13/12]

From: [ Jan Decaluwe of Sigasi ]
Subject: VHDL Jan warns of a subtle legacy Verilog simulator time bomb

Hi, John,

Some time ago I watched a video on FPGA design book recommendations by Jeri
Ellsworth, who is also known as the Circuit Girl. 

      

Her top pick is a book called "HDL Chip Design" by Douglas Smith, informally
know as the "Blue Book".  She describes it as a must-have.

Needless to say, I ordered it immediately.  A used copy though, because it
is an expensive beast.


Checking out the Blue Book:

The Blue Book is rather intimidating, if only for its size.  One definite
plus is that it discusses both VHDL and Verilog.  Moreover, the foreword
promises that it will be "a beacon in your quest for perfect HDL design".

While glancing over it, I got the impression that it contains a lot of
useful information.  However, my first action was to look for errors and
bad advice.  (I always do this when I get my hands on a HDL design book.)
I suppose the reason is a mixture of my own bad character and experience.
Anyway, I did not have to look very hard.

On page 174, the Doug demonstrates how to describe flip-flops.  According
to the book, a simple D flip-flop without reset would be described in
Verilog like so:

              module ff(clock, a, y);
                 input clock;
                 input a;
                 output y;
                 reg y;
 
              always @(posedge clock)
                 y = a;
 
              endmodule

In a stand-alone simulation, your Verilog simulator *may* tell you that this
is indeed a flip-flop, as *may* your synthesis tool.  However, it is not.
(At least not always.)  Only when you are lucky.


The Problem:

A flip-flop is a building block for more complex circuitry.  For example,
consider a simple two-stage delay line:

              module delay_line(clock, a, y);
                 input clock;
                 input a;
                 output y;
                 wire y1;
 
                 ff dff1(clock, a, y1);
                 ff dff2(clock, y1, y);
 
              endmodule

As presented, this model may behave as the intended two-stage delay line, or
as an unintended single stage.  There is *nothing* in Verilog to prefer one
behavior over the other.  It depends on your simulator brand.  Or version.
Or on source code order.  Or on some random, unpredictable event.

Both outcomes are equally valid.  This is Verilog nondeterminism.

To see the problem more clearly, consider the following code, which is
equivalent from the point of view of the Verilog scheduling algorithm:

              module delay_line(clock, a, y);
                 input clock;
                 input a;
                 output y;
                 reg y;
                 reg y1;
 
              always @(posedge clock)
                 y1 = a;
              always @(posedge clock)
                  y = y1;
 
              endmodule

If you run this on any Verilog simulator, and experiment with the order of
the "always" blocks, you will most likely see the issue.


Simulation Won't Help:

One problem with nondeterminism, as with bugs in general, is that it is
impossible to prove its absence by simulation.  To complicate matters
further, your simulator may hide the nondeterminism in the original example.

The reason is that some simulators, including the original Verilog simulator
and its descendants from Cadence, handle ports in a special way.  However,
don’t be misled by this.  The Verilog standard scheduling algorithm has no
special provisions for ports.  Other simulators, such as Synopsys VCS, have
exploited this characteristic by implementing "optimizations" that will
reveal the nondeterminism.

The problem with the flip-flop code is the use of a blocking assignment "="
for synchronous communication.  This coding error is made systematically
throughout the whole Doug's Blue Book.  The fix would be to use non-blocking
assignments "<=" in such cases instead.


A Verilog Simulator Time Bomb:

According to Jeri Ellsworth, the Blue Book is very popular.  This suggests
that many companies follow its coding style.  As a result, there may be a
lot of fragile Verilog legacy code out there: code that has "always worked"
but that suddenly will stop working when a new version or brand of the
Verilog simulator comes out.

I am puzzled that the Blue Book was never corrected.  The author certainly
was aware of non-blocking assignments.  In some examples Doug uses them for
their parallel semantics in a single thread of code.  Perhaps he was not
aware of their main purpose, but others could have told him.  According to
the foreword, "[the book's] accuracy has been verified by leading industry
experts".  Perhaps the issue was not yet clear to them in the first edition
of 1996.  However, my copy of the book is the ninth printing from July 2001.
It seems there was ample expertise and time available for corrections, but
for some reason they were not made.  I have no indication of later editions
that may have fixed the problem.


The Fix Is Non-Trivial:

One factor may be that the required corrections are not trivial.  We don't
want to substitute all blocking assignments by non-blocking assignments, as
their semantics are completely different.  Only the assignments used for
communication should be considered.

However, we don't want to subsitute all of those either.

For combinatorial logic, there is no issue with nondeterminism, and Verilog
designers typically prefer blocking assignments in this case.

In short, we only want to substitute assignments used for communication
and controlled by a clock edge.


The Need For Automatic Refactoring:

What I just described is a typical example of "refactoring".  By definition,
a refactoring is a code transformation intended to improve the code while
keeping its intended behavior intact.  As can be seen from this example,
interesting refactorings are often non-trivial.  No matter how desirable,
manual refactorings are often avoided because there is a significant risk
to introduce new errors in the process.

To make refactorings practical, they must be automated.

In a Verilog IDE product, a "Fix Nondeterminism" refactoring would be at the
top of my list of desired features.  It could be used to fix the Blue Book
automatically.  In the development environment, it would be available as a
code warning with an associated quick-fix.  This would avoid the issue at
the root.


Conclusion:

As you may have guessed (because my company specializes in VHDL design)
all these considerations are irrelevant for VHDL.  Any VHDL example from
the Blue Book will behave identically on any compliant VHDL simulator.

By comparison, the cost of Verilog's nondeterminism seems disproportionally
high.  Why did the Verilog language designers not avoid it like VHDL does?

    - Jan Decaluwe
      Sigasi NV                                  Ghent, Belgium

   !!!     "It's not a BUG,
  /o o\  /  it's a FEATURE!"
 (  >  )
  \ - / 
  _] [_     (jcooley 1991)