search

lkolbly / ripstop

Apache License 2.0
0 stars 0 forks source link

Reset Behaviour #15

Closed lkolbly closed 2 years ago

lkolbly commented 2 years ago

So if you have this code:

module blinky() -> (bit led) {
    led[0] = 0;
    led[t] = ~led[t-1];
}

I think we should interpret the led[0] as being the reset value. In other words, if rst is high, then led should be low. In other words, this module should have this behaviour: image Wavedrom:

{signal: [
  {name: 'clk', wave: 'p.........'},
  {name: 'rst', wave: '0..1..0...'},
  {name: 'led', wave: 'x...0..101'},
], config: { hscale: 2 }, head:{
   tock:-6,
   every:1
 }}

The numbering is what I think is where the "t" values should be placed (note how the numbers are on the falling edge, rather than the rising edge when values change).

Asynchronous reset

Consider this code:

module foo() -> (bit led) {
    bit a;
    led[0] = 0;
    led[t] = a[t];
    a[t] = ~a[t-1];
}

Here, led is driven by combinatorial logic. This could be used to express this functionality:

reg a_q;
wire a_d;
assign led = rst ? 0 : a_q;
assign a_d = ~a_q;
always @(posedge clk) begin
    a_q <= a_d;
end

but then we have an asynchronous reset. So, I think to start with we can enforce the semantic that if a variable is driven by combinatorial logic (i.e. x[t] depends on something[t]), then you cannot specify the reset value for that parameter.

Chained reset values

Consider this code:

module bar() -> (bit led) {
    led[0] = 0;
    led[t] = ~led[t-3];
}

In a strictly mathematical sense, led[1] = ~led[-2], and led[-2] hasn't been defined. However, we can interpret led[0] as setting the value led[x] for all x >= 0. But this opens the possibility for specifying a whole chain of reset values, e.g.:

module bar() -> (bit led) {
    led[-2] = 0;
    led[-1] = 1;
    led[0] = 0;
    led[t] = ~led[t-3];
}

but again, I think we should start simple, and only allow setting led[0].

lkolbly commented 2 years ago

Thinking about it some more, this might actually not be an issue with eager/lazy evaluation at all (like I implied in #2). This might be more of an issue with how synchronous resets are implemented.

In particular, look at this generated code:

module blink (
    input rst,
    input clk,
    output led
);
    reg led_neg1;
    wire led_0;
    assign led = led_0;
    assign led_0 = ~(led_neg1);
    always @(posedge clk) begin
        led_neg1 <= rst ? (1'd0) : (led_0);
    end
endmodule

Notice that we're assigning the reset value to state_neg1. Which makes sense, because that's the only register we have.

So this code is equivalent to if we had specified led[-1] = 0.

This effectively means that we need to pull things forward by a step. Ultimately, we want code equivalent to the following:

module blink(
   input rst,
   input clk,
   output led
);
   reg led_q, led_d;
   assign led = led_q;

   always @(*) begin
      led_d = ~led_q;
   end

   always @(posedge clk) begin
      led_q <= rst ? 0 : led_d;
   end
endmodule

which could be rewritten:

module blink(
   input rst,
   input clk,
   output led
);
   reg led_0;
   wire led_next;
   assign led_next = ~led_0;
   assign led = led_0;

   always @(posedge clk) begin
      led_0 <= rst ? 0 : led_next;
   end
endmodule

In other words, a register generated for x[t] should store the current value, not the previous value. In the reset case, there is no previous value. There is only the current value.

How does this interact with register chains? For example, consider:

module blink_long() -> (bit led) {
    led[t] = ~led[t-3];
}

I think we want this to generate the following code:

module blink(
   input rst,
   input clk,
   output led
);
   reg led_0, led_neg1, led_neg2;
   wire led_next;
   assign led_next = ~led_neg2;
   assign led = led_0;

   always @(posedge clk) begin
      led_0 <= rst ? 0 : led_next;
      led_neg1 <= led_0;
      led_neg2 <= led_neg1;
   end
endmodule

How does this interact with combinatorial logic? Consider:

module add(bit a, bit b) -> (bit c) {
    c[t] = a[t] + b[t-1];
}

I think this should generate:

module add(
   input rst,
   input clk,
   input a,
   input b,
   output c
);
   reg c_0, b_neg1;
   wire a_0, c_next;
   assign c_next = a_0 + b_neg1;
   assign c = c_0;
   assign a_0 = a;

   always @(posedge clk) begin
      c_0 <= rst ? 0 : c_next;
      b_neg1 <= rst ? 0 : b;
   end
endmodule
lkolbly commented 2 years ago

Here's another example, to narrow down on the solution a little better:

module blink(bit a) -> (bit led) {
    led[0] = 0;
    led[t] = ~led[t-1] + a[t];
}

If a is held at zero, this should should be equivalent to:

module blink() -> (bit led) {
    led[0] = 0;
    led[t] = ~led[t-1];
}

Which means that we need to generate code like:

module blink(
    input clk,
    input rst,
    input a,
    output led
);
    reg led_0;
    wire led_next;
    assign led = led_next + a;
    assign led_next = ~led_0;

    always @(posedge clk) begin
        led_q <= rst ? 0 : led_d;
    end
endmodule

Which I think means that the compiler must to be able to split a single right hand side into different components. There is no way to handle the RHS opaquely as a complete expression and correctly compile in every case.

Notably, all we need to be able to do is divide the expression into "can be done using only register state," and "must be done combinatorially." We don't need to evaluate each subexpression as early as possible (doing so falls into the realm of optimization, covered in #14).

Or do we? Let's think about that. We can invent a module like this:

module blink(bit a, bit b) -> (bit led) {
    led[t] = (a[t] + ~led[t-1]) + b[t];
}

Here, we must evaluate the subexpression (a[t] + ~led[t-1]) combinatorially (because it contains a [t]). But, we still must evaluate ~led[t-1] as early as possible, to avoid the reset issue that spawned this whole discussion. Imagine if both a and b were fixed at zero, this code must still behave like the simple no-parameter blink above.

lkolbly commented 2 years ago

Yet another example:

module blink(bit a) -> (bit led) {
    led[0] = 0;
    led[t] = ~(led[t-1] + a[t]);
}

The earliest we can evaluate the bitwise inverse is combinatorially.

To take another look at the last example above:

module blink(bit a, bit b) -> (bit led) {
    led[t] = (a[t] + ~led[t-1]) + b[t];
}

do we need to evaluate the ~led[t-1] as early as possible? Let's say we don't, we could generate code like this:

module blink(
    input clk,
    input rst,
    input a,
    input b,
    output led
);
    reg led_0;
    wire led_next;
    assign led = led_next;
    assign led_next = a + ~led_0 + b;

    always @(posedge clk) begin
        led_0 <= rst ? 0 : led_next;
    end
endmodule

which does not behave as we want, because under reset led will be high (if a and b are low).

Then the question is: What even is the right way to codegen the led[0] = 0; led[t] = ~(led[t-1] + a[t]) example? Is that expressible in Verilog? I can't think of a way! (well, without adding additional logic)

So maybe we're thinking about reset wrong.

Ban reset for combinatorial circuits

In other words, this:

module blink(bit a) -> (bit led) {
    led[0] = 0;
    led[t] = ~(led[t-1] + a[t]);
}

is a compile error.

This isn't actually too crazy. After all, we were already considering that this:

module blink(bit a) -> (bit led) {
    led[0] = 0;
    led[t] = a[t];
}

should be a compile error.

But then the question is - can the user still specify the behaviour they want? There's two behaviours that need to be expressable. The led-high-on-reset case:

module blink(bit a) -> (bit led) {
    bit led_state;
    led_state[0] = 0;
    led_state[t] = led[t-1];
    led[t] = ~(led_state[t] + a[t]);
}

And the led-low-on-reset case:

module blink(bit a) -> (bit led) {
    bit led_state;
    led_state[0] = 1;
    led_state[t] = led[t-1];
    led[t] = ~(led_state[t] + a[t]);
}

But, this is painful for the user. The whole point of the language is that state is sort of implicit in time. If the user just does the intuitive thing:

module blink(bit a) -> (bit led) {
    led[t] = ~(led[t-1] + a[t]);
}

then they have to rely on the default reset value of led.

Allow reset values at t=-1 for combinatorial RHSs

Maybe we could give them a branch, and let them set the reset value for t=-1:

led[-1] = 0;
led[t] = ~(led[t-1] + a[t]);

Is it clear enough that led[-1] refers to the value "before reset"? (such that the reset value, led[0], is computed from that) It sorta makes sense to me, but I've been thinking about this really hard for several days.

The question then is, what is the rule for deciding what times of reset are allowed?

In general, the common thread is that if the RHS has a [t] reference, then the reset value should be [-1].

Is that something that's easy to explain to users? Obviously, we can have error messages like this:

Reset value at t=0 is not allowed when variable is assigned combinatorially:
led[0] = 0;
    ^
Assigned here:
led[t] = ~(led[t-1] + a[t]);
                        ^
Use a reset value of t=-1 instead.

One potential gotcha of this design is how implicit reset values work. For example:

module blinky(bit a) -> (bit led) {
    led[t] = ~(led[t-1] + a[t]);
}

Implicitly, a led[-1] = 0 would be added, which would mean that implicitly led[0] = 1 if a[0] = 0.

Maybe the takeaway from this is that we should not have (or, start with) implicit reset values. We can warn if the user doesn't specify a value.

Allow reset values at t=-1, and disallow reset values at t=0

Interestingly, in all of the above cases, led[-1] is semantically valid. So maybe we should just only allow that.

In this model, the language is always allowing led[0] be computed by the led[t] statement. Which makes sense: Because then assignments (led[t] = ...) describe what's happening, and negative absolute assignments (led[-1] = ...) describe the setup.

But the problem is that the user needs to back out their desired led[-1] value from the desired reset value. For example, in led[t] = ~led[t-1]; the user may just want led[0] = 0. They don't want to have to go figure out that implies that led[-1] = 1. If the logic is more complicated, this effect gets worse:

module counter() -> (bits<32> counter) {
    counter[-1] = 0xFFFF_FFFF; // In order to start at 0
    counter[t] = counter[t-1] + 1;
}

Allow reset values for right-hand-side references only

In a case like led[t] = a[t-2], does it really make sense for the reset value to be led? Really, we want to set the reset value for a[t-2] and a[t-1] (a[t], of course, might be an input or computed elsewhere).

For a case like led[t] = ~(led[t-1] + a[t]), this makes sense. There is a led[t-1] on the right hand side, so the reset value is led[-1] = 0.

But for a case like led[t] = ~led[t-1], even though the right hand side still has a led[t-1], the reset value should be for led[t].

Replace [0] with [rst]

As a slight tangent, maybe this would be clearer:

led[rst] = 0;
led[t] = ~led[t-1];

But then, does rst-1 make sense?

led[rst-1] = 0;
led[t] = ~(led[t-1] + a[t]);

On the one hand, this is nice because it moves in the direction of varying (generic) time stamps. But on the other hand, this is weird because it implies that it happens somehow before reset.

Other options?

???