Re: [sv-ec] EXT-14: 12.4.11 Object handle guards


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