Add Proposal | Add Analysis | Edit Class, Environment, or Release |
Number | 84
|
Category | errata
|
Synopsis | 9.7.5: Should @* include delay controls?
|
State | open
|
Class | errata-discuss
|
Arrival-Date | Jul 30 2002
|
Originator | sharp@cadence.com
|
Release | 2001b: 9.7.5
|
Environment |
http://boydtechinc.com/etf/archive/etf_2002/0012.html |
Description |
Section 9.7.5 is not entirely clear on whether certain things should be included in the implicit event_expression list. One case that seems uncertain is variables appearing in delay controls. See my comments in http://boydtechinc.com/etf/archive/etf_2002/0012.html Also, a repeat count on an event control on an intra-assignment delay is really part of the event control. Should it be included? My opinion is that delay controls and repeat-event-controls should be listed with wait and event controls as exceptions that do not get included in the implicit event_expression list. These could be listed in terms of the grammar as wait or delay_or_event_control expressions. |
Fix |
|
Audit-Trail |
From: Shalom Bresticker <Shalom.Bresticker@motorola.com> To: sharp@cadence.com Cc: etf-bugs@boyd.com Subject: Re: errata/84: Should @* include delay controls? Date: Thu, 01 Aug 2002 11:35:44 +0300 Generally, my feeling is that we should remember that the implicit event_expression list is supposed to facilitate combinational logic. Therefore, it should include, if at all possible, whatever is necessary to simulate combinational logic correctly. Other stuff, such as those mentioned here, or the side-effects mentioned in errata/82, don't need to concern us so much. That is, we can define it as we wish, and the result is whatever it is, as long as combinational logic descriptions still work correctly. I do accept the idea that where there is a comparable continuous assignment, the behavior should be similar to that of the continuous assignment. Shalom From: Michael McNamara <mac@verisity.com> To: Shalom Bresticker <Shalom.Bresticker@motorola.com> Cc: etf-bugs@boyd.com Subject: Re: errata/84: Should @* include delay controls? Date: Thu, 1 Aug 2002 18:39:11 -0700 I agree; and given that Steve quite correctly point out that we can't have both correct iterative vector indexing implict sensitivity, and implicit sensitivity to with code that indexes into arrays, with what is currently in the standard, I would rather that we lean toward the later rather than the former. So, specifically, I would rather that we inject an errata to state that given the following definitions: integer i; reg [1024:0] a, b; reg [31:0] memdata, memory[1024*1024:0]; reg [19:0] memaddr; the following code: always @(*) for (i = 0; i < 32; i = i + 1) a[i] = b[i]; always @(*) memdata = memory[memaddr]; will map to: always @(b[i]) // wrong for (i = 0; i < 32; i = i + 1) a[i] = b[i]; always @( memory[memaddr]) // right memdata = memory[memaddr]; rather than to: always @(b or i) // right for (i = 0; i < 32; i = i + 1) a[i] = b[i]; always @(memory or memaddr) // wrong memdata = memory[memaddr]; As I expect that the second always block (or indeed always blocks that do many things including differencing arrays) are much more common in todays and in future usage; where as bit walking through vectors is less common. I can see a more complicated errata that states that simulator vendors shall correctly handle bit walking by either mapping it [conservatively] to @(vector or i); and even better map it to [precisisely] @(vector[5:0]) -mac Shalom Bresticker writes: > Precedence: bulk > > The following reply was made to PR errata/84; it has been noted by GNATS. > > From: Shalom Bresticker <Shalom.Bresticker@motorola.com> > To: sharp@cadence.com > Cc: etf-bugs@boyd.com > Subject: Re: errata/84: Should @* include delay controls? > Date: Thu, 01 Aug 2002 11:35:44 +0300 > > Generally, my feeling is that we should remember that the implicit > event_expression list is supposed to facilitate combinational logic. > Therefore, it should include, if at all possible, whatever is necessary > to simulate combinational logic correctly. > > Other stuff, such as those mentioned here, or the side-effects mentioned > in errata/82, > don't need to concern us so much. That is, we can define it as we wish, > and the result is whatever it is, > as long as combinational logic descriptions still work correctly. > > I do accept the idea that where there is a comparable continuous > assignment, > the behavior should be similar to that of the continuous assignment. > > Shalom > > From: Steven Sharp <sharp@cadence.com> To: etf-bugs@boyd.com, mac@verisity.com Cc: Subject: Re: errata/84: Should @* include delay controls? Date: Fri, 2 Aug 2002 15:04:08 -0400 (EDT) > I agree; and given that Steve quite correctly point out that we can't > have both correct iterative vector indexing implict sensitivity, and > implicit sensitivity to with code that indexes into arrays, with what > is currently in the standard, I would rather that we lean toward the > later rather than the former. I disagree. The intent of @* was to prevent users from making mistakes that would result in pre- and post-synthesis differences, without any warning. With your preferred change, we would silently produce incorrect results. With what is in the standard, certain things could not be supported, but the user would be notified of that fact. I think that this is an important distinction. Furthermore, it may be possible to extend support in the future while maintaining backward compatibility. If you actually break it, then you can't fix it while maintaining backward compatibility. Steven Sharp sharp@cadence.com From: Shalom.Bresticker@motorola.com To: Michael McNamara <mac@verisity.com> Cc: etf-bugs@boyd.com Subject: Re: errata/84: Should @* include delay controls? Date: Sun, 4 Aug 2002 08:06:41 +0300 (IDT) Mac, I have not managed to follow every single email on this subject, so I may have missed something important. But, regarding the "iterative vector indexing implicit sensitivity," at least in the example you give, isn't that a case where i is a temporary variable assigned before its use, where we say that it will not be included in the sensitivity list? And the second case is of an array (as opposed to a vector), where you could not put it even explicitly into a sensitivity list. I claim that we must not, if at all possible, deliberately create a situation where a legitimate way of writing combinational logic will simulate wrong using @*. An array is a different case, because even today, you could not write it even with an explicit sensitivity list. A simulator can distinguish between a vector and an array. I don't see causing 'erroneous' behavior as viable. Better to delete @* entirely. I think it is necessary to guarantee correct behavior with vectors. Regarding arrays, it would be possible to say it should map to mem[addr] in Mac's example. In cases where that might not be sufficient, the standard could say that @* does not cover that case and implementations might give an error message if they cannot map it correctly. I also agree with the approach that it is better to give a mapping that might be overkill but works, rather than something which is efficient but wrong. The latter is out of the question in my mind. Shalom On Thu, 1 Aug 2002, Michael McNamara wrote: > I agree; and given that Steve quite correctly point out that we can't > have both correct iterative vector indexing implict sensitivity, and > implicit sensitivity to with code that indexes into arrays, with what > is currently in the standard, I would rather that we lean toward the > later rather than the former. > > So, specifically, I would rather that we inject an errata to state > that given the following definitions: > > integer i; > reg [1024:0] a, b; > reg [31:0] memdata, memory[1024*1024:0]; > reg [19:0] memaddr; > > the following code: > > always @(*) > for (i = 0; i < 32; i = i + 1) > a[i] = b[i]; > always @(*) > memdata = memory[memaddr]; > > will map to: > > always @(b[i]) // wrong > for (i = 0; i < 32; i = i + 1) > a[i] = b[i]; > always @( memory[memaddr]) // right > memdata = memory[memaddr]; > > rather than to: > > always @(b or i) // right > for (i = 0; i < 32; i = i + 1) > a[i] = b[i]; > > always @(memory or memaddr) // wrong > memdata = memory[memaddr]; > > As I expect that the second always block (or indeed always blocks that > do many things including differencing arrays) are much more common in > todays and in future usage; where as bit walking through vectors is > less common. > > I can see a more complicated errata that states that simulator vendors > shall correctly handle bit walking by either mapping it > [conservatively] to @(vector or i); and even better map it to > [precisisely] @(vector[5:0]) > > -mac > > Shalom Bresticker writes: > > Precedence: bulk > > > > The following reply was made to PR errata/84; it has been noted by GNATS. > > > > From: Shalom Bresticker <Shalom.Bresticker@motorola.com> > > To: sharp@cadence.com > > Cc: etf-bugs@boyd.com > > Subject: Re: errata/84: Should @* include delay controls? > > Date: Thu, 01 Aug 2002 11:35:44 +0300 > > > > Generally, my feeling is that we should remember that the implicit > > event_expression list is supposed to facilitate combinational logic. > > Therefore, it should include, if at all possible, whatever is necessary > > to simulate combinational logic correctly. > > > > Other stuff, such as those mentioned here, or the side-effects mentioned > > in errata/82, > > don't need to concern us so much. That is, we can define it as we wish, > > and the result is whatever it is, > > as long as combinational logic descriptions still work correctly. > > > > I do accept the idea that where there is a comparable continuous > > assignment, > > the behavior should be similar to that of the continuous assignment. > > > > Shalom > > > > > From: Steven Sharp <sharp@cadence.com> To: etf-bugs@boyd.com, Shalom.Bresticker@motorola.com Cc: Subject: Re: errata/84: Should @* include delay controls? Date: Mon, 12 Aug 2002 18:43:54 -0400 (EDT) > But, regarding the "iterative vector indexing implicit sensitivity," at least in > the example you give, isn't that a case where i is a temporary variable assigned > before its use, where we say that it will not be included in the sensitivity > list? There is no such exception in the standard. I don't know whether there was an attempt to put in such an exception at some point. I don't see a good way to add such an exception. In the general case, I believe that the question of whether a variable is guaranteed to be assigned before being used can be reduced to the halting problem, and is therefore uncomputable. > I claim that we must not, if at all possible, deliberately create a situation > where a legitimate way of writing combinational logic will simulate wrong using > @*. I completely agree. > Regarding arrays, it would be possible to say it should map to mem[addr] in > Mac's example. In cases where that might not be sufficient, the standard could > say that @* does not cover that case and implementations might give an error > message if they cannot map it correctly. > > I also agree with the approach that it is better to give a mapping that might be > overkill but works, rather than something which is efficient but wrong. The > latter is out of the question in my mind. And I agree that if an implementation can find a way of handling some or all memory references in a way that always gives the desired results, that it would be nice to allow it. But it should give an error rather than do it wrong. Steven Sharp sharp@cadence.com From: Shalom.Bresticker@motorola.com To: Steven Sharp <sharp@cadence.com> Cc: etf-bugs@boyd.com Subject: Re: errata/84: Should @* include delay controls? Date: Wed, 14 Aug 2002 22:43:36 +0300 (IDT) On Mon, 12 Aug 2002, Steven Sharp wrote: > > But, regarding the "iterative vector indexing implicit sensitivity," at least > in > > the example you give, isn't that a case where i is a temporary variable > assigned > > before its use, where we say that it will not be included in the sensitivity > > list? > > There is no such exception in the standard. Really? Are you sure? I was sure I had read it. I don't have it with me to check. > I don't know whether there was > an attempt to put in such an exception at some point. I don't see a good way > to add such an exception. In the general case, I believe that the question > of whether a variable is guaranteed to be assigned before being used can be > reduced to the halting problem, and is therefore uncomputable. Not in the general case. But there are cases where it is trivial. E.g., always @* begin a = b ; c = a ; end It is trivial to see that a is always assigned before being used. Shalom From: Steven Sharp <sharp@cadence.com> To: etf-bugs@boyd.com, Shalom.Bresticker@motorola.com Cc: Subject: Re: errata/84: Should @* include delay controls? Date: Wed, 14 Aug 2002 16:23:39 -0400 (EDT) > > There is no such exception in the standard. > > Really? Are you sure? > I was sure I had read it. > I don't have it with me to check. I have the print copy in front of me. Section 9.7.5 is less than a page long, so it would be hard to miss. > Not in the general case. > But there are cases where it is trivial. It is not as trivial as you think. And how much analysis should a tool do? You either have to provide a precise algorithm for all tools to use, or a general statement that tools can eliminate variables from the list if they can guarantee that they never read a value set by any other process. The latter would allow for optional optimization, at the cost of differences in the behavior of different tools. Of course, if the code is purely combinational, there should be no visible differences. But I've wasted a lot of time trying to track down race conditions in designs and trying to explain to customers that the standard allows different behavior in different simulators in those cases. Stating in the standard that differences are legal and usually indicate faulty Verilog code does not mean that those differences don't cause problems. > E.g., > always @* > begin > a = b ; > c = a ; > end > > It is trivial to see that a is always assigned before being used. And you are incorrect in seeing that. What if a is forced or quasi-continuous-assigned somewhere else? Then the assignment to a has no effect and c will be set to the value forced/assigned. Perhaps you would never do that, but the fact is that a is not guaranteed to be assigned before being used, even in such a trivial case. Steven Sharp sharp@cadence.com From: Michael McNamara <mac@verisity.com> To: Shalom.Bresticker@motorola.com Cc: etf-bugs@boyd.com Subject: Re: errata/84: Should @* include delay controls? Date: Wed, 14 Aug 2002 14:36:24 -0700 Shalom.Bresticker@motorola.com writes: > Precedence: bulk > > The following reply was made to PR errata/84; it has been noted by GNATS. > > From: Shalom.Bresticker@motorola.com > To: Steven Sharp <sharp@cadence.com> > Cc: etf-bugs@boyd.com > Subject: Re: errata/84: Should @* include delay controls? > Date: Wed, 14 Aug 2002 22:43:36 +0300 (IDT) > > On Mon, 12 Aug 2002, Steven Sharp wrote: > > > > But, regarding the "iterative vector indexing implicit > > > sensitivity," at least in the example you give, isn't that a > > > case where i is a temporary variable assigned before its use, > > > where we say that it will not be included in the sensitivity > > > list? > > > > There is no such exception in the standard. > > Really? Are you sure? > I was sure I had read it. > I don't have it with me to check. > > > > I don't know whether there was an attempt to put in such an > > exception at some point. I don't see a good way to add such an > > exception. In the general case, I believe that the question of > > whether a variable is guaranteed to be assigned before being > > used can be reduced to the halting problem, and is therefore > > uncomputable. Come now, this is absolutely not true. Education on Def Use chaining has been an integral part of every compiler class at a university for the past 25 years and the basic depth first search iterative algorithms were described in a survey paper, sumerizing past work, by Jeffery Ullman and and John Kam in the Journal of the ACM in 1976. Over the the last 25 years these techniques have been refined (I like the papers by Jeanne Ferrante in 1991, "Automatic constructions of sparse data flow evaluation graphs." Fundamentally if what you said was true, synthesis tools would not work, and optimizing compilers would not work. > > Not in the general case. > But there are cases where it is trivial. > E.g., > always @* > begin > a = b ; > c = a ; > end > > It is trivial to see that a is always assigned before being used. > An algorithm that inmplements this is available in source form in my Emacs mode, which you can get at http://www.verilog.com -- _ // Michael McNamara, Sr VP Technology <mac@verisity.com> _ // 650-934-6888, 408-930-6875 Cell <http://www.verisity.com> \\ // ___ ____ _ ___ _ ___ _ _ ___ ___ __ _ _ _ _ \\// |_ |___)|(___ |' | ` \ / | \ |_ (__ | / _ |\ | \/ |__ | \ | ___)| | | |__/ |__ __)| \_/ | \| From: Shalom.Bresticker@motorola.com To: Steven Sharp <sharp@cadence.com> Cc: etf-bugs@boyd.com Subject: Re: errata/84: Should @* include delay controls? Date: Thu, 15 Aug 2002 07:05:57 +0300 (IDT) On Wed, 14 Aug 2002, Steven Sharp wrote: > It is not as trivial as you think. And how much analysis should a tool do? > You either have to provide a precise algorithm for all tools to use, or a > general statement that tools can eliminate variables from the list if they > can guarantee that they never read a value set by any other process. The > latter would allow for optional optimization, at the cost of differences > in the behavior of different tools. Well, these days tools are pretty smart. But see my next comment. > > E.g., > > always @* > > begin > > a = b ; > > c = a ; > > end > > > > It is trivial to see that a is always assigned before being used. > > And you are incorrect in seeing that. What if a is forced or > quasi-continuous-assigned somewhere else? Then the assignment to a has > no effect and c will be set to the value forced/assigned. Perhaps you > would never do that, but the fact is that a is not guaranteed to be > assigned before being used, even in such a trivial case. Two comments here: 1. Let's again remember that we are talking about modeling combinational logic. In that case, the rule is what I said. That is, the way to write this explicitly is always @b begin a = b ; c = a ; end In fact, what a synthesis tool is going to give you is either a union between b and c, or at most a buffer from b to c. a is not going to appear at all. 2. As for force or quasi-continuous assignment (deprecated in SystemVerilog 3.0), this relates to my complaint about Section 5, that anyone who writes code like this thinks and expects and demands that a will not change between the two assignment statements. That is, he needs this code to be expected atomically (or at most that a not be assigned in the middle). Unfortunately, most of the WG did not accept my arguments. But some did, like Daryl Stewart. And I have seen the problem arise in several places in different contexts and by different people. I remain convinced that this is a major problem in Section 5. Shalom From: Steven Sharp <sharp@cadence.com> To: etf-bugs@boyd.com Cc: Subject: Re: errata/84: Should @* include delay controls? Date: Thu, 15 Aug 2002 20:24:21 -0400 (EDT) > > > In the general case, I believe that the question of > > > whether a variable is guaranteed to be assigned before being > > > used can be reduced to the halting problem, and is therefore > > > uncomputable. > > Come now, this is absolutely not true. I am afraid that you are incorrect about this. It is impossible to write an algorithm that can determine this about an arbitrary piece of code. With a little more thought, I was able to produce a proof of the fact, similar to the proof that the halting problem is uncomputable. > Education on Def Use chaining has been an integral part of every > compiler class at a university for the past 25 years and the basic > depth first search iterative algorithms were described in a survey > paper, sumerizing past work, by Jeffery Ullman and and John Kam in > the Journal of the ACM in 1976. Education on computability has been a part of the curriculum too, and Alan Turing demonstrated that the halting problem was uncomputable in 1936. I have been educated in all of these areas. > Over the the last 25 years these techniques have been refined (I like > the papers by Jeanne Ferrante in 1991, "Automatic constructions of > sparse data flow evaluation graphs." These algorithms can only compute approximations of the desired result. In many cases, they can guarantee that a variable will be assigned before being read. In others, they cannot be sure, and must assume the worst case. Different algorithms may differ in what they can get exact answers for, but none of them can do so for arbitrary code. > Fundamentally if what you said was true, synthesis tools would not > work, and optimizing compilers would not work. Not all code is accepted by synthesis tools, and optimizing compilers have the option of not applying an optimization if they are not sure it is legal. Conservative approximations are adequate for these uses. We cannot define the behavior of the language in terms of an algorithm that does not and cannot exist. That leaves several choices: 1. Leave the sensitivity list independent of whether variables could get values from outside the block. That is how it is now. 2. Specify the exact algorithm to be used to approximate the computation of whether a variable can get its value from outside the block. 3. Specify that simulators can leave variables out of the sensitivity list if they can determine that they never get a value from outside the block, by whatever algorithm they like. This could result in different simulators producing different results if the block has side effects. Note that if the block has no visible side effects (which should be true of any truly combinational code), a simulator can already optimize the sensitivity list if it likes, using whatever conservative approximation it likes. Its behavior would be equivalent to the standard behavior and therefore legal. The only advantage of option 3 above is if there are a significant number of blocks which have side effects or which the compiler can't be sure don't have side effects (since this is uncomputable too). I don't know how common this will be. Steven Sharp sharp@cadence.com From: Michael McNamara <mac@verisity.com> To: Steven Sharp <sharp@cadence.com> Cc: etf-bugs@boyd.com Subject: Re: errata/84: Should @* include delay controls? Date: Fri, 16 Aug 2002 09:47:32 -0700 Steven Sharp writes: > Precedence: bulk > > The following reply was made to PR errata/84; it has been noted by GNATS. > > From: Steven Sharp <sharp@cadence.com> > To: etf-bugs@boyd.com > Cc: > Subject: Re: errata/84: Should @* include delay controls? > Date: Thu, 15 Aug 2002 20:24:21 -0400 (EDT) > > > > > In the general case, I believe that the question of > > > > whether a variable is guaranteed to be assigned before being > > > > used can be reduced to the halting problem, and is therefore > > > > uncomputable. > > > > Come now, this is absolutely not true. > > I am afraid that you are incorrect about this. It is impossible to > write an algorithm that can determine this about an arbitrary piece > of code. We are not talking about arbitray code, or some abstract general case. We are talking about Verilog statements. We are ignoring force and release. We are ignoring someone using the command line interface at run time. We are ignoring runtime pli access to set variables. We are ignoring somebody using the a debugger to change the value of memory at arbitrary points. We are ignoring hierarchical references from other code. The conservative algorithmn in IEEE 1364-2001 has us adding every variable the appears in in a rhs context of any statement contained in the statement (which could be a statement group) of a procedural_timing_control_statement. This will result in more execution than is necessary, execution which will exhibit side effects. That said, the alogrithmn in 1364-2001 is certainly O(n), and is fully computable. We have an opportunity to tune this text now; or we can continue to pursue academic arguments, with the result that this feature will either be implemented extremely conservatively by some (translated into slow speed of execution), and be implemented by others in the manner originally intended, (translating into faster execution) by others. I would like to see an O(nlogn) algorithmn, like that in use by the compiler that compiled the code I am using to send you email, and that you are using to read this email. One could say let the market decide; and pick the faster simulator; however, procedural blocks very naturally include many side effects which will cause users to trivially get different answers, leading to a requirement upon us as the standards body to set a useful, unambiguous standard. > With a little more thought, I was able to produce a proof > of the fact, similar to the proof that the halting problem is > uncomputable. Show us the proof. From: Gordon Vreugdenhil <gvreugde@synopsys.com> To: Steven Sharp <sharp@cadence.com> Cc: etf-bugs@boyd.com Subject: Re: errata/84: Should @* include delay controls? Date: Tue, 27 Aug 2002 14:16:19 -0700 Steven Sharp wrote: > > From: Steven Sharp <sharp@cadence.com> > To: etf-bugs@boyd.com > Cc: > Subject: Re: errata/84: Should @* include delay controls? > Date: Thu, 15 Aug 2002 20:24:21 -0400 (EDT) [...] I'm going to stay away from the computability argument <grin>, but would like to comment on the 3 options that Steven mentions. > We cannot define the behavior of the language in terms of an algorithm > that does not and cannot exist. That leaves several choices: > > 1. Leave the sensitivity list independent of whether variables could > get values from outside the block. That is how it is now. > 2. Specify the exact algorithm to be used to approximate the computation > of whether a variable can get its value from outside the block. > 3. Specify that simulators can leave variables out of the sensitivity > list if they can determine that they never get a value from outside > the block, by whatever algorithm they like. This could result in > different simulators producing different results if the block has > side effects. I am afraid that for option 1 (and perhaps 2), implementation divergence will almost certainly occur unless vendors agree on "how to do it" independent of the committee work. Given the following: reg [7:0] m [1023:0]; always @* begin y = m[z]; $display(y); end We (VCS) are *definitely* going to have customer opposition to triggering on a change to any word of m. At the very least, we would likely have a non-standard default behavior and support the default behavior only under a switch (if at all). As Steven noted, for "equivalent to combinational" blocks, we can do the right thing anyways, but even for non-combinational blocks, customers will expect combinational sensitivities. This is a case where (some) customers will say "I don't care about the LRM, do what we expect". Realistically, I think that we should try to come up with some sort of statement on this. It might be a guarantee only in the presence of "equivalent to combinational" blocks or it might be that the implicit sensitivity list would be the same as one implied by a continuous assign formed by every RHS *expression* in the block. In any case, if we don't try to make this close to what a designer expects, vendors will almost certainly implement support in inconsistent and non-compliant ways. Gord. -- ---------------------------------------------------------------------- Gord Vreugdenhil gvreugde@synopsys.com Staff Engineer, VCS (Verification Tech. Group) (503) 547-6054 Synopsys Inc., Beaverton OR |
Unformatted |
|
Hosted by Boyd Technology