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

Support short-circuiting #487

Closed
veripoolbot opened this issue Apr 23, 2012 · 15 comments · Fixed by #4437
Closed

Support short-circuiting #487

veripoolbot opened this issue Apr 23, 2012 · 15 comments · Fixed by #4437
Labels
effort: weeks Expect this issue to require weeks or more of invested effort to resolve 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: 487 from https://www.veripool.org


Verilog 2001 (and I believe 2005) allows considerable flexibility in short-circuiting. IEEE 1364-2001, section 4.1.4 states:

"The operators shall follow the associativity rules while evaluating an expression as described in 4.1.2. How-
ever, if the final result of an expression can be determined early, the entire expression need not be evaluated."

The standard does not make the precise circumstances explicit, but the example used is based on bitwise-AND where the first operand evaluates to zero. I understand that VCS short-circuits evaluation of bitwise AND and bitwise OR.

I have written a patch with regression test to implement this when the Verilator language specified is Verilog, but not SystemVerilog. This is an extension of the work in Issue 413, which implements short-circuiting compliant with the SystemVerilog IEEE 1800-2009 standard. Please pull the changes from:

https://github.com/jeremybennett/verilator/tree/v2k1-short-circuit

@veripoolbot
Copy link
Contributor Author


Original Redmine Comment
Author Name: Wilson Snyder (@wsnyder)
Original Date: 2012-04-23T23:16:15Z


Isn't short-circuiting optional in Verilog-2001? Either way I do not believe Verilator should do anything different WRT this in Verilog vs SystemVerilog unless the spec forces it, as that will just confuse people.

Anyhow the big problem is test case currently fails on both VCS and NC. (And fails identically with either SystemVerilog or Verilog 2005 mode.)

Also minor issues with the specific patch; first the test.pl should use verilator_flags2 not v_flags2 as the flags are verilator specific, and second testing the --language switch is incorrect; --language is just the default language if not specified; it can be overridden on a file-by-file basis, so the best thing to do would be to put the language setting into the FileLine flags, then test it at the appropriate point. (This hasn't been needed yet as there isn't anything that simulates differently.)

@veripoolbot
Copy link
Contributor Author


Original Redmine Comment
Author Name: Jeremy Bennett (@jeremybennett)
Original Date: 2012-04-24T08:15:15Z


I have to confess that I don't have a copy of the 2005 standard, but the 2001 standard definitely leaves it up to the user. It may be that 2005 tightened things up.

I have an example which passes with VCS, but fails with Verilator. Since this is commercially confidential, I extracted the test case, which passes with Icarus Verilog, but fails with Verilator. I don't routinely have access to VCS - does it pass with VCS if you specify 2001 as the Verilog version? Maybe I need to tighten down the language variant test.

My objective was that synthesizable code that is acceptable to VCS (or for that matter any major simulator) should also be OK with Verilator. Maybe I should make this issue a warning about short-circuiting that can be turned off?

I've changed the code on github to use verilator_flags2. I'll work on making the language test per module as you suggest - I see the comment in the definition of class FileLine about doing this.

@veripoolbot
Copy link
Contributor Author


Original Redmine Comment
Author Name: Wilson Snyder (@wsnyder)
Original Date: 2012-04-24T10:49:05Z


VCS fails with $stop at line 88. NC complains about bit-select out of bounds on 67 as the AND isn't short circuited. Both are identical in v2001/2005/SV modes, emphasizing my point that changing behavior on the language isn't appropriate.

@veripoolbot
Copy link
Contributor Author


Original Redmine Comment
Author Name: Jeremy Bennett (@jeremybennett)
Original Date: 2012-04-24T12:25:46Z


Hmmm. Things get more and more messy.

VCS appears to do bitwise constant folding, but evidently gets the wrong answer for bitwise OR (the $stop should never be executed). It also seems that for SystemVerilog it is not standards compliant (short-circuiting bitwise AND is explicitly not allowed).

NC doesn't do constant folding. Icarus Verilog does constant folding and seems to get it right in both cases.

The original code I have only uses bitwise AND short-circuiting and the designers use VCS, so that explains why it works for them. The Verilog 2001 standard is not helpful by using bitwise AND as the example of where short-circuiting could be used - presumably why VCS does it.

I have a ton of legacy code which uses this, and with a very strong prohibition on not modifying the RTL. Should I add a new option to offer bitwise short-circuiting?

@veripoolbot
Copy link
Contributor Author


Original Redmine Comment
Author Name: Wilson Snyder (@wsnyder)
Original Date: 2012-04-24T12:44:40Z


Can you post a test that shows what you just said; namely it passes in VCS and fails in NC? (Warnings not being considered failures, for this purpose.)

@veripoolbot
Copy link
Contributor Author


Original Redmine Comment
Author Name: Jeremy Bennett (@jeremybennett)
Original Date: 2012-04-24T13:10:53Z


As noted, I don't have VCS to check this, but I have reduced the test to just using bitwise-AND. This passes in Icarus Verilog. From your previous comment, I believe this should pass with VCS and fail with a range check with NC. With --verbose, the output from both Verilator is:

Bitwise AND generate if MASK [0] = 1
Bitwise AND generate if MASK [1] = 1
Bitwise AND generate if MASK [0] = 1
Bitwise AND generate if MASK [1] = 1
*-* All Finished *-*

and from IV is:

Bitwise AND generate if MASK [1] = 1
Bitwise AND generate if MASK [0] = 1
Bitwise AND generate if MASK [0] = 1
Bitwise AND generate if MASK [1] = 1
*-* All Finished *-*

Identical, apart from the order in which parallel always blocks are evaluated.

New test t_gen_cond_v2k1_bitrange_and.{pl,v} pushed to GitHub, and attached here for convenience.

@veripoolbot
Copy link
Contributor Author


Original Redmine Comment
Author Name: Jeremy Bennett (@jeremybennett)
Original Date: 2012-04-24T13:13:49Z


Sorry - I should have added, that is Verilator with my patch to enable bitwise AND short-circuiting with Verilog. It fails with standard Verilator as follows:

%Error: t/t_gen_cond_v2k1_bitrange_and.v:67: Selection index out of range: 2:2 outside 1:0
%Error: t/t_gen_cond_v2k1_bitrange_and.v:67: Selection index out of range: 3:3 outside 1:0
%Error: Exiting due to 2 error(s)

@veripoolbot
Copy link
Contributor Author


Original Redmine Comment
Author Name: Wilson Snyder (@wsnyder)
Original Date: 2012-04-24T13:22:43Z


NC does print a warning, but then passes and VCS passes identically, so this test doesn't prove the difference you indicated. I think what you're seeing is VCS just doesn't warn about this case, it presumes Xs. If that's true then what Verilator should do is make it a warning instead of an error, and the user should turn off the warning.

@veripoolbot
Copy link
Contributor Author


Original Redmine Comment
Author Name: Jeremy Bennett (@jeremybennett)
Original Date: 2012-04-24T13:46:56Z


Thanks for running the tests. I'll update my patch accordingly.

@veripoolbot
Copy link
Contributor Author


Original Redmine Comment
Author Name: Jeremy Bennett (@jeremybennett)
Original Date: 2012-11-14T20:06:04Z


Continuing the conversation from Bug 532 (sorry for duplicating)...

Although Verilog 2001 does not mandate short-circuiting of bitwise-AND and bitwise-OR, it does use bitwise-AND as an example. As you note, NC and VCS accept this with a warning.

I have legacy code that breaks with Verilator (generate loops that go out of range) because of this. I'll follow your suggestion and modify the patch, so it generates a warning, and the warning can be turned off.

@veripoolbot
Copy link
Contributor Author


Original Redmine Comment
Author Name: Wilson Snyder (@wsnyder)
Original Date: 2019-10-18T00:06:23Z


Not currently being worked on.

@veripoolbot veripoolbot added effort: weeks Expect this issue to require weeks or more of invested effort to resolve type: feature-IEEE Request to add new feature, described in IEEE 1800 labels Dec 22, 2019
@wsnyder wsnyder changed the title Support short-circuiting of bitswise AND and OR Support short-circuiting Mar 28, 2021
@yTakatsukasa
Copy link
Member

yTakatsukasa commented Apr 2, 2021

Some notes from #2861
IEEE 1800-2017 11.4.7 requires && and || to evaluate the second operand only when necessary.

isTPure() always returns true at this moment because m_doShort is true. (too optimistic)

verilator/src/V3Const.cpp

Lines 911 to 916 in 273fcce

bool isTPure(AstNode* nodep) {
// Pure checks - if this node and all nodes under it are free of
// side effects can do this optimization
// Eventually we'll recurse through tree when unknown, memoizing results so far,
// but for now can disable en-mass until V3Purify takes effect.
return m_doShort || VN_IS(nodep, VarRef) || VN_IS(nodep, Const);

There are some issues if isTPure() becomes too pessimistic.

  • Less optimization chance
  • Internal error (latter pass expects some ops are removed by V3Const).
  • Wrong simulation result. (ShiftL with excessive shift amount in Verilog is 0, but undefined behavior in C++).

#2861 (comment) has experimental implementation.

Test to reproduce the issue will be added via #2869

I guess the challenge would be

  • Cover ALL AstNodes
  • Cache the previous evaluation otherwise isTPure() will be too expensive

@RRozak
Copy link
Member

RRozak commented Aug 24, 2023

The problem with conversion of logical expressions to bit expressions is fixed by #4437.
This issue requires also #4413. It disables moving function calls before their expressions.
When both PRs are merged, all cases from t_const_opt_shortcut.pl and t_dpi_shortcircuit.pl will be handled correctly. Generally, short-circuit evaluation will be supported for && and ||, with the exception of operands wrongly marked as pure, because there are still nodes that don't have a correct implementation of isPure() method.

@wsnyder
Copy link
Member

wsnyder commented Sep 18, 2023

Still need a new warning when side effects may cause problems. Hope to commit shortly.

@wsnyder
Copy link
Member

wsnyder commented Oct 15, 2023

The new SIDEEFFECT warning should tell us what additional fixes are needed in this area. Closing as general solution handled.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
effort: weeks Expect this issue to require weeks or more of invested effort to resolve resolution: fixed Closed; fixed type: feature-IEEE Request to add new feature, described in IEEE 1800
Projects
None yet
Development

Successfully merging a pull request may close this issue.

4 participants