RE: [sv-bc] Mantis 1345: 10.4: "illegal" unique if/case issues

Sorry for the late response.

_____________________________________________
From: owner-sv-bc@eda.org [mailto:owner-sv-bc@eda.org] On Behalf Of Greg
Jaxon
Sent: Thursday, February 23, 2006 3:33 AM
To: Steven Sharp
Cc: sv-bc@eda.org
Subject: Re: [sv-bc] Mantis 1345: 10.4: "illegal" unique if/case issues

Steven Sharp wrote:
>>From: "Bresticker, Shalom" <shalom.bresticker@intel.com>
> 
> 
>>[Shalom] And in unique 'if'. I admit I don't understand all the 
>>discussion about interleaving orderings in that I don't think it makes

>>a difference in any normal case. Is there any such case which is not 
>>pathological?
> 
> 
> Except for the issue in Mantis item 1304, which is just plain wrong, I

> would call all the cases where interleaving order matters
pathological.
> They could all be considered illegal, without losing anything useful.

I'd generally agree, and I'd guess the cost of detecting this at
simulation time is no worse than o(n log n) time and space proportional
to the storage addressed by the conditional tests.  Brad has often
suggested that SV prohibit side-effects here altogether, which would
probably not be practical for testbench uses; but prohibiting
side-effects on each others' logic cones is both sensible and doable.
Or there's another alternative (below)

[Shalom] If such a prohibition would only apply to 'unique' if/case and
not to regular case, maybe it would be practical.

>>I would be happy with deleting all the discussion about various 
>>orderings from the LRM and even be willing to have the LRM specify 
>>evaluation in top-down order.
> 
> I wouldn't have any problem with that.  Has anyone else implemented it

> with a different evaluation order?

There are several ways to define "top-down", given that control is also
branching into one of the conditional statement lists.  Here's a
proposal in which the case label side-effects are permitted, but don't
compromise concurrent evaluation.

Consider code where A,B,C,... stand for expressions or statements whose
evaluation order we wish to settle.

     unique case (A)
      B, C :  D;
      E:      F;
      G, H:   I; J;
     endcase;
     K;

[Shalom] Quibble: "I;J;" needs to be enclosed in begin/end.

Clearly A evaluates once and must be compared with {B,C,E,G,H} in order
to test that
    - only one of the branch directions is taken, or
    - only one of those case labels matches A.
In the first instance, at most one of C or H might be skipped due to
shortcut evaluation.

If A has a side-effect, my gut says that all of {B-K} should see the
resulting state.

[Shalom] Agree.

Now consider who should see side-effects in E.  I think that this
side-effect must become visible to the execution of F when A==E.  
[Shalom] Agree.
Steven's instinct tells him that E's side-effect should probably /not/
be visible to B, C, or D.  
[Shalom] Agree.
I agree and further argue that (by the symmetry of concurrency) it
should also /not/ be visible to G, H, I, or J.
[Shalom] Agree.

If that branch to F is taken, control will afterward move to K, and
clearly it sees E's side-effect.  But at this juncture, F has already
ignored any side-effects that were in {B,C,G,H}, and so K should
continue to ignore them.
[Shalom] Agree.

In this model, side-effects in case labels are "speculative" and only
committed if they appear on the "winning" branch.  This is really no
problem at all for synthesis :-)  For simulation, it looks more
complicated.  It's complexity is no worse than *detecting* side-effect
collision.  But if these side effects can trigger events, the whole
proposal looks silly.  I think embedded assignments cannot be
non-blocking, so perhaps their relationship to event scheduling is
already special in other ways that would support this "speculation".
If this is not supportable, then prohibiting side-effects (in the design
space) would be the best policy.
[Shalom] Just in uniques.

The final point in this definition is to say whether C and H see
side-effects of B or G (respectively).  If they do *not* see prior
label-list side effects, then they are acting like entirely separate
branch guardians, and as such they should be considered as separate case
labels subject to the uniqueness assertion - meaning that it would be
illegal for A==B && A==C.
[Shalom] Disagree. They should not see side-effects in a unique case,
though I would not make a big fuss about it. But definitely, the
case_expression should be allowed to match more than one expression
within a single case_item. One reason, but not the only one, is that the
problem with uniqueness (parallel_case) violation is really only when
the two matches can cause different case actions. That is difficult to
identify when they are in different case_items. However, when there is
more than one expression in a single case_item, then even if more than
one expression matches, they will cause the same case action.

The discussion of unique case so far hasn't required one-hot across all
the separate labels, but rather one-hot across the several label-lists.
Given that precedent, we'd expect serial, and possibly shortcut
evaluation of B then C, with C having access to B's side-effects, even
if B does not match A.
[Shalom] I don't see why.

So that's a serializable parallel semantics that ought to model the
synthesized hardware reasonably well.  Side effects like $display which
have trouble being done "speculatively" are the cart which should not be
put before this horse.  I believe those effects lie outside the design
space anyway.

> I can see the possibility of someone optimizing case statements for 
> efficient table lookup in a way that effectively alters the evaluation

> order.  I can't actually think of any way of doing it in the presence 
> of the kinds of expressions that could have side effects, but maybe 
> somebody else could.

In my proposal, the side-effects only propagate downstream along the
taken branch - never sideways into the concurrent alternatives.
This leaves them unordered yet still well-defined.
It also avoids the pathology where G's side-effect can reach D.

By "top-down" I understand Steven to mean:
[Shalom] Actually, "top-down" was my term. Steven would have been more
precise.
   1) execute all the case labels in lexical order,
      possibly shortcutting,
      possibly triggering events due to embedded side-effects...
   2) compare and assert one-hotness
   3) execute the winning branch

That offers a lot of support for pathological cases - it puts too much
execution between the winning label and the winning branch.
I prefer to avert my eyes from pathological effects, so I propose
confining them to the taken control paths and ignoring those done only
to verify the one-hot assertion.
[Shalom] Is that easy to implement? Or make them illegal in unique
if/cases.

This counter-proposal corresponds better to a "parallel"
reading for unique case.

[Shalom] Overall, I like the idea.

Greg Jaxon
Discalimer:  this is another crazy idea, with no specific relationship
to extant or planned Synopsys products.
[Shalom] A shame.

Thanks,
Shalom