Some Ideas on Coverage Extendability

The biggest advantage of e regarding coverage is, in my opinion, the ability to tweak the definitions of existing coverage groups by extending them from anywhere inside the verification environment. This is particularly useful when dealing with coverage groups defined inside eVCs. For example, let's say that we have an AHB eVC that provides some very extensive coverage definitions to make sure that we rigorously verify our DUT. If that DUT is a very simple slave that can only process read transactions, we'll never reach 100% coverage unless we ignore all references to write transactions. This is easily done with just a few lines of code:

<'
extend has_coverage vgm_ahb_monitor {
  cover access is also {
    item direction using also ignore = (direction == WRITE);
  };
};
'>

While SystemVerilog provides a comparably expressive coverage description syntax to e's (which, may be even more powerful in some respects), it doesn't allow for the same extendibility.

Let's say that we are verifying a RISC CPU that can perform simple arithmetic operations using a register file of size 8:

typedef enum { ADD, SUB, MUL, DIV } operation_e;
typedef enum { R[8] } register_e;

An instruction would contain fields for the operation to be performed, the registers where the two operands are stored and the register in which to store the result:

class instruction;
  rand operation_e operation;
  rand register_e op1;
  rand register_e op2;
  rand register_e dest;
endclass

At first glance, we might be tempted to try and cover all possible combinations of operations and registers:

class cov_collector;
  covergroup cg;
    coverpoint operation;
    coverpoint op1;
    coverpoint op2;
    coverpoint dest;

    cross operation, op1, op2, dest;
  endgroup

  // ...
endclass

Even for such a basic CPU this means covering 4 * 8 * 8 * 8 = 2048 cross bins. Adding just one more instruction would raise that number to 2560. Adding just one more register would raise that number to 2916. Adding just two more registers would raise that number to 4000. I guess it's clear that this approach won't scale when our design grows.

Maybe it isn't necessary to cover all combinations. After all, we've had to give up on the dream of traversing the entire state space of a DUT many years ago, when they started getting way too big. We could make an educated guess that it isn't important to make sure that we executed an ADD with all combinations of operands and destinations. What would be important, though, is that we've made sure that each register can be multiplexed to each of the three operation arguments:

class cov_collector;
  covergroup cg;
    // ...

    operation_vs_op1 : cross operation, op1;
    operation_vs_op2 : cross operation, op2;
    operation_vs_dest : cross operation, dest;
  endgroup
endclass

Some other interesting corner cases might be to make sure that we've tried to use the same register for both operands or for one of the operands and the destination, regardless of what the operation was:

class cov_collector;
  covergroup cg with function sample(operation_e operation, register_e op1,
    register_e op2, register_e dest
  );
    // ...

    same_reg_both_ops : coverpoint (op1 == op2);
    same_reg_op1_and_dest : coverpoint (op1 == dest);
    same_reg_op2_and_dest : coverpoint (op2 == dest);
    same_reg_both_ops_and_dest : coverpoint (op1 == dest && op2 == dest);
  endgroup
endclass

Now that we've cut down the problem space to a more manageable size and are merrily going about verifying our design, our colleagues in marketing notice that there might be some profit to be made if we could offer a version of our CPU that only supports addition and subtraction. Since SystemVerilog coverage groups aren't extendable we can't leverage the coverage definitions from above for this other project. We'd need to define the covergroup again and specify that we want to ignore multiplications and divisions:

class no_mul_cov_collector;
  covergroup cg;
    coverpoint operation {
      ignore_bins ignore[] = { MUL, DIV };
    }

    coverpoint op1;
    coverpoint op2;
    coverpoint dest;

    operation_vs_op1 : cross operation, op1;
    operation_vs_op2 : cross operation, op2;
    operation_vs_dest : cross operation, dest;

    same_reg_both_ops : coverpoint (op1 == op2);
    same_reg_op1_and_dest : coverpoint (op1 == dest);
    same_reg_op2_and_dest : coverpoint (op2 == dest);
    same_reg_both_ops_and_dest : coverpoint (op1 == dest && op2 == dest);
  endgroup

  // ...
endclass

Those same colleagues from marketing also figure out that we could sell a slightly slower variant of our CPU that only has four registers. As before, we'd need to create another copy of the covergroup where we ignore all registers from R4 onward:

class less_regs_cov_collector;
  covergroup cg;
    coverpoint operation;

    coverpoint op1 {
      ignore_bins ignore[] = { [R4:R7] };
    }

    coverpoint op2 {
      ignore_bins ignore[] = { [R4:R7] };
    }

    coverpoint dest {
      ignore_bins ignore[] = { [R4:R7] };
    }

    operation_vs_op1 : cross operation, op1;
    operation_vs_op2 : cross operation, op2;
    operation_vs_dest : cross operation, dest;

    same_reg_both_ops : coverpoint (op1 == op2);
    same_reg_op1_and_dest : coverpoint (op1 == dest);
    same_reg_op2_and_dest : coverpoint (op2 == dest);
    same_reg_both_ops_and_dest : coverpoint (op1 == dest && op2 == dest);
  endgroup

  // ...
endclass

Now we've got three copies of essentially the same covergroup, with very small differences. If after a review we notice that we need to add a new coverage item because we missed some important aspect, we'll need to make sure that we update all three of those coverage groups. If marketing finds even more potential for stripped down CPUs (for example, without multiplication and with less registers at the same time), those new variants will only increase the number of files we need to maintain in sync.

I couldn't accept that there isn't any elegant solution to this problem, so I went digging through the LRM. The new 2012 standard added some cool new features to the coverage chapter. The one that caught my eye in particular was the with syntax for specifying coverpoints:

covergroup some_covergroup;
  coverpoint some_coverpoint {
    ignore_bins ignore[] = some_coverpoint with (is_ignore_bin(item));
  }
endgroup

What this code snippet would do is ignore all values of the coverpoint for which the is_ignore_bin(...) function returns a 1. Let's imagine that we write the definition of the operation coverpoint in this manner. We need to find a way to switch out the implementation of the function, so that it always returns a 0 (in the general case where we don't want to ignore anything) or sometimes returns a 1 (to ignore MULs and DIVs).

There is a lot of literature on this topic (switching out method implementations) in the world of software programming. Generic programming and, more specifically, policy-based design give us the answer. This programming paradigm is based on C++ templates, which are analogous to SystemVerilog parameterized classes. We could use parameter classes to define different policies whether a bin is supposed to be ignored or not.

class cov_collector #(type POLICY);
  covergroup cg;
    coverpoint operation {
      ignore_bins ignore[] = operation with (
        POLICY::is_operation_ignore_bin(item));
    }

    // ...
  endgroup

  // ...
endclass

A policy class would need to provide an appropriate implementation of the is_operation_ignore_bin(...) function, for example to ignore multiplication and division:

class no_mul_cg_ignore_bins_policy extends cg_ignore_bins_policy;
  static function bit is_operation_ignore_bin(operation_e operation);
    return operation inside { MUL, DIV };
  endfunction
endclass

When instantiating the coverage collector, we would select what policy to parameterize it with:

cov_collector #(no_mul_cg_ignore_bins_policy) no_mul_cov = new();

While trying out this code I got a cryptic error message regarding the use of is_operation_ignore_bin(...) inside the bin definition. Luckily, I was able to tweak the code to an equivalent form:

class cov_collector #(type POLICY);
  covergroup cg;
    coverpoint operation {
      ignore_bins ignore[] = operation with (item inside
        { POLICY::get_operation_ignore_bins() });
    }

    // ...
  endgroup

  // ...
endclass

Now, the policy class just has to return a list containing the values we want ignore:

typedef operation_e array_of_operation_e[$];

class no_mul_cg_ignore_bins_policy extends cg_ignore_bins_policy;
  static function array_of_operation_e get_operation_ignore_bins();
    return '{ MUL, DIV };
  endfunction
endclass

We can extend this idea to the other coverpoints as well, leading to the following definition for the covergroup:

class cov_collector #(type POLICY = cg_ignore_bins_policy);
  covergroup cg;
    coverpoint operation {
      ignore_bins ignore[] = operation with (item inside
        { POLICY::get_operation_ignore_bins() });
    }

    coverpoint op1 {
      ignore_bins ignore[] = op1 with (item inside
        { POLICY::get_op1_ignore_bins() });
    }

    coverpoint op2 {
      ignore_bins ignore[] = op2 with (item inside
        { POLICY::get_op2_ignore_bins() });
    }

    coverpoint dest {
      ignore_bins ignore[] = dest with (item inside
        { POLICY::get_dest_ignore_bins() });
    }

    operation_vs_op1 : cross operation, op1;
    operation_vs_op2 : cross operation, op2;
    operation_vs_dest : cross operation, dest;

    same_reg_both_ops : coverpoint (op1 == op2);
    same_reg_op1_and_dest : coverpoint (op1 == dest);
    same_reg_op2_and_dest : coverpoint (op2 == dest);
    same_reg_both_ops_and_dest : coverpoint (op1 == dest && op2 == dest);
  endgroup

  // ...
endclass

The default policy (for the fully-featured CPU) would be to not ignore anything:

class cg_ignore_bins_policy;
  static function array_of_operation_e get_operation_ignore_bins();
    return '{};
  endfunction

  static function array_of_register_e get_op1_ignore_bins();
    return '{};
  endfunction

  static function array_of_register_e get_op2_ignore_bins();
    return '{};
  endfunction

  static function array_of_register_e get_dest_ignore_bins();
    return '{};
  endfunction
endclass

Implementing new variants would just boil down to writing new policy classes. For example, for the CPU with less registers, we would have:

class less_regs_cg_ignore_bins_policy extends cg_ignore_bins_policy;
  static function array_of_register_e get_op1_ignore_bins();
    return '{ R4, R5, R6, R7 };
  endfunction

  static function array_of_register_e get_op2_ignore_bins();
    return get_op1_ignore_bins();
  endfunction

  static function array_of_register_e get_dest_ignore_bins();
    return get_op1_ignore_bins();
  endfunction
endclass

We can also easily handle the CPU with less registers and no multiplier/divider by just writing a few more lines of code:

class less_regs_no_mul_cg_ignore_bins_policy extends
  less_regs_cg_ignore_bins_policy;

  static function array_of_operation_e get_operation_ignore_bins();
    return no_mul_cg_ignore_bins_policy::get_operation_ignore_bins();
  endfunction
endclass

As we already saw, selecting the appropriate coverage model is done by passing the corresponding policy as a parameter when instantiating the coverage collector:

cov_collector cov;
cov_collector #(no_mul_cg_ignore_bins_policy) no_mul_cov;
cov_collector #(less_regs_cg_ignore_bins_policy) less_regs_cov;
cov_collector #(less_regs_no_mul_cg_ignore_bins_policy) less_regs_no_mul_cov;

Using policy classes allows us to separate our coverage definitions from their parameterization. The result is that we have less code, which is also much easier to maintain because we did away with the redundancy the old-school method suffered from.

Have a look at the next post for an alternative way of using policy classes.

Keeping Constraints and Covergroups in Sync

In the old days, people had to write all of their tests by hand. With chips getting bigger and bigger, it became clear that this painstaking process couldn't scale. Constrained random verification was invented to help us verification engineers deal with the increasing complexity of our DUTs. By describing the kind of stimulus we want to drive and letting the random generator do its thing we can verify more with less effort. Random tests are nice and all, mostly because they are easier to write, but this all comes at a price. It's much more difficult to say what a random test is really doing without letting it run. We typically write coverage to log what we are actually stimulating.

Constraints and coverage are two sides of the same coin; they both represent the legal state space. By writing constraints we decide what we want to stimulate, whereas coverage describes what we want to observe. The two should be in sync, since if we aren't driving something, it doesn't make any sense to try to observe it.

Let's look at a very basic example of an item with two integer fields and some constraints set on them:

class item;
  rand bit[2:0] x, y;

  constraint x_always_smaller {
    x < y;
  }

  constraint never_same_parity {
    x % 2 == 0 <-> y % 2 == 1;
  }

  constraint if_2_then_5 {
    x == 2 -> y == 5;
  }
endclass

We only want to generate pairs with x always smaller than y, both having different parities and if x is 2 we want y to be 5. These constraints range from very general to very specific.

As mentioned above, generating random items isn't going to help us much if we can't prove for certain that we've driven all legal values. We'll need to cover the values of x and y and ignore any illegal combinations. Specifying ignore bins used to be a very daunting task, as the language wasn't particularly rich in features. Things have gotten much better with the IEEE 1800-2012 standard. This post from AMIQ Consulting shows how to use expressions to specify cross-coverage bins. Here's how our coverage collector could look like:

class cov_collector;
  covergroup cov with function sample(bit[2:0] x, bit[2:0] y);
    coverpoint x;
    coverpoint y;

    cross x, y {
      function CrossQueueType create_x_greater_ignore_bins();
        for (int i = 0; i < 8; i++)
          for (int j = 0; j < 8; j++)
            if (i >= j)
              create_x_greater_ignore_bins.push_back('{ i, j });
      endfunction

      function CrossQueueType create_same_parity_ignore_bins();
        for (int i = 0; i < 8; i++)
          for (int j = 0; j < 8; j++)
            if (i % 2 == j % 2)
              create_same_parity_ignore_bins.push_back('{ i, j });
      endfunction

      function CrossQueueType create_if_2_and_not_5_ignore_bins();
        for (int i = 0; i < 8; i++)
          if (i != 5)
            create_if_2_and_not_5_ignore_bins.push_back('{ 2, i });
      endfunction

      ignore_bins x_greater = create_x_greater_ignore_bins();
      ignore_bins same_parity = create_same_parity_ignore_bins();
      ignore_bins if_2_and_not_5 = create_if_2_and_not_5_ignore_bins();
    }
  endgroup

  // ...
endclass

Writing this covergroup without expressions would have been a true test of one's patience. Previously we would have had to explicitly write out all of the values we wanted to ignore, since it wasn't possible to specify any relationships between values. The new language constructs are definitely a step in the right direction.

To make it all a bit easier to follow it makes sense to create one set of ignore bins for each constraint. With some looping and expression checking we can ignore all of the value pairs that would be restricted by each constraint. This way, we can ensure that everything is in sync. The unfortunate part, however, is that we get a lot of redundancy between the two classes. We've described our state space (the legal values of x and y) twice: once as the expressions inside the constraints and once again as the same expressions (albeit in negative form) inside the ignore bins. Should we want to add a new constraint or modify one of the existing ones, we'd need to modify both classes. Thus, the constraints and the coverage form a very fragile equilibrium.

Randomization can be used for more than just driving stimulus. This paper from Verilab shows how the constraint solver can be used in reverse gear to extract metadata from a collected packet. Constraints can also be leveraged as checkers, for example, to make sure that a collected packet contained a legal combination of fields. Using the constraint solver for these tasks means that we don't need to duplicate information inside the checking code.

We can integrate this idea into our coverage problem. We could just loop over all combinations of x and y and use the constraint solver to figure out if a certain combination is legal or not:

class better_cov_collector;
  covergroup cov with function sample(bit[2:0] x, bit[2:0] y);
    coverpoint x;
    coverpoint y;

    cross x, y {
      function CrossQueueType create_ignore_bins();
        item it = new();
        for (int i = 0; i < 8; i++)
          for (int j = 0; j < 8; j++) begin
            if (!it.randomize() with { x == i; y == j; })
              create_ignore_bins.push_back('{ i, j });
          end
      endfunction

      ignore_bins ignore = create_ignore_bins();
    }
  endgroup

  // ...
endclass

Now we can modify the constraints on our items as much as we like and our ignore bins will stay in sync. This is one of the few cases where we want randomization to fail. One small problem with that is that modern simulators have features where it is possible to stop or break on randomization failures. This will interfere with our code and might become really annoying. Turning such features off isn't an option either, since they can provide real benefit for cases where we actually overconstrain a randomization call.

We can adapt our code to use the inline constraint checker language feature:

function CrossQueueType create_ignore_bins();
  item it = new();
  for (int i = 0; i < 8; i++)
    for (int j = 0; j < 8; j++) begin
      it.x = i;
      it.y = j;
      if (!it.randomize(null))
        create_ignore_bins.push_back('{ i, j });
    end
endfunction

By calling randomize(null) we are turning off randomization for all fields inside our item and checking whether the values that we assigned to them conform to the constraints. This way, the simulator can distinguish that this isn't a regular randomization call and wouldn't need to break if it failed. I know of at least one simulator that doesn't do this, though. If yours also breaks here, it might be nice to open a support case with the vendor to check if they wouldn't want to implement this differentiation inside their tool.

While this approach works for cross-coverage, it wont work for regular coverpoints, since there it isn't possible to specify ignore bins using functions. For example, in our case it isn't possible to cover the value 7 for x, because x always has to be smaller than y. Such a language feature might be a nice addition in the next version of the standard.

One thing we still need to do is update our bin generating function if the ranges for our fields change. In our current example, if we would change the type of x and y to bit [15:0] we would need to change the endpoints of all the loops. If SystemVerilog (better)supported reflection we could figure out these endpoints automatically.

The approach we've looked at above, while not 100% bulletproof, is still very useful because it avoids the need for error prone manual modifications to the coverage code. When working with SystemVerilog, it keeps our coverage definitions in sync and it makes refining constraints a breeze. If you want to give it a try yourself, you can find the code on SourceForge.

Enum fields in UVM_REG

For some time now, I've been mulling over the problem of storing register field values as enumerations. Enumerations are a very handy tool to improve code readability. Design specifications often make use of them too. If our verification environments could handle enumerated values for register fields we wouldn't have to go back and forth to the specification to decode bits when trying to figure out, for example, how to start the operations that we want or what results we got.

As we already know, fields in UVM_REG are first class objects. There is an own class, uvm_reg_field, used to model them. On the other hand, in vr_ad, fields are merely members of the register struct. They can be of any scalar type and the register will handle packing and unpacking itself.

A big advantage that vr_ad has is that fields can be of enumerated types. This isn't possible out of the box when using UVM_REG. That's because uvm_reg_field is supposed to be as generic as possible and only stores values as bit vectors. What those bit vectors represent is supposed to be a layer on top of the physical representation. Let's build a new register field class that can do this. I've chosen the name vgm_reg_enum_field since I don't have the authority to create classes with the uvm_* prefix.

We'll make our class a child of uvm_reg_field, so that the base class can handle the heavy lifting of interacting with other register layer classes. Users of our classes would mostly be interested in working with the field's desired value, for which we'll define a new API.

The uvm_reg_field class provides a value field which can be used for randomizing the value that we want driven. This field is of type uvm_reg_data_t, which is simply a bit vector. We'll need another such field that is of the enumerated type our field is supposed to hold. Since we want our class to handle any enumerations, we'll need the type being stored to be a parameter:

class vgm_reg_enum_field #(type T) extends uvm_reg_field;
  rand T value;

  // ...
endclass

By defining a new class member called value inside our new class we're effectively hiding the one from uvm_reg_field. Generally, variable hiding is frowned upon and this post makes a good case as to why, but in this case it kind of feels right (though I'm pretty sure Puneet will be upset with me). I'd rather have the old member hidden so that it isn't possible to constrain raw values.

We've made our enum type a parameter, but we need to make sure that its width is compatible to the register field's size. The size is set within the configure(...) function, so we'll extend it to check it:

class vgm_reg_enum_field #(type T) extends uvm_reg_field;
  // ...

  function void configure(uvm_reg parent, int unsigned size,
    int unsigned lsb_pos, string access, bit volatile, uvm_reg_data_t reset,
    bit has_reset, bit is_rand, bit individually_accessible
  );
    if (size != $bits(T))
      `uvm_fatal("SIZERR", "Size and enum width don't match")
    super.configure(parent, size, lsb_pos, access, volatile, reset, has_reset,
      is_rand, individually_accessible);
  endfunction

  // ...
endclass

The configure(...) function is, however, non-virtual, so it won't be possible to do any sort of type overriding and have our consistency check executed. I'm sure glad they made get_parent() and other "useful" functions virtual, but not this one... We could also add the check inside the get_n_bits() function, since that will be called when the parent register is being created to check for overlaps:

  virtual function int unsigned get_n_bits();
    int unsigned size = super.get_n_bits();
    if (size != $bits(T))
      `uvm_fatal("SIZERR", "Size and enum width don't match")
    return size;
  endfunction

This isn't a nice solution, but it's pragmatic.

We also need to take into account the is_rand argument to configure(...). Again, since the function isn't virtual, doing anything there won't be enough. We can extend the pre_randomize() function and set the rand_mode based on the rand_mode configured for the base class' value field:

  function void pre_randomize();
    super.pre_randomize();
    value.rand_mode(super.value.rand_mode());
  endfunction

We also need to handle the field's reset value. We can cheat and pass it into configure(...), but note that this still allows us to pass in a raw value. Reset values can also be set using set_reset(...), but it also takes a uvm_reg_data_t argument. We need a function that can only accept an enumerated value. Since SystemVerilog doesn't allow function overloading to create a new set_reset(...) function that takes an enum argument, we'll need to use a new name. An idea would be set_reset_enum(...):

  virtual function void set_reset_enum(T value, string kind = "HARD");
    super.set_reset(uvm_reg_data_t'(value), kind);
  endfunction

This new function is a thin wrapper around the original set_reset(...) function, but it forces the user to pass in an enum argument. Since we're on the topic, the current implementation of uvm_reg_field blatantly ignores user errors when providing input. When setting stuff, it will merrily chop of most significant bits from arguments to truncate them to the field's size, leaving the user the fun of having to debug this. Not nice...

We can also create a complementary get_reset_enum() function to return the reset value in a strongly typed form:

  virtual function T get_reset_enum(string kind = "HARD");
    return T'(get_reset(kind));
  endfunction

Aside from randomizing the field's value, the user can set a desired value using the set(...) function. We'll need to extend this function to also update our new value field:

  virtual function void set(uvm_reg_data_t value, string fname = "",
    int lineno = 0
  );
    super.set(value, fname, lineno);
    this.value = T'(super.value);
  endfunction

For the corresponding get() function, we don't have to do anything, but to satisfy my paranoia we could add a check to make sure that both desired values (the original and the overridden one) are consistent:

  virtual function uvm_reg_data_t get(string fname = "", int lineno = 0);
    if (value != bits2enum(super.value))
      `uvm_fatal("VALERR", "Inconsistend desired values")
    return super.get(fname, lineno);
  endfunction

Similarly to the set/get_reset_enum(...) functions, we can provide strongly typed versions of set(...)/get():

  virtual function void set_enum(T value, string fname = "", int lineno = 0);
    set(uvm_reg_data_t'value, fname, lineno);
  endfunction


  virtual function T get_enum(string fname = "", int lineno = 0);
    return T'(get(fname, lineno));
  endfunction

The do_predict(...) function should also update the desired value, so it also needs to be extended:

  virtual function void do_predict(uvm_reg_item rw,
    uvm_predict_e kind = UVM_PREDICT_DIRECT, uvm_reg_byte_en_t be = -1
  );
    super.do_predict(rw, kind, be);
    this.value = bits2enum(super.value);
  endfunction

Finally, the get_mirrored_value() could use a strongly typed counterpart:

  virtual function T get_mirrored_value_enum(string fname = "",
    int lineno = 0
  );
    return bits2enum(get_mirrored_value(fname, lineno));
  endfunction

One thing I've been avoiding is asking what would happen if we tried to set a raw value that isn't defined in the enum.For example, if we had a 2-bit enum type with only 3 literals, what would happen if we set the value 3? I'd expect the simulator to flag an error, something along the lines of "can't convert". Unfortunately, this isn't what happens. I guess we'll have to handle this in a different way.

We'll need to replace all casts from uvm_reg_data_t to the enum type with our own function that can detect conversion errors. The LRM makes a distinction between using T'(...) (called a static cast) and $cast(...) (called a dynamic cast). In our conversion function we could call $cast(...) and if it fails we could issue a fatal error:

  protected virtual function T bits2enum(uvm_reg_data_t value);
    if (!$cast(bits2enum, value))
      `uvm_fatal("CASTERR", { "In field '", get_name(), "': ",
        $sformatf("Requested value 'b%0b not mapped to enum literal", value) })
  endfunction

By using this instead of static cast we might get slightly slower code, but it's a price worth paying.

The situation we looked at above does raise an interesting question. In some designs we can actually have the case that multiple bit representations of a register field do the same thing. For example, let's consider a field who's values are encoded using a priority encoding scheme, where the first set bit determines what operation will be performed:

typedef enum bit[2:0] {
  CONTINUE = 3'b001, STOP = 3'b010, START = 3'b100 } operation_e;

In this case, when bit 2 is set, a START will be executed, regardless of what the other bits contains. If bit 1 is set and bit 2 is cleared, then a STOP will be executed. A CONTINUE will only be executed if only bit 0 is set. For such a field, we actually want to test that writing 3'b101, for example, still triggers a START.

What we could do is map all of the values of the enum type. This is easily done in SystemVerilog:

typedef enum bit[2:0] {
  CONTINUE = 3'b001, STOP[2], START[4] } operation_e;

The operation_e enum will have a CONTINUE literal, followed by STOP0, STOP1, START0, START1, START3 and START4. Handling all of these values inside generation code (that users write in sequences) or modeling code (that is used for reference modeling) is going to be pretty difficult. We'd need a mess of if and/or case statements.

A better idea is to have functions inside the register field class that can convert to and from the bit and enum representations.This new field class could inherit from the vgm_reg_enum_field class and extend the bits2reg(...) function to do a many-to-one style conversion:

class multiply_mapped_enum_field extends vgm_reg_enum_field #(operation_e);
  protected virtual function operation_e bits2enum(uvm_reg_data_t value);
    if (value[2])
      return START;
    if (value[1])
      return STOP;
    if (value[0])
      return CONTINUE;
    `uvm_fatal("VALERR", { "In field '", get_name(), "': ",
      $sformatf("Illegal value 'b%0b", value) })
  endfunction

  // ...
endclass

The advantage to doing it this way is that any modeling code the user writes doesn't need to care that START can be executed via multiple bit representations.

At the same time, to simplify generation code, converting from enums to bits is a one-to-many problem. From an information theory point of view, this involves creating new "information" to fill the gaps. Constrained randomization can be used to fill those gaps:

  protected virtual function uvm_reg_data_t enum2bits(operation_e value);
    if(!std::randomize(enum2bits) with {
      enum2bits[`UVM_REG_DATA_WIDTH - 1:3] == 0;
      value == START -> enum2bits[2] == 1;
      value == STOP -> enum2bits[2:1] == 2'b01;
      value == CONTINUE -> enum2bits[2:0] == 3'b001;
    })
      `uvm_fatal("RANDERR", "Randomization error")
  endfunction

This implies changing the vgm_reg_enum_field base class to handle any such conversions using such a enum2bits(...) function. It's implementation is trivial when the values aren't multiply-mapped. We should be careful where we use this function though. It would make little sense to use any kind of random values when trying to set reset values, for example, but for set_enum(...) it definitely makes sense.

We could also add enum wrappers for the read/write/mirror/predict(...) tasks, but these are only used for starting accesses. It's pretty uncommon to only access a single field so we won't look at it now, but this should be pretty straightforward to implement.

Using enumerated values together with the register access layer has the potential to make sequences and modeling code much more readable. The UVM BCL implementation and the language itself don't make it easy on us, though. You can download the full code for vgm_reg_enum_field from SourceForge, including the example on how to implement multiply-mapped enum literals. It's not production grade just yet, as it would need to be beta tested on a real project, but if you do use it get in touch and share your experiences.

Fun and Games with CRV: Draw This Without Lifting Your Pencil

It's time for another installment in the "Fun and Games with CRV" series. I love doing these posts because there's something very engaging in modeling all sorts of problems as constraints. This time we're going to look at how to draw a barn without lifting our pencil from the paper and without doubling back. This wikiHow post shows us two ways how we could do that. Now lets see if we can write a solver that can find either of these solutions.

This problem is different from the other puzzle we've looked at before because it has a "time" component. We make moves one after the other and the order in which we make them limits what we can do in the next step. We know exactly how many moves we need to make; this is the number of edges the drawing has. This makes it easier to model, in comparison to more difficult problems where the number of steps is unknown.

While we are looking at how to draw a barn, this kind of puzzle is pretty widespread. Why not implement a more generic solver that can draw any type of figure? We can do this by splitting the solver part (the constraints) from the actual drawing we want to make. Such a drawing is merely a collection of edges, which connect two vertices each. These edges and vertices form a graph and what we want is to traverse it, by taking each edge exactly once. While for the drawing itself the direction of the edges doesn't matter (which is the start or the end vertex), it is important for how we draw the figure. We'll see how this impacts the solver later.

We'll encapsulate the task of modeling such a graph and the constraints needed to traverse it inside an own class. This drawer class (not the best of names, I admit) will provide a protected method that subclasses can call to define the edges of the drawing:

virtual class drawer;
  typedef struct {
    rand vertex_t v1;
    rand vertex_t v2;
  } edge_t;

  protected function void add_edge(vertex_t vertex1, vertex_t vertex2);
    // ...
  endfunction

  // ...
endclass

My first try was to store all of the edges inside an array and add a constraint to try and randomly select one from the list:

virtual class drawer;
  local edge_t edges[$];
  local edge_t dummy_edge;

  constraint choose_existing_edges {
    dummy_edge inside { edges };
  }
endclass

This would have been too easy and probably have made for too short a post. "Fortunately", the SystemVerilog LRM doesn't allow this kind of construct, restricting us to using only singular types with the inside operator (integers, bit vectors, enums, etc.). We'll need to store the connected vertices in some other way if we want to be able to solve this problem. The best way (I could think of) is an associative array of queues indexed by the vertex and containing a list of all other vertices it's connected to directly via edges:

virtual class drawer;
  typedef int unsigned vertex_t;
  typedef vertex_t connections_t[$];

  local connections_t connections[vertex_t];
endclass

Let's look at an example:

In the drawing above, this is what the connections matrix would contain:

1 : { 2, 3, 4 }
2 : { 1 }
3 : { 1 }
4 : { 1, 5 }
5 : { 4 }

We can add to this data structure from the add_edge(...) function:

virtual class drawer;
  protected function void add_edge(vertex_t vertex1, vertex_t vertex2);
    if (connections.exists(vertex1) && vertex2 inside { connections[vertex1] })
      $fatal(0, "Connection %0d -> %0d already exists", vertex1, vertex2);

    connect_vertices(vertex1, vertex2);
    connect_vertices(vertex2, vertex1);

    begin
      edge_t e;
      e.v1 = vertex1;
      e.v2 = vertex2;
      edges.push_back(e);
    end
  endfunction


  local function void connect_vertices(vertex_t src, vertex_t dest);
    if (connections.exists(src))
      connections[src].push_back(dest);
    else
      connections[src] = '{ dest };
  endfunction
endclass

The connect_vertices(...) function handles updating the array of connections. Even though the edges can't be used in constraints directly, we can still store them. The number of edges we add will be the number of steps we need to draw.

It's also a good idea to store a list of all the vertices we have in our drawing. This list we could easily extract from the connections array by taking all of its keys:

virtual class drawer;
  local vertex_t vertices[$];

  function void pre_randomize();
    vertex_t v;
    void'(connections.first(v));
    do
      vertices.push_back(v);
    while (connections.next(v));
  endfunction
endclass

At this point, it makes sense to try again and write a constraint that can select an edge from the ones we've added to the list. I wanted to try something fancy here:

virtual class drawer;
  constraint choose_existing_edge {
    dummy_edge.v1 inside { vertices } &&
    dummy_edge.v2 inside { connections[dummy_edge.v1] };
  }
endclass

The idea was to choose the first vertex at random. The second vertex we could then choose from the list of vertices connected to the first one. In theory, this is great, but in practice, this constraint doesn't work because the index we are using for connections (dummy_edge.v1) is a random variable itself and this doesn't seem to be allowed. I'm not entirely sure if this is a simulator limitation or if the LRM forbids it.

We shouldn't give up on the idea just yet. With a bit of massaging, we can get it to compile. In the second constraint expression we can just loop over all entries inside connections and stop when we've reached the one corresponding to our chosen "starting" vertex:

virtual class drawer;
  constraint choose_existing_edges {
    dummy_edge.v1 inside { vertices };

    foreach (connections[v])
      if (dummy_edge.v1 == v)
        dummy_edge.v2 inside { connections[v] };
  }
endclass

It's a little more code, but it does the job perfectly. Now we have a solid base to really start building our solver. We'll need to keep track of what edges we've already drawn and when. We'll store them in an array, where index 0 will be the first edge we drawn, index 1 the second and so on:

virtual class drawer;
  local rand edge_t edge_being_drawn[];
endclass

The first constraint we'll write is that each edge we draw actually exists in the drawing. We've already written such a constraint for one edge, so we'll just extend it to cover all of them:

virtual class drawer;
  constraint choose_existing_edges {
    foreach (edge_being_drawn[i])
      edge_being_drawn[i].v1 inside { vertices };

    foreach (edge_being_drawn[i])
      foreach (connections[v])
        if (edge_being_drawn[i].v1 == v)
          edge_being_drawn[i].v2 inside { connections[v] };
  }
endclass

Just choosing edges that exist inside the figure isn't enough. We have to make sure that the edges are unique. Here I tried some more fanciness than the language affords. This constraint, though short and sweet, also doesn't compile:

virtual class drawer;
  constraint choose_unique_edges {
    unique { edge_being_drawn };
  }
endclass

As with the inside operator, the unique operator also only works on integral types. I tried to outsmart the compiler by declaring the struct as packed, but then it can't be declared as rand so that won't get us anywhere. As before, we're just going to have to throw some more code at the problem:

virtual class drawer;
  constraint choose_unique_edges {
    foreach (edge_being_drawn[i])
      foreach (edge_being_drawn[j])
        if (i != j)
          !(edge_being_drawn[i].v1 == edge_being_drawn[j].v1 &&
            edge_being_drawn[i].v2 == edge_being_drawn[j].v2);

    foreach (edge_being_drawn[i])
      foreach (edge_being_drawn[j])
        if (i != j)
          !(edge_being_drawn[i].v1 == edge_being_drawn[j].v2 &&
            edge_being_drawn[i].v2 == edge_being_drawn[j].v1);
  }
endclass

As we already know from the previous post on array constraints we can replace a unique constraint with a double foreach. It's not enough to say that the starting or ending vertices be different. We also need to make sure that we're not backtracking. Going from vertex 1 to vertex 3 is the same edge when going from vertex 3 to vertex 1 (it's just the direction that's different).

One more constraint is missing to make the solution complete. We have to make sure that when going from one edge to another, the end vertex of the previous edge is the start vertex of the current edge. If we don't, then we're lifting our pencil from the paper. This is very easy to express:

virtual class drawer;
  constraint choose_connected_edges {
    foreach (edge_being_drawn[i])
      if (i > 0)
        edge_being_drawn[i].v1 == edge_being_drawn[i - 1].v2;
  }
endclass

Let's test it out by trying to draw a barn. Here's how the vertices are numbered:

The barn_drawer class only needs to define the edges using the add_edge(...) function:

class barn_drawer extends drawer;
  function new();
    add_edge(0, 1);
    add_edge(0, 2);
    add_edge(1, 2);
    add_edge(1, 3);
    add_edge(1, 4);
    add_edge(2, 3);
    add_edge(2, 4);
    add_edge(3, 4);
  endfunction
endclass

We just need to randomize an instance of barn_drawer and we should get the instructions we need to solve our puzzle. Sadly, things are never this easy. Immediately after putting all constraints together I got a constraint violation. After looking at the "choose" constraints over and over and hitting my head on the table, some time later I found what the problem was; it wasn't in my code. As in the first installment of the series, when solving Sudoku, a simulator bug reared its ugly head, but this time it wasn't as easy to pinpoint. I should probably consider moonlighting as a QA for an EDA company since I seem to draw such issues to me. Getting to the point, if we add this slight modification to the choose_unique_edges constraint it's going to make the clouds go away:

virtual class drawer;
  constraint choose_unique_edges {
    // ...

    foreach (edge_being_drawn[i])
      foreach (edge_being_drawn[j])
        // (Very) Possible bug in simulator
        if (i == j - 1)
          edge_being_drawn[i].v1 != edge_being_drawn[j].v2;
        else if (j == i - 1)
          edge_being_drawn[j].v1 != edge_being_drawn[i].v2;
        else

        // This condition should be enough by itself.
        if (i != j)
          !(edge_being_drawn[i].v1 == edge_being_drawn[j].v2 &&
            edge_being_drawn[i].v2 == edge_being_drawn[j].v1);
  }
endclass

And there we have it! Now we can solve any such "draw this without lifting your pencil" puzzle. We've also learned a bit more about the limitations of the SystemVerilog constraint language. I can't help thinking that the whole thing would have been much cleaner in e. I might try it out in the future just to see. If someone else does it, it would be nice to compare. In the meantime, you can find the code on SourceForge if you want to experiment drawing other figures.