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

Jump to bottom

generate-conditional with short-circuited local expression #413

Closed
veripoolbot opened this issue Nov 4, 2011 · 11 comments
Closed

generate-conditional with short-circuited local expression #413

veripoolbot opened this issue Nov 4, 2011 · 11 comments
Labels
resolution: fixed Closed; fixed type: feature-IEEE Request to add new feature, described in IEEE 1800

Comments

@veripoolbot
Copy link
Contributor

Author Name: Jeremy Bennett (@jeremybennett)
Original Redmine Issue: 413 from https://www.veripool.org
Original Date: 2011-11-04
Original Assignee: Jeremy Bennett (@jeremybennett)

In C, conditional expressions are "short-circuited". For example @((i < MAX) && (a[i] == 0))@ will not evaluate @A[i]@ if @i@ is not less than @max@.

The same is not true of Verilog, which leaves it to the implementation to decide whether to carry out such short-circuiting. SystemVerilog removes the ambiguity to follow the same rule as C.

This means that in SystemVerilog at least the following should not cause a problem:

  #( parameter
      MAXSIZE = 8,
      ACTSIZE = 4,
      MASK = 4'b1
      )

    generate
       genvar  g;
       for (g = 0; g < MAXSIZE; g = g + 1)
         begin: gfg
            if (g < ACTSIZE && MASK[g])
            ...

Even though @ACTSIZE@ is less than @maxsize@, @Mask[g]@ will only be evaluated when @g@ is less than ACTSIZE. However Verilator gets this wrong, and throws an error trying to access @Mask[4]@ through @Mask[7]@. Other tools accept this (with Verilog of SystemVerilog).

A variant is where the boolean AND (@&&@) is replaced by a bitwise AND (@&@). This would seem to be wrong by any standard, but other tools all accept it. The problem was only found in the source when Verilator threw an error.

The attached test exercises the first case in module @foobar@, and the second in module @BarFoo@.

The following web page provides some helpful discussion of the language standard issue: http://stackoverflow.com/questions/3224553/does-verilog-support-short-circuit-evaluation.
@veripoolbot
Copy link
Contributor Author

Original Redmine Comment
Author Name: Wilson Snyder (@wsnyder)
Original Date: 2011-11-04T16:48:59Z

I knew about the side effect part related to ++ and --, but this is an interesting case. I'm surprised that & also short circuits.

What Verilator is seeing is the MASK[CONSTANT] and throwing the warning on that in isolation. It performs this check before it processes the block as part of the data type resolution, so doesn't (yet) know it won't be executed.

The fix isn't obvious, it has to process the expression before evaluating it due to Verilog's nasty width resolution rules. Maybe it needs to remember the error and only throw it later, or in the case of generates check later, but not too late as all of the constants will soon be folded in. This'll need some thought.

@veripoolbot
Copy link
Contributor Author

Original Redmine Comment
Author Name: Jeremy Bennett (@jeremybennett)
Original Date: 2011-11-15T11:14:44Z

A little more digging in the standards by a colleague found exactly how this should behave. If is section 4.2.1 in IEEE 1354-2001 (Verilog) and section 11.5.1 in IEEE 1800-2009 (SystemVerilog) "Vector bit-select and part-select addressing":

"Bit-selects extract a particular bit from a vector net, vector reg, integer variable, or time variable. The bit can be addressed using an expression. If the bit-select is out of the address bounds or the bit-select is x or z, then the value returned by the reference shall be x. The bit-select or part-select of a variable declared as real or realtime shall be considered illegal."

Thus, it would seem to be fully legal to access a vector out-of-bounds as in this case in either Verilog or SystemVerilog, and the result from this look-up must be considered x.

@veripoolbot
Copy link
Contributor Author

Original Redmine Comment
Author Name: Jeremy Bennett (@jeremybennett)
Original Date: 2012-03-09T14:51:11Z

I'm looking further into this bug. For convenience, I have created a rather simpler patch, which I attach as a diff against git HEAD (commit 0ae00fc).

@veripoolbot
Copy link
Contributor Author

Original Redmine Comment
Author Name: Wilson Snyder (@wsnyder)
Original Date: 2012-03-09T23:43:08Z

I also extended the initial test cases back when this was filed and can make them ready when/if you'd like to work on this.

@veripoolbot
Copy link
Contributor Author

Original Redmine Comment
Author Name: Jeremy Bennett (@jeremybennett)
Original Date: 2012-04-11T16:58:58Z

Here is a patch to deal with this. It only affects generated @if@, since the test in generated @for@ loops is restricted to simple comparisons at present in Verilator, while in generated @case@ blocks, the dependency is on a constant expression, with much less scope for short-circuiting.

We set a flag (@m_generate@) in @WidthVisitor@ to indicate that we are inside a generate block for which selection width errors should be ignored. We don't print the error and we don't reduce the width in this case.

When constifying the condition of a generated if, we set a flag for @ConstVisitor@ to indicate we are in the generate block. This has two effects.

  1. In @replaceConst@ we finally check widths. By this stage we know we are being used.
  2. When evaluating logical AND or OR we don't iterate the children if the generate flag is set. Instead we iterate just the first child, and if its result permits short-circuiting we need not evaluate the second child. Otherwise we continue as normal.

To make this work, I had to modify astgen. I added an optional third argument to TREEOP, which I used to indicate the visit function should not be generated automatically. I could then substitute hand-written versions for @AstLogAnd@, @astand@, @AstLogOr@ and @Astor@ to do short-circuiting. I'm not a PERL expert, but ultimately it would be good to provide this automatically through a third argument.

I've extended the test case to check all the possible short-circuiting operations.

Supplied as a git patch against current HEAD (commit 4a5e775).

@veripoolbot
Copy link
Contributor Author

Original Redmine Comment
Author Name: Wilson Snyder (@wsnyder)
Original Date: 2012-04-12T10:56:31Z

Great, I'm still digesting! I need to think about how to get what you want with the astgen visitors without actually overriding the function as I don't want to maintain a hand written visitor.

@veripoolbot
Copy link
Contributor Author

Original Redmine Comment
Author Name: Wilson Snyder (@wsnyder)
Original Date: 2012-04-14T11:53:46Z

I added to git a t_dpi_shortcircuit test. It's currently disabled.

I also added a patch to do the emacs indentation part of this patch.

I'd like your thoughts on the overall approach, since ideally the solution wouldn't care about parameters, because we'll want short circuiting to apply to everything not just parmameters eventually. One alternative might be to use V3Simulate.h to determine what to execute.

I'll email some general thoughts on the patch itself.

@veripoolbot
Copy link
Contributor Author

Original Redmine Comment
Author Name: Jeremy Bennett (@jeremybennett)
Original Date: 2012-04-15T17:52:43Z

Updated patch, which has a modified TREEOP to generate short-circuited visitors. Various improvements to the C++ code as suggested by email.

For general short-circuiting, the C compiler will presumably do this, even if we do not. However we may be able to generate smaller programs if we can short-circuit constants within Verilator to prune unused code. Potentially that opens up other optimizations (pruning code often does).

I haven't tried the DPI short-circuit test yet.

@veripoolbot
Copy link
Contributor Author

Original Redmine Comment
Author Name: Jeremy Bennett (@jeremybennett)
Original Date: 2012-04-19T17:11:49Z

Some more changes, following email discussion. This is now strictly IEEE 1800-2009. Short-circuiting is used only for && || -> and ?:, and is applied both to generate IF statements and expressions in general.

I've added a new set of tests to check that this fails when it should. For example with bitwise & and | and where there are selection width errors remaining after short-circuiting.

Attached as a tar and bzipped git format-patch against current HEAD (commit 7eb407f)

@veripoolbot
Copy link
Contributor Author

Original Redmine Comment
Author Name: Wilson Snyder (@wsnyder)
Original Date: 2012-04-20T02:55:09Z

I ran "make test" and it showed two failures t_lint_unused_bad and t_lint_syncasyncnet_bad, related to short circuiting suppressing variable unused warnings. To match what GCC and other tools do, "0 && a" should still consider "a" as a used variable. I realized though this was broken related to my last set of suggestions, and just needed to include m_doVConst in astgen.

Everything is merged in, so please "git pull" and start from the mainline before sending other patches, thanks. (BTW your using a github account would be useful.)

Fixed in git towards 3.840.

@veripoolbot
Copy link
Contributor Author

Original Redmine Comment
Author Name: Wilson Snyder (@wsnyder)
Original Date: 2012-07-31T22:54:32Z

In 3.840.

@veripoolbot veripoolbot added resolution: fixed Closed; fixed type: feature-IEEE Request to add new feature, described in IEEE 1800 labels Dec 22, 2019
@veripoolbot veripoolbot mentioned this issue Dec 22, 2019
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
resolution: fixed Closed; fixed type: feature-IEEE Request to add new feature, described in IEEE 1800
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@veripoolbot