Possibility of Dynamic Type Generator in BSV

[ChienTeLi]

Since I started using BSV, I have truly enjoyed working with it as my development HDL.

However, I have encountered a somewhat unfortunate limitation regarding dynamic generation capabilities. Languages like Chisel3 and even traditional Verilog can dynamically generate corresponding hardware types, whereas in BSV, everything is static. The advantage of this approach is clear: it provides excellent design control and reduces errors.

Although it is possible to use preprocessing tools like Python to assist with dynamic generation, it does not seem as direct or straightforward.

As BSV continues to evolve, I wonder if there is any possibility of adding syntax specifically for generating numeric types, types, or even interfaces. While I understand this may not be easy, such a feature would greatly enhance parameterization and make hardware generation even more powerful.

ex1.

Within a module, multiple submodules may need to be instantiated, each with a different type. However, all these types can be determined based on a specific type or numeric type parameter.

ex2.

The types used in an interface could also be determined by an input numeric type, which specifies both the number of elements and their respective types.

[quark17]

These are all possible in BSV, in various ways. The examples are vague, though, so I'm not sure what to suggest, beyond looking at typeclasses, provisos, and numeric type constructors. Perhaps you can make it more concrete by giving an example of code that you want to write, even if the types or syntax doesn't work?

For example, here is one way of generating a new type using provisos:

module mkMod (Ifc#(n))
  provisos (Add#(n,1,m));

  Reg#(Bit#(n)) rg1 <- mkRegU;
  Reg#(Bit#(m)) rg2 <- mkRegU;

Here, the numeric size n of the interface is provided by the context where mkMod is instantiated, and the type variable m is determined to be n plus one. You can also use this type in specific places without giving it a name:

module mkMod (Ifc#(n));

  Reg#(Bit#(n)) rg1 <- mkRegU;
  Reg#(Bit#(TAdd#(n,1))) rg2 <- mkRegU;

In the provisos clause, you can use various built-in numeric type classes, but you can also do more complex generation by defining your own typeclasses. When you define a type class, you can use a dependencies clause to indicate which variables are generated from the others. For example:

typeclass MyTypeClass#(a,b) dependecies(a determines b);
  ...
endtypeclass

instance MyTypeClass#(X,Y);
  ...
endinstance

module mkMod (Ifc#(t1))
  provisos (MyTypeClass#(t1,t2));

In the above example, the mkMod module has a variable t1 that is given by the context, and type t2 is determined from that, because of the MyTypeClass proviso. The MyTypeClass declaration says that for a given a, there is a unique b that is determined from it. In the example, I've defined an instance for X paired with Y -- so once we know X, we know that the second type is Y.

To make the example more concrete, MyTypeClass could be the class of types a that are indexable, and b is the type of the index. So if a is MyBRAMInterface, then b would be MyBRAMIndex, but if a is MyOtherBRAMInterface, then b would be MyOtherBRAMIndex -- for example.

Are those the kind of things that you're asking for?

You can also do things like this:

module mkMod(Ifc#(n));

  Reg#(Bit#(32)) rg;

  if (valueOf(n) == 1) begin
    ... instantiate modules, rules, etc ...
    rg = ... ;
  end
  else if (valueOf(n) = 2) begin
    ...
    rg <- ... ;
  end
  else
    ...

Inside the case arms, you can instantiate things of any size. However, there are limitations, in that any types they touch from outside the case arm has to match. So, for example, rg has be of width 32, and can't be of different sizes in different arms. And n can't used as 1 in one arm and 2 in another arm. For that situation, type classes can again be used:

typeclass MkMod#(n);
  module mkMod(Ifc#(n));
endtypeclass

instance MkMod#(1);
  module mkMod(Ifc#(1));
    ...
  endmodule
endinstance

instance MkMod#(2);
  module mkMod(Ifc#(2));
    ...
  endmodule
endinstance

// Fall-through default
instance MkMod#(n);
  module mkMod(Ifc#(n));
    ...
  endmodule
endinstance

Does that help?

[ChienTeLi]

I apologize for not providing clear examples.
I understand type functions (such as TAdd) and the use of provisos for inferring types. I am still learning about typeclasses and their power in BSV.
I have encountered two scenarios where I wish to perform more complex type-level calculations or parameterizations, but have run into difficulties:

ex1. MergeSort Staging and Type-Level Calculation
In my MergeSort implementation, I pass the type td and the numeric type num into the top module, using num to infer how many stages are needed.

However, the required FIFO depth varies at each stage. While the FIFO itself can be configured using an Integer fifoDepth, if I want to optimize the counter within each stage, I need to implement different widths of them.

At this point, I am unable to determine the size based on stageIdx, nor can I use num to know which stage I am currently at.

package MergeSort;
import Logging::*;
import Probe::*;
import GetPut::*;
import Vector::*;
import FIFOF::*;
import BuildVector :: * ;
import BUtils :: * ;
import Connectable :: * ;

interface MergeSort#(type td, numeric type num);
    interface Put#(td) in;
    interface Get#(td) out;
endinterface


module mkMergeSortStage#(String order, Integer stageIdx)(MergeSort#(td, num))
    provisos(
        NumAlias#(TLog#(num), num_stage),
        NumAlias#(TExp#(TSub#(num_stage, 1)), max_fifo_size),
        Bits#(td, sz), 
        Ord#(td)
    );


    Integer group_size      = 2**stageIdx;
    Integer round_num       = (valueOf(num) - 1) / (2 * group_size) + 1; // ceil div
    Integer remain          = valueOf(num) - (round_num - 1) * 2 * group_size;
    Integer last_left_remain   = (remain < group_size) ? remain : group_size;
    Integer last_right_remain  = (remain > group_size) ? (remain - group_size) : 0;

    Reg#(Bit#(TLog#(num))) in_count <- mkReg(0);
    Reg#(Bit#(TLog#(TDiv#(num, 2)))) round_count <- mkReg(0);

    // TODO: each stage need different min count width
    Reg#(LUInt#(max_fifo_size)) left_count <- mkReg(0);
    Reg#(LUInt#(max_fifo_size)) right_count <- mkReg(0);

    let left_fifo <- mkUGSizedFIFOF(group_size+2);
    let right_fifo <- mkUGSizedFIFOF(valueOf(num)<2*group_size? valueOf(num)-group_size+2:group_size+2);

    let result_rwire <- mkRWire;
    let left_pop_pwire <- mkPulseWire;
    let right_pop_pwire <- mkPulseWire;


    let last_round = round_count == fromInteger(round_num-1);

    let left_total = last_round? fromInteger(last_left_remain): fromInteger(2**stageIdx);
    let right_total = last_round? fromInteger(last_right_remain): fromInteger(2**stageIdx);

    rule compare_rule;
        let left_data = left_fifo.first;
        let right_data = right_fifo.first;

        Bool left_valid = left_count!=left_total;
        Bool right_valid = right_count!=right_total;
        if(left_valid && right_valid) begin
            if(left_fifo.notEmpty && right_fifo.notEmpty) begin
                if(left_data < right_data) begin
                    if(order=="ascending") begin
                        result_rwire.wset(left_data);
                        left_pop_pwire.send;
                    end else begin
                        result_rwire.wset(right_data);
                        right_pop_pwire.send;
                    end
                end else begin
                    if(order=="ascending") begin
                        result_rwire.wset(right_data);
                        right_pop_pwire.send;
                    end else begin
                        result_rwire.wset(left_data);
                        left_pop_pwire.send;
                    end
                    
                end
            end
        end else if(left_valid) begin
            if(left_fifo.notEmpty) begin
                result_rwire.wset(left_data);
                left_pop_pwire.send;
            end
        end else if(right_valid) begin
            if(right_fifo.notEmpty) begin
                result_rwire.wset(right_data);
                right_pop_pwire.send;
            end
        end
    endrule

    Bool sel_in_left = in_count[stageIdx]==0;
    Bool sel_in_right = in_count[stageIdx]==1;
    Bool fifo_availble = sel_in_left && left_fifo.notFull || sel_in_right && right_fifo.notFull;

    interface Put in;
        method Action put(td val) if(fifo_availble);
            if(sel_in_left) left_fifo.enq(val);
            if(sel_in_right) right_fifo.enq(val);
            Bool last = in_count==fromInteger(valueOf(num)-1);
            in_count <= last? 0: in_count+1;
        endmethod
    endinterface
    
    interface Get out;
        method ActionValue#(td) get if(result_rwire.wget matches tagged Valid .get_data);
            if(left_count==left_total && (right_count==right_total-1) || (left_count==left_total-1) && right_count==right_total) begin
                round_count <= last_round? 0: round_count+1;
                left_count <= 0;
                right_count <= 0;
            end else begin
                if(left_pop_pwire) left_count <= left_count + 1;
                if(right_pop_pwire) right_count <= right_count + 1;
            end

            if(left_pop_pwire) left_fifo.deq;
            if(right_pop_pwire) right_fifo.deq;
            return get_data;
        endmethod
    endinterface

endmodule

// default:"ascending", "descending"
module mkMergeSort#(String order)(MergeSort#(td, num))
    provisos(
        NumAlias#((TLog#(num)), num_stage),
        Bits#(td, sz), 
        Ord#(td)
    );

    Vector#(num_stage, MergeSort#(td, num)) stage_inst = ?;

    for(Integer i=0; i<valueOf(num_stage); i=i+1) begin
        stage_inst[i] <- mkMergeSortStage(order, i);
        if(i!=0) mkConnection(stage_inst[i-1].out, stage_inst[i].in);
    end

    interface in = stage_inst[0].in;
    interface out = stage_inst[valueOf(num_stage)-1].out;

endmodule

endpackage

Perhaps this problem can be simplified as follows:

interface ShiftReg#(type td, numeric type num_stage);
    method Action _write(td d);
    method td _read;
endinterface

module mkShiftRegStage#(Integer idx)(ShiftReg#(td, num_stage))
    provisos( Bits#(td, sz) );
    Vector#(2**idx, Reg#(td)) shift_reg; // FIXME: Of course, 2**idx is not a numeric type

    method Action _write(td d);
        writeVReg(shift_reg, d);
    endmethod
    method _read = shift_reg[2**idx-1];
endmodule

module mkShiftReg(ShiftReg#(td, num_stage))
    provisos( Bits#(td, sz) );
    Vector#(num_stage, ShiftReg#(td, num_stage)) stage_inst = ?;

    for(Integer idx=0; idx<valueOf(num_stage); idx=idx+1) begin
        stage_inst[idx] <- mkShiftRegStage(idx);
        if(idx!=0) stage_inst[idx] <= stage_inst[idx-1];
    end

    method _write = stage_inst[0]._write;
    method _read = stage_inst[valueOf(num_stage)-1]._read;

endmodule

What I mean is, I wish to perform complex type-level calculations, similar to what we can do with Integer values. Is this possible now, or planned for the future?
As in your last example, perhaps I could enumerate all possible cases, but when using parameterization, it becomes somewhat unintuitive and not easy to reuse.

ex2. Parameterized AXIS Port Generation
This example comes from my experience implementing AXIS ports. At that time, I needed one AXIS slave port and multiple AXIS master ports. However, I wanted both the number of master ports and the number of ports for each to be parameterizable. As a result, I eventually used Python for preprocessing.

Below is a simplified version of the example:

Before python preprocessing:

package Broadcast;

import GetPut :: *;
import FIFO::*;
import BUtils::*;


typedef 2 NUM_CH;
typedef 10 IN_W;


typedef 2 OUT_W_PYGEN_IDX;
typedef 2 OUT_SHIFT_PYGEN_IDX;


interface Broadcast;
    interface Put#(Bit#(IN_W)) in;
    interface Get#(Bit#(OUT_W_PYGEN_IDX)) out_pygen_idx;
endinterface


module mkBroadcast(Broadcast);

    FIFO#(Bit#(IN_W)) in_fifo <- mkFIFO;
    FIFO#(Bit#(OUT_W_PYGEN_IDX)) out_pygen_idx_fifo <- mkFIFO;

    rule broadcast_rule;
        let data = in_fifo.first;
        in_fifo.deq;

        out_pygen_idx_fifo.enq(cExtend(data>>fromInteger(valueOf(OUT_SHIFT_PYGEN_IDX))));
    endrule

    interface in = toPut(in_fifo);
    interface out_pygen_idx = toGet(out_pygen_idx_fifo);

endmodule

endpackage

After python preprocessing:

package BroadcastGen;

import GetPut :: *;
import FIFO::*;
import BUtils::*;

typedef 2 NUM_CH;
typedef 8 IN_W;


typedef 4 OUT_W_0;
typedef 3 OUT_W_1;
typedef 3 OUT_SHIFT_0;
typedef 4 OUT_SHIFT_1;


interface BroadcastGen;
    interface Put#(Bit#(IN_W)) in;
    interface Get#(Bit#(OUT_W_0)) out_0;
    interface Get#(Bit#(OUT_W_1)) out_1;
endinterface


module mkBroadcastGen(BroadcastGen);

    FIFO#(Bit#(IN_W)) in_fifo <- mkFIFO;
    FIFO#(Bit#(OUT_W_0)) out_0_fifo <- mkFIFO;
    FIFO#(Bit#(OUT_W_1)) out_1_fifo <- mkFIFO;

    rule broadcast_rule;
        let data = in_fifo.first;
        in_fifo.deq;

        out_0_fifo.enq(cExtend(data>>fromInteger(valueOf(OUT_SHIFT_0))));
        out_1_fifo.enq(cExtend(data>>fromInteger(valueOf(OUT_SHIFT_1))));
    endrule

    interface in = toPut(in_fifo);
    interface out_0 = toGet(out_0_fifo);
    interface out_1 = toGet(out_1_fifo);

endmodule

endpackage

Any suggestions or best practices for achieving this kind of type-level computation or parameterization in BSV?
Thank you for your time and any insights you can provide!

[quark17]

I haven't yet had time to fully read your comment, but I will do that when I can. In the meantime, I can give a quick example of something that's possible, for part 1, in case it helps.

import Vector::*;

interface ShiftRegIfc#(type td, numeric type num_stage);
    method Action _write(td d);
    method td _read;
endinterface

typeclass ShiftReg#(numeric type num_stage);
    module mkShiftReg(ShiftRegIfc#(td,num_stage)) provisos(Bits#(td,sz));
endtypeclass

instance ShiftReg#(0);
  module mkShiftReg(ShiftRegIfc#(td,0)) provisos(Bits#(td,sz));
    Reg#(td) rg <- mkRegU;

    method _write = rg._write;
    method _read = rg._read;
  endmodule
endinstance

instance ShiftReg#(n)
provisos (Add#(m,1,n), ShiftReg#(m));
  module mkShiftReg(ShiftRegIfc#(td,n)) provisos(Bits#(td,sz));
    Vector#(TExp#(n),Reg#(td)) rgs <- replicateM(mkRegU);
    ShiftRegIfc#(td,m) ss <- mkShiftReg;

    method Action _write(td d);
      ss <= d;
      writeVReg(rgs, replicate(ss));
    endmethod
    method _read = rgs[valueOf(TExp#(n))-1];
  endmodule
endinstance

You rightfully pointed out that my example of typeclass instances had an explicit instance for every number. Hopefully this is a better example, using induction to get all possible values with only two instances. I confirmed that a module can be synthesized:

(* synthesize *)
module mkShiftReg_Bit8_2 (ShiftRegIfc#(Bit#(8),2));
  (* hide *)
  ShiftRegIfc#(Bit#(8),2) __i <- mkShiftReg;
  return __i;
endmodule

The instance names of the stages are not succinct, but that could possibly be fixed through the use of attributes or naming primitives.

It is also possible that we need more capabilities in BSC, but offhand I'm still unsure what that specifically would be. I'll need to find time to sit down and fully understand your example. Perhaps a type-level for-loop would help -- I rewrote your example using recursion, where the original was using a for-loop. In my code, I've put the entire body of the stages into the typeclass, but maybe that's unnecessary; perhaps a typeclass could just implement a generic for-loop, and take the body module as an argument.

For example, I tried to make function like replicate and replicateM but for types (mkTypeReplicate), however I've run into an issue that BSC's type system is not allowing a typeclass member to be polymorphic, and I'll need to figure that out:

import Vector::*;

interface ShiftReg#(type td);
    method Action _write(td d);
    method td _read;
endinterface

module mkShiftRegStage #(Bit#(num_stage) dummy) (ShiftReg#(td))
    provisos( Bits#(td, sz) );
    Vector#(TExp#(num_stage), Reg#(td)) shift_reg <- replicateM(mkRegU);

    method Action _write(td d);
        writeVReg(shift_reg, replicate(d));
    endmethod
    method _read = shift_reg[valueOf(TExp#(num_stage))-1];
endmodule

module mkShiftReg #(Bit#(num_stages) dummy) (ShiftReg#(td))
    provisos( Bits#(td, sz), TypeReplicate#(num_stages) );
    Vector#(num_stages, ShiftReg#(td)) stages <- mkTypeReplicate(mkShiftRegStage);

    method Action _write(td d);
      stages[0] <= d;
      for(Integer idx=1; idx<valueOf(num_stages); idx=idx+1) begin
        stages[idx] <= stages[idx-1];
      end
    endmethod
    method _read = stages[valueOf(num_stages)-1];
endmodule

typeclass TypeReplicate#(numeric type num_stages);
    module mkTypeReplicate#(function module#(ifc) mkMod(Bit#(n) dummy_n)) (Vector#(num_stages,ifc));
endtypeclass

instance TypeReplicate#(0);
    module mkTypeReplicate#(function module#(ifc) mkMod(Bit#(n) dummy_n)) (Vector#(0,ifc));
      return nil;
    endmodule
endinstance

instance TypeReplicate#(1);
    module mkTypeReplicate#(function module#(ifc) mkMod(Bit#(n) dummy_n)) (Vector#(1,ifc));
      Bit#(1) n_typearg = ?;
      ifc __i <- mkMod(n_typearg);
      return cons(__i,nil);
    endmodule
endinstance

instance TypeReplicate#(num_stages) provisos(Add#(num_stages_minus1,1,num_stages), TypeReplicate#(num_stages_minus1));
    module mkTypeReplicate#(function module#(ifc) mkMod(Bit#(n) dummy_n)) (Vector#(num_stages,ifc));
      Vector#(num_stages_minus1,ifc) is <- mkTypeReplicate(mkMod);
      Bit#(num_stages) n_typearg = ?;
      ifc __i <- mkMod(n_typearg);
      return cons(__i,is);
    endmodule
endinstance

[quark17]

Oh! Also note that you don't have to use Vector! If the size of the vector is what you want to dynamically generate, you can use List, which doesn't have its size as part of its type. For example:

import List::*;

interface ShiftReg#(type td);
    method Action _write(td d);
    method td _read;
endinterface

module mkShiftRegStage #(Integer idx) (ShiftReg#(td))
    provisos( Bits#(td, sz) );

    Integer num_regs = 2**idx;
    List#(Reg#(td)) rgs <- replicateM(num_regs, mkRegU);

    method Action _write(td d);
        for (Integer i=0; i<num_regs; i=i+1)
          rgs[i] <= d;
    endmethod
    method _read = rgs[num_regs-1];
endmodule

module mkShiftReg #(Integer num_stages) (ShiftReg#(td))
    provisos( Bits#(td, sz) );

    List#(ShiftReg#(td)) stages <- mapM(mkShiftRegStage, upto(0,num_stages-1));

    method Action _write(td d);
      stages[0] <= d;
      for (Integer i=1; i<num_stages; i=i+1)
        stages[i] <= stages[i-1];
    endmethod
    method _read = stages[num_stages-1];
endmodule

(* synthesize *)
module mkShiftReg_Bit8_2 (ShiftReg#(Bit#(8)));
  (* hide *)
  ShiftReg#(Bit#(8)) __i <- mkShiftReg(2);
  return __i;
endmodule

[ChienTeLi]

Thank you for providing the induction method. I believe this can solve most of my problems and is very practical. Additionally, your reminder about using List is also very helpful. With these two approaches, I feel I can handle my design much more efficiently.

Regarding my initial MergeSort example, it was actually more about the bit width of a counter, which varies at different stages.

[ChienTeLi]

Recently, I discovered a more relevant example. When using MIMO(To be more specific, I used mkMIMOV), I need to determine the size. However, in some cases, the size can be roughly calculated as max_in + max_out + (max_in - gcd(max_in, max_out)). When I want to package this into a module that automatically infers the size, I cannot find a good approach to do so.