Subject: Re: [sv-ec] EXT-14: 12.4.11 Object handle guards
From: Arturo Salz (Arturo.Salz@synopsys.com)
Date: Wed Oct 08 2003 - 15:28:41 PDT
MessageRay,
Sorry for the delayed response. My comments are interspersed below.
Arturo
----- Original Message -----
From: Ryan, Ray
To: 'Arturo Salz' ; 'sv-ec@server.eda.org'
Sent: Wednesday, September 10, 2003 3:45 PM
Subject: RE: [sv-ec] EXT-14: 12.4.11 Object handle guards
Arturo,
I appreciate you clarification for declaration of an object handle as rand. It makes more sense
that this includes the object's random variables rather than my misinterpretation of applying
the rand to the object's variables.
OK. Good.
I still have problems with object handle guards, (or more generally contraint guards).
1) As originally defined, a predicated constraint defines a logical relationship between the
expression and the constraint. That is a => b is equivalent to !a || b (section 12.4.5).
That is correct. Actually, it defines a logical relationship between the expression and the
constraint set. If the constraint set includes more than one expression then there is an
implicit && between all the constraints expressions.
2) EXT-14 identifies the need to have a guarded constraint, where the 'guard' controls whether
the constraint is included as an 'active' constraint. A guarded constraint is needed when
evaluation of the constraint may cause an error. Two cases are identified (are there others):
a) the constraint references a variable through an object handle and the object handle may be null.
b) the constraint references an array with an index out of range (specifically in a foreach constraint).
Those are the only two non-compile time errors that can be generated at run-time.
3) EXT-14 proposes that the expression in a predicated constraint be treated as a guard when:
a) the expression involves object handle comparisons
b) the predicated constraint occurs in the constraint set of a foreach construct.
Yes. That's correct.
The reason for (a) is that object handles are special. As noted in (1) above, rand object handles
have transitive-like semantics, that is, the handle itself is not randomized but the object to which
the handle refers. Thus, if the solver even tries to examine a property within a null-object, it will
result in an error, regardless of the constraint.
The reason for (b) is that the constrains generated by a foreach can result in bogus constraints
(i.e., an out-of-bounds index) and when the solver tries to examine the constraints, it will result
in an error, regardless of the constraint.
Both of these situations are quite unique from other types of constrains in which the user can
ensure that the constraints are well formed.
Note that guards do not introduce any new semantics. They only define the behavior under error
conditions. A predicated constraint, A => B, can have the following scenarios:
1) A is TRUE => involves only state variables and can be evaluated
2) A is FALSE => involves only state variables and can be evaluated
3) A is unknown => involves one or more random variables
In case (1) the solver can optimize the constraint set by ignoring A and including B (un-predicated):
The only constraint generated is: B. (i.e., B == TRUE)
In case (2) the solver can optimize the constraint set by ignoring A discarding B:
No additional constraint is generated.
In case (3) no optimization is possible and the implication constraint must be used:
The constraint generated is: !A || B.
Note that even if the above optimizations (cases 1 and 2) are not applied, the constraints semantics
are the same, that is, the solver must always solve the relation !A || B. This is not mentioned in the
LRM because they are only optimizations. A solver implementation may choose to apply them or not.
Thus, the only observable difference is when the expression B in case (2) contains an error. An
implementation that applies the optimization will not generate an error, whereas an implementation
that does not apply the optimization may or may not generate an error; it is up to the implementation.
What EXT-14 proposes is that under two specific situations, predicated constraints must not generate
an error. These are the only situations that the LRM mandates that an error not be generated.
Some problems with #3:
The criteria that the expression involves object handle comparisons likely needs to be more
specific. That is, which of the following predicate expressions are guards - they all involve
an object handle comparison?
Class Slist;
rand int n;
rand int A[10];
rand Slist left;
rand Slist right;
constraint c1 { (left != null) => n < left.n; }
constraint c2 { ((left != null) && (right != null)) => left.n < right.n; }
constraint c3 { ((left == left) && (n < 10) ) => A[n] == 0; }
constraint c4 { ((left != null) + (right != null) == 2) => n < left.n; }
endclass
All the predicated expressions that involve object handle comparisons are guards.
That just means that the expressions can be evaluated before passing them to the
next phase of the solver. This definition includes all the constraints you wrote.
The expression in c3 includes (involves) a object handle comparison simply to cause the expression
to be treated as a guard.
The specification that "Predicate expressions within a foreach behave as guards ..." (proposed 12.4.7)
has the restrictive effect that regular implication constraints cannot be used within a foreach
constraint. For example, in the following:
Class C;
rand int A[];
rand bit B[];
rand bit x;
constraint { A.size == B.size; }
constraint f1 { foreach ( A[k] ) (A[k] < 0) => x == 1; }
constraint f2 { foreach ( A[k] ) (B[k] == 1) => A[k] < 0; } // also, is "B[k]" allowed here
endclass
In f1 and f2, the predicate expression (A[k] < 0) and (B[k] ==1) are guard expressions. This will
cause an implicit variable ordering (similar to functions). That is, each B[k] is solved before
A[k], and each A[k] is solved before x.
In this case, the user may perfer that these not be treated as guard conditions.
I think that here you are deriving new semantics that are not part of the spec. First, a minor
comment about your example: The size of A (or B) is really unconstrained. A valid solution
includes all possible size values (i.e., any integer). Surely some of those values will cause
the system to run out of memory.
The foreach construct is simply a shorthand to avoid having to unroll the constraints, but the
solver must still do that. Thereafter, all constraints must be solved as one.
For example, if the first constraint in your code was changed as follows:
constraint S { A.size == 2 ; A.size == B.size; } // both arrays of size 2!
Then that set of constraint declarations would generate the following constraints:
(A[0] < 0) => x == 1;
(A[1] < 0) => x == 1;
(B[0] == 1) => A[0] < 0;
(B[1] == 1) => A[1] < 0;
Constraint f1 contributes the first two constraints, constraint f2 contributes the last 2.
Next, these four constraints must be solved together, as a single set of constraints.
I'm not sure if the constraints make sense, but the semantics should be clear.
When I say generate constraints, I mean a process very similar to the generate construct,
except that instead of operating on static information, the generation of constraints depends
on run-time data including other constraints. This is the reason why foreach constraints
impose an ordering with the size of the array: Before the foreach constraints can be
unrolled (generated), they size of the array must be known as the number of equations
will depend on the size of the array.
In summary, I'd prefer that rather than try to identify the cases where a predicate expression
should implicitly be treated as a constraint guard, there should be a explicit means of
specifying a guarded constraint or a predicated constraint. That is, let the user explicitly
specify which form of constraint is desired. (This is also perferable to by previous suggestion
that a state variable expression be implicitly treated a guard).
I believe that these are best left as optimizations for the solver. There is no semantic
benefit to the user other than attempt to control the generation of errors for malformed
constraints. The situations we have identified are truly unique in the sense that a well
formed and correctly written constraint will not result in an error.
As a possability, how about if the implication operator specifies a predicated constraint (ie
specifies a logical relation between the expression and constraint) and an if ..else constraint
specifies a guarded constraint (ie conditional inclusion of the constraint as active) ?
What you propose is plausible, but I think that it will simply complicate the language by
adding an additional set of semantics to the different predicated operators. Currently, the
implication and if constraints are the same, with the exception that an if constraint may
optionally specify an else clause.
Ray
-----Original Message-----
From: Arturo Salz [mailto:Arturo.Salz@synopsys.com]
Sent: Tuesday, September 09, 2003 3:59 PM
To: Ryan, Ray; 'sv-ec@server.eda.org'
Subject: Re: [sv-ec] EXT-14: 12.4.11 Object handle guards
Ray,
You raise two distinct issues. First, a proposal to generalize predicated constraint expressions. Second, an attempt to clarify the definition of object handles declared random. let me deal with each one separately.
First issue:
The object guards proposal states that a predicated expression such as
'expression' => 'constraint'
behave thus:
During loop (foreach) constraint generation, if the expression involves object handle comparisons, the expression is evaluated in order for the solver to decide whether to keep the constraint. If the constraint is eliminated, no error is issued on illegal access within the constraint.
If we merge the existing proposal with Ray's suggestion, we end up with the following:
During loop (foreach) constraint generation, if the expression involves object handle comparisons or it is a state variable expression, the expression is evaluated in order for the solver to decide whether to keep the constraint. If the constraint is eliminated, no error is issued on illegal access within the constraint.
Basically, this allows an object handle itself to be treated the same as a state variable. On this, Ray's proposal and the original proposal both agree. The observation that the handles themselves are not randomized is right on. However, I believe that Ray's proposal goes beyond this and attempts to generalize what I believe is just an optimization, which is best left to the implementation. For example, Ray's suggestion would force to optimize a case like:
a == 1 => x == 0;
where "a" is a state variable. Whether the constraint is eliminated during constraint generation, or during constraint solving, should be left to the implementation. The effect will be the same. The only difference is in which phase of the constraint solution the expression might be evaluated, which is highly implementation dependant. The only observable difference is whether an illegal array index within the predicated constraint generates an error or not. For example, if we make the following change to the above constraint:
a == 1 => x[7] == 0;
Where 7 is an illegal index to array variable "x". The current scheme might result in an illegal array index error whereas Ray's proposal will not.
Thus, Ray's comment on deactivating constraints is accurate, but it has multiple implementations. In either implementation, if the guard evaluates to FALSE, the constraint is indeed inactive. Note that evaluating guards during constraint generation raises the possibility of evaluating expressions that have rand variables as well, e.g.,
a == 1 && y == 0 => x == 0;
Here, if "a" is not 1, then we might short-circuit the condition. This can get arbitrarily hairy. Again, this is best left to the implementation. In either case, there should be no semantic differences.
------------------------------------------------------------------------------
The second issue is deals with object handles declared rand.
The LRM says:
"An object handle can be declared rand in which case all of that object's variables and constraints are solved concurrently with the variables and constraints of the object that contains the handle."
And Ray states:
"Declaration of an object handle as random, declares all the variables within the instance of the object to be random, but the handle itself is not a random variable - the value of the handle is never randomized (ie a new instance is never generated by randomization)."
There is a partial truth to what Ray says. The handle itself is never randomized. But, it does not say that the contents of the object are declared random. Rather, that the random variables declared within the object along with the object's constraints are solved concurrently. I think the wording of the LRM may be misleading.
Perhaps the LRM should be changed to:
"An object handle can be declared rand in which case all of that object's random variables and constraints are solved concurrently with the variables and constraints of the object that contains the handle."
I hope this clarifies the issue.
Arturo
----- Original Message -----
From: "Ryan, Ray" <Ray_Ryan@mentorg.com>
To: "'sv-ec@server.eda.org'" <sv-ec@eda.org>
Sent: Monday, September 08, 2003 10:32 AM
Subject: [sv-ec] EXT-14: 12.4.11 Object handle guards
In the description for EXT-14 the section 12.4.11 introduces
Object handle guards (for constraints).
In this section, a special case is made for predicate expressions
that involve comparisons between two object handles. I believe that
instead, a more general clarification should be made for predicated
constaints.
A predicated constraint consists of a 'expression' and a 'constraint
set' (12.4.5, 12.4.6). I propose that a distinction be made depending
on whether the 'expression' contains a reference to any active random
variable.
If the expression does not contain a reference to any active random
variable, then the expression is a guard for the constraint set. If the
value of the guard expression is false, then the constraint set is inactive.
This definition of a guard expression should apply to both the implication
and if..else forms of conditional constraints.
This construct could be used for other cases, where evaluation of
a constraint would be invalid (besides the special case involving
object handles).
The case of an object handle in a conditional expression may need the
clarification that an object handle itself is never a random variable.
Declaration of an object handle as random, declares all the variables
within the instance of the object to be random, but the handle itself
is not a random variable - the value of the handle is never randomized
(ie a new instance is never generated by randomization).
Therefore an expression that include a object handle (and no other
random variable) is a guard expression, and acts to control whether or
not the constraint set is active.
- Ray Ryan
This archive was generated by hypermail 2b28 : Wed Oct 08 2003 - 15:32:45 PDT