Monday, November 17, 2014

Experimental Cures for Flattened Register Definitions in vr_ad

On my current project, I had an issue with my register definitions. Quite a few of my DUT's registers where just instances of the same register type. My vr_ad register definitions were generated by a script, based on the specification, a flow that I'm pretty sure is very similar to what most of you also have. Instead of generating a nice regular structure, this script created a separate type for each register instance. What resulted was a flattened structure where I'd, for example, get one instance each of registers SOME_REG0, SOME_REG1, SOME_REG2, instead of three instances of SOME_REG. I was lucky enough to be able to (partly) change the definitions by patching them by hand.

Someone on StackOverflow had the same problem, but didn't have the luxury of being able to fix it like I did. They weren't allowed to touch the code as I'm guessing it probably belonged to a different team. They probably also had a lot of legacy code that was using those flattened register definitions. This made me want to do an experimental post on how to best cope with such an issue.

Naturally the best thing to do is to fix the underlying problem of the registers getting flattened, but that might not be possible, so let's look at how to fix the symptoms.

To be able to do any kind of serious modeling, we need to be able to program generically. We can't (easily) do this if each register is an own type. I've tried to think of how to best handle this from a maintainability point of view. As a bonus requirement, we'd also like it that when the register definitions do get fixed (i.e. the generation flow gets updated) we have to make as few changes as possible to the modeling code.

Enough with the stories, let's get our hands dirty. As always, we'll start small, but think big. We'll go through a few iterations, look at where we're lacking and gradually refine our approach.

Let's say we have a device that can operate with shapes. Part of its functionality involves doing stuff with triangles. It can process multiple triangles at the same time, where each triangle is described by a register containing the lengths of its sides. Our DUT does computations on the triangles, based on these values. For example, it can compute the areas of the triangles. We want to check that what the DUT writes out is correct so we need to model these computations.

We have a trusty script that can generate the register definitions from the specification (maybe an XML file). This script isn't very well written and it doesn't know that all three TRIANGLE registers are just the same register instantiated 3 times (i.e. a regular structure), or maybe the information got lost in the XML somehow. This is what we get for our register definitions:

<'
extend vr_ad_reg_file_kind : [ GRAPHICS ];
extend GRAPHICS vr_ad_reg_file {
  keep size == 256;
  post_generate() is also {
    reset();
  };
};

reg_def TRIANGLE0 GRAPHICS 0x00 {
  reg_fld SIDE0 : uint(bits : 8);
  reg_fld SIDE1 : uint(bits : 8);
  reg_fld SIDE2 : uint(bits : 8);
};

reg_def TRIANGLE1 GRAPHICS 0x10 {
  reg_fld SIDE0 : uint(bits : 8);
  reg_fld SIDE1 : uint(bits : 8);
  reg_fld SIDE2 : uint(bits : 8);
};

reg_def TRIANGLE2 GRAPHICS 0x20 {
  reg_fld SIDE0 : uint(bits : 8);
  reg_fld SIDE1 : uint(bits : 8);
  reg_fld SIDE2 : uint(bits : 8);
};
'>

Our reference model will contain a pointer to the register file:

<'
struct flattened_graphics_model {
  graphics_regs : GRAPHICS vr_ad_reg_file;
};
'>

The reference model needs to be able to compute the area of each triangle. As a first idea, we create a method for each triangle that implements Heron's formula:

<'
extend flattened_graphics_model {
  get_triangle0_area() : real is {
    var triangle0 := graphics_regs.triangle0;
    var half_per : real = 0.5 *
      (triangle0.SIDE0 + triangle0.SIDE1 + triangle0.SIDE2);
    result = sqrt(
      (half_per - triangle0.SIDE0) *
      (half_per - triangle0.SIDE1) *
      (half_per - triangle0.SIDE2) *
      half_per
    );
  };
  
  get_triangle1_area() : real is {
    var triangle1 := graphics_regs.triangle1;
    var half_per : real = 0.5 *
      (triangle1.SIDE0 + triangle1.SIDE1 + triangle1.SIDE2);
    result = sqrt(
      (half_per - triangle1.SIDE0) *
      (half_per - triangle1.SIDE1) *
      (half_per - triangle1.SIDE2) *
      half_per
    );
  };
  
  get_triangle2_area() : real is {
    var triangle2 := graphics_regs.triangle2;
    var half_per : real = 0.5 *
      (triangle2.SIDE0 + triangle2.SIDE1 + triangle2.SIDE2);
    result = sqrt(
      (half_per - triangle2.SIDE0) *
      (half_per - triangle2.SIDE1) *
      (half_per - triangle2.SIDE2) *
      half_per
    );
  };
};
'>

We can immediately see a problem with this approach. We've implemented the formula in three different places. This means that should something change, we have three places to fix. Now, Heron's formula changing is a pretty unlikely event, but should we have a different computation to perform here the discussion stands.

What we can do is extract the part that computes the actual area as an own method, that takes the three sides as its arguments:

<'
get_triangle_area(side0 : uint, side1 : uint, side2 : uint) : real is {
  var half_per : real = 0.5 * (side0 + side1 + side2);
  result = sqrt(
    (half_per - side0) *
    (half_per - side1) *
    (half_per - side2) *
    half_per
  );
};
'>

We can simplify the three methods from before to just call this generic method:

<'
get_triangle0_area() : real is {
  var triangle := graphics_regs.triangle0;
  result = get_triangle_area(triangle.SIDE0, triangle.SIDE1,
    triangle.SIDE2);
};

get_triangle1_area() : real is {
  var triangle := graphics_regs.triangle1;
  result = get_triangle_area(triangle.SIDE0, triangle.SIDE1,
    triangle.SIDE2);
};

get_triangle2_area() : real is {
  var triangle := graphics_regs.triangle2;
  result = get_triangle_area(triangle.SIDE0, triangle.SIDE1,
    triangle.SIDE2);
};
'>

At least this way we've centralized the computation part to one location. The number of such methods will grow linearly, though, with the number of TRIANGLE registers. This means that for n triangles we'll need n methods to compute the areas.

Let's add a new requirement: our DUT is also able to compute which triangle is the largest and we need to model that too. We can define a new method to do that based on the areas:

<'
largest() : uint is {
  var areas : list of real;
  areas.add(get_triangle0_area());
  areas.add(get_triangle1_area());
  areas.add(get_triangle2_area());
  
  result = areas.max_index(it);
};
'>

In this method, the number of calls to get_triangleX_area() also grows with the number of triangles. Moreover, if we want to be able to find out which triangle is the smallest, the method for that would have to look like this:

<'
smallest() : uint is {
  var areas : list of real;
  areas.add(get_triangle0_area());
  areas.add(get_triangle1_area());
  areas.add(get_triangle2_area());
  
  result = areas.min_index(it);
};
'>

Pretty much the same as largest(), isn't it? In this setup, adding a single triangle would require adding a new method for the area and changing two others. That's not very maintainable. We can use the same trick we did for the area computation and pull out computing the list of areas to it's own method, while simplifying the largest() and smallest() methods:

<'
get_triangle_areas() : list of real is {
  result.add(get_triangle0_area());
  result.add(get_triangle1_area());
  result.add(get_triangle2_area());
};

largest() : uint is {
  var areas := get_triangle_areas();
  result = areas.max_index(it);
};

smallest() : uint is {
  var areas := get_triangle_areas();
  result = areas.min_index(it);
};
'>

Now we only need to update the get_triangle_areas() method when adding a new triangle. Not much of an improvement, but every little thing counts when you're potentially dealing with a large number of triangles.

While we may have things sorted out for areas, we get a new requirement. Our DUT can also compute perimeters and tell us which triangle is the longest and which one is the shortest. This means we'll need to add a similar set of methods to handle this aspect, based on the examples from above:

<'
extend flattened_graphics_model {
  get_triangle_perimeter(side0 : uint, side1 : uint, side2 : uint) : uint is {
    result = side0 + side1 + side2;
  };
  
  get_triangle0_perimeter() : uint is {
    var triangle := graphics_regs.triangle0;
    result = get_triangle_perimeter(triangle.SIDE0, triangle.SIDE1,
      triangle.SIDE2);
  };
  
  get_triangle1_perimeter() : uint is {
    var triangle := graphics_regs.triangle1;
    result = get_triangle_perimeter(triangle.SIDE0, triangle.SIDE1,
      triangle.SIDE2);
  };
  
  get_triangle2_perimeter() : uint is {
    var triangle := graphics_regs.triangle2;
    result = get_triangle_perimeter(triangle.SIDE0, triangle.SIDE1,
      triangle.SIDE2);
  };
  
  get_triangle_perimeters() : list of uint is {
    result.add(get_triangle0_perimeter());
    result.add(get_triangle1_perimeter());
    result.add(get_triangle2_perimeter());
  };
  
  longest() : uint is {
    var perimeters := get_triangle_perimeters();
    result = perimeters.max_index(it);
  };
  
  shortest() : uint is {
    var perimeters := get_triangle_perimeters();
    result = perimeters.min_index(it);
  };
};
'>

Adding just one measly triangle is starting to become a real pain. What would be awesome is being able to just add one line of code every time a new triangle gets added and be done with it. Well, thanks to our good friends, the macros, this is possible.

What we notice is that the code is very regular. Aside from the indices, the method bodies look remarkably similar. This means that for the area aspect we can create the following macro:

<'
define <triangle_area_utils'statement> "triangle_area_utils <num>" as {
  extend flattened_graphics_model {
    get_triangle<num>_area() : real is {
      var triangle := graphics_regs.triangle<num>;
      result = get_triangle_area(triangle.SIDE0, triangle.SIDE1,
        triangle.SIDE2);
    };
    
    get_triangle_areas() : list of real is also {
      result.add(get_triangle<num>_area());
    };
  };
};
'>

Adding a new triangle is now as easy as just expanding the macro with the appropriate argument:

<'
triangle_area_utils 0;
triangle_area_utils 1;
triangle_area_utils 2;
'>

We could define a similar macro for the perimeter aspect (I won't show it here). While we have made adding new triangles easier, we've also shot ourselves in the foot. Excessive use of macros is a code smell because it can be very difficult to understand what code gets expanded in the background. Also, it makes the code more difficult to refactor, since we can't rely on fancy IDE features.

If we analyze the code up now we see that one of our main problems is that each triangle is stored in an individual field. This means that there's no way to access a triangle from a method by just passing in the index of the triangle (0, 1, 2, etc.). If we could do this, we could get rid of all our get_triangleX_area() methods.

A way of doing this is using the reflection API. Reflection allows us, among others, to get a field of a struct by using only the name of that field, specified as a string. In our case, we know that our register file contains fields named triangle0, triangle1, triangle2, etc. We can use the reflection API to extract the field that contains contains the appropriate index as its suffix:

<'
extend flattened_graphics_model {
  num_triangles : uint;
    keep num_triangles == 3;
  
  get_triangle_reg(idx : uint) : vr_ad_reg is {
    assert idx < num_triangles;
    
    var regs_type := rf_manager.get_exact_subtype_of_instance(graphics_regs);
    
    var triangle_reg_field :=
      regs_type.get_fields().first(it.get_name() == appendf("triangle%d", idx));
    assert triangle_reg_field != NULL;
    
    assert triangle_reg_field.get_type() ==
      rf_manager.get_type_by_name(appendf("TRIANGLE%d'kind vr_ad_reg", idx));
    result =
      triangle_reg_field.get_value(graphics_regs).get_value().unsafe();
  };
};
'>

The way to use the reflection API is to get the representation of our register file from the rf_manager singleton. What we'll end up with is a struct of type rf_struct that understands what fields, methods, etc. the register file has. Out of this we can extract a representation of the field for the triangle that interests us, of type rf_field. Based on this field we can construct our return value. How exactly this happens is explained in the documentation and in this excellent post from the Specman R&D team. Have a look at those resources for more details on how to use the reflection interface.

After we've gotten an instance of our desired register, we can use this to compute the area. We can do away with the get_triangleX_area() methods and replace them with one get_triangle_area_by_index(...) method:

<'
get_triangle_area_by_index(idx : uint) : real is {
  assert idx < num_triangles;
  var reg := get_triangle_reg(idx);
  var reg_type := rf_manager.get_exact_subtype_of_instance(reg);
  
  var side0_field := reg_type.get_fields().first(it.get_name() == "SIDE0");
  assert side0_field != NULL;
  assert side0_field.get_type() == rf_manager.get_type_by_name("uint(bits:8)");
  var side0 : uint = side0_field.get_value(reg).get_value().unsafe();
  
  var side1_field := reg_type.get_fields().first(it.get_name() == "SIDE1");
  assert side1_field != NULL;
  assert side1_field.get_type() == rf_manager.get_type_by_name("uint(bits:8)");
  var side1 : uint = side1_field.get_value(reg).get_value().unsafe();
  
  var side2_field := reg_type.get_fields().first(it.get_name() == "SIDE2");
  assert side2_field != NULL;
  assert side2_field.get_type() == rf_manager.get_type_by_name("uint(bits:8)");
  var side2 : uint = side2_field.get_value(reg).get_value().unsafe();
  
  result = get_triangle_area(side0, side1, side2);
};
'>

Because the return value of get_triangle_reg(...) is of type vr_ad_reg, we can't reference the SIDEx fields directly (as these are defined under when subtypes). We can't cast the value to any of these subtypes, because we would need n cast statements (the very thing we want to avoid). We can use the same method as before to get the values of the sides via the reflection interface. The resulting code isn't pretty, but it works. Can we do better, though?

Of course we can! An essential observation to make here is that all triangle register types contain the same fields, whether they are of type TRIANGLE0 or TRIANGLE1 or TRIANGLE2. We could do all of our operations using only a variable of one of these types, provided that we fill it up with the appropriate values for the sides. That is, a TRIANGLE0 with sides 1, 2 and 3 has the same area as a TRIANGLE1 with the same sides. With this idea in mind, we can do the following:

<'
get_triangle_area_by_index(idx : uint) : real is {
  assert idx < num_triangles;
  var triangle : TRIANGLE0 vr_ad_reg = new;
  triangle.write_reg_rawval(get_triangle_reg(idx).read_reg_rawval());
  result = get_triangle_area(triangle.SIDE0, triangle.SIDE1,
    triangle.SIDE2);
};
'>

We can just create a variable of type TRIANGLE0 and fill it up with the contents of our desired register. We can then reference the SIDE fields directly, without the need for all of that messy reflection code. The price we pay for this convenience, however is in essence a copy operation. Whether this is slower than using the reflection interface I can't say (though I suspect it isn't), but it is in any case cleaner.

Our largest() method becomes pretty trivial to write:

<'
largest() : uint is {
  var areas : list of real;
  for i from 0 to num_triangles - 1 {
    areas.add(get_triangle_area_by_index(i));
  };
  
  result = areas.max_index(it);
};
'>

Not only that, but we can now handle any number of triangles without increasing the number of lines in the code. The only modification we need to make is to set the num_triangles field to the appropriate value.

I'd propose one final refactoring step. Why do we have to define the methods that compute the area and the perimeter inside the reference model? A triangle register contains all of the information required to compute these values. Seeing as how we'll just be using the TRIANGLE0 subtype in our code, we can extend that to contain a get_area() method:

<'
extend TRIANGLE0 vr_ad_reg {
  get_area() : real is {
    var half_per : real = 0.5 * (SIDE0 + SIDE1 + SIDE2);
    result = sqrt(
      (half_per - SIDE0) *
      (half_per - SIDE1) *
      (half_per - SIDE2) *
      half_per
    );
  };
};
'>

Getting the area of a triangle becomes just:

<'
print graphics_model.get_triangle_reg(0).get_area();
'>

We can also rewrite the largest() method as:

<'
extend flattened_graphics_model {
  get_triangle_regs() : list of TRIANGLE0 vr_ad_reg is {
    for i from 0 to num_triangles - 1 {
      result.add(get_triangle_reg(i));
    };
  };
  
  largest() : uint is {
    var triangles := get_triangle_regs();
    result = triangles.max_index(it.get_area());
  };
};
'>

Of course, we can do the same for the perimeter aspect (not shown here). Let's take a moment to see what we've achieved. We've managed to program our computations in a generic way, by relying on methods that take the index of a register as a parameter. This saves us a lot of typing because we don't have to define a method that accesses each field. We've also nicely encapsulated our methods: all methods that refer to a single triangle (get_area() and get_perimeter()) are defined in the triangle register struct, while the methods that refer to all triangles are encapsulated in the reference model struct.

Further above, I've mentioned the bonus requirement that we want our resulting code to look as similar as possible to the case where the register definitions aren't flattened. Let's see how our reference model would look in the ideal case.

First we have to start with our register definitions:

<'
reg_def TRIANGLE {
  reg_fld SIDE0 : uint(bits : 8);
  reg_fld SIDE1 : uint(bits : 8);
  reg_fld SIDE2 : uint(bits : 8);
};


extend GRAPHICS vr_ad_reg_file {
  triangles[3] : list of TRIANGLE vr_ad_reg;
  
  add_registers() is also {
    for each (triangle) in triangles {
      add_with_offset(index * 0x10, triangle);
    };
  };
};
'>

Since there is only one triangle struct, we extend that to add the get_area() method:

<'
extend TRIANGLE vr_ad_reg {
  get_area() : real is {
    var half_per : real = 0.5 * (SIDE0 + SIDE1 + SIDE2);
    result = sqrt(
      (half_per - SIDE0) *
      (half_per - SIDE1) *
      (half_per - SIDE2) *
      half_per
    );
  };
};
'>

Finding the largest and the smallest triangles is easily done by iterating over the triangles list of the register file:

<'
extend compacted_graphics_model {
  largest() : uint is {
    var triangles := graphics_regs.triangles;
    result = triangles.max_index(it.get_area());
  };
  
  smallest() : uint is {
    var triangles := graphics_regs.triangles;
    result = triangles.min_index(it.get_area());
  };
};
'>

Notice that we don't need the get_triangle_regs() method anymore, as we already have our triangles organized in a list. If we were to implement the last proposal, once our register definitions would be fixed, migrating to the new structure would only require some minor search and replace operations. This goes to show that starting off on the wrong foot doesn't mean we're completely out of the dance. With some extra work, we can get very close to the ideal solution, but we have to be willing to compromise a bit on simulation speed. Still, it's better than compromising on maintainability and getting stuck in an endless loop of bad coding style.

I hope you found this post useful. I've posted the code to SourceForge for reference. Stay tuned for more!

2 comments:

  1. You can also try this:

    get_reg_side(reg_index : uint, side_index : uint) : uint is {
    var reg := graphics_model.graphics_regs.get_reg_by_kind(appendf("TRIANGLE%d", reg_index).as_a(vr_ad_reg_kind));
    var fld_name : string = appendf("SIDE%d", side_index);
    var field_info := reg.static_info.fields_info.first(it.fld_name == fld_name);
    return reg.get_cur_value()[(field_info.fld_fidx + field_info.fld_size - 1):field_info.fld_fidx];
    };

    You should also include protection for the values of reg_index and side_index

    ReplyDelete
    Replies
    1. You're right! This also removes the need to do reflection. I was so fixed on that idea that I forgot about get_reg_by_kind(...).

      What I also usually do is define an extra method inside vr_ad_reg, called get_field_by_name(fld_name : string). This basically does what your snippet does (including asserts, etc.). I find it really handy.

      Delete