Subject: RE: [sv-ec] EXT-14: 12.4.11 Object handle guards
From: Ryan, Ray (Ray_Ryan@mentorg.com)
Date: Mon Oct 13 2003 - 09:37:39 PDT
Arturo,
I agree that when the condition expression does not contain any random
variables, it
can be an optimization to treat the condition as a guard (ie. the
condition can be evaluated
prior to the randomization).
When the condition expression does include a random variable, by default
it cannot be
optimized into a guard condition - that is, the condition must be solved
along with the
constraint. In Ext-14, two special cases are made (handles, iterative
constaints) where
the condition is forced to be a guard (even if it contains random
variables). This forces
the condition to be evaulated prior to randomization of the variables in
the constraint
part. Therefore, any random variables in the condition part must be
randomized first
(generating a randomization ordering for the variables).
My opinion is that since two cases have occured where there is a need to
force the
condition to be a guard (evaluated prior randomization of the
constraint), it would be
useful to provide a means for the User to explicitly specify that the
condition is a
guard. I suggest that the if-then-else form be used for the this.
--- If the preference is for implicit object handle guards, it just occured to me that it could be simpler and safer for the User if rather than scan the condition for an object handle the compiler could scan the constraint for the usage of an object handle and if a constraint includes a object handle, implicitly generate the guard that the handle is not null. Ray-----Original Message----- From: Arturo Salz [mailto:Arturo.Salz@synopsys.com] Sent: Wednesday, October 08, 2003 3:29 PM To: Ryan, Ray; 'sv-ec@server.eda.org' Subject: Re: [sv-ec] EXT-14: 12.4.11 Object handle guards
Ray, Sorry for the delayed response. My comments are interspersed below. Arturo ----- Original Message ----- From: Ryan, Ray <mailto:Ray_Ryan@mentorg.com> To: 'Arturo Salz' <mailto:Arturo.Salz@synopsys.COM> ; 'sv-ec@server.eda.org' <mailto:'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" < <mailto:Ray_Ryan@mentorg.com> Ray_Ryan@mentorg.com> To: " <mailto:'sv-ec@server.eda.org'> 'sv-ec@server.eda.org'" < <mailto:sv-ec@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 : Mon Oct 13 2003 - 09:46:31 PDT