[RFC] Add a (more) general shape conversion operator

[whitequark]

In response to #292 we've added operators that reinterpret a value of any signedness as a signed or unsigned value of the same width. It would be nice to have an operator that changes the width of a value, too.

Current workaround: for truncation, use v[:new_width]; for extension, use a no-op bitwise operation, like v | C(0, new_width).

• Downside: this code is confusing when it is encountered among a bunch of arithmetic operations.
• Downside: this code is fragile because neither of these operations is guaranteed to return a value with width new_width.

The workaround seems unacceptable to me.

Proposal 1: add two new operators, v.trunc(new_width) for truncation and v.extend(new_width) for zero/sign extension depending on the signedness of v. The new operators would make it an error to truncate to a larger width, or extend to a smaller width than the width of v.

• Upside: the new operators reliably return a value with requested width.
• Upside: the new operators eliminate bugs caused by extension being used instead of truncation or vice versa
• Downside: the new operators accept a width, not a shape, so there is no way to extend a value until it matches the width inferred for range or an enum.
• Downside: two new operators with quite limited use

Proposal 2: like Proposal 1, but the operators accept a new_shape rather than new_width, enforcing the same preconditions. The signedness of the result matches the signedness of the shape.

• Upside: the new operators reliably return a value with requested width.
• Upside: the new operators eliminate bugs caused by extension being used instead of truncation or vice versa
• Upside: the new operators are quite expressive, and as_unsigned/as_signed can be implemented in terms of either.
• Downside: two new flexible operators but "either extend or truncate"--chiefly what happens in x.eq(y)--still isn't expressible and requires an intermediate wire

Proposal 3: add one new operator, v.as(new_shape) for truncation, zero/sign extension, and type conversion. The new operator would extend v if new_shape.width > len(v), truncate v if new_shape.width < len(v), and return a value with shape new_shape.

• Upside: the new operator reliably returns a value with requested width.
• Upside: one operator that can express every implicit shape conversion done by nMigen, including as_unsigned/as_signed.
• Downside: the new operator can hide bugs caused by extension being used instead of truncation or vice versa

Proposal 4: Proposals 2 and 3 at the same time

Thoughts?

[Ravenslofty]

TL;DR: Proposal 2, but this might be Stroustrup's rule in effect.

My issue with Prop 1 is that I generally don't declare values as signed or not, but instead consider them signed at point of use, because I don't generally need signed math much, so it's an exceptional case. So when I'm wandering through a codebase, something like

m.d.sync += imm.eq(i_imm.extend(32))

makes me immediately ask "is this zero or sign-extending?", so I scurry back to its definition (some editors can just point to the definition, some can't) to find

i_imm = Signal(signed(12))

and oh, right, it's sign extending.

m.d.sync += imm.eq(i_imm.extend(signed(32)))

is perhaps more verbose, but it tells me at point of use this is sign-extending.

To me it feels like a fundamental tenet of nMigen that things should not silently truncate, so if you're in the middle of some generic code that operates on a width given by a parameter, I would much prefer having to explicitly check and use the right operator than stare at my code wondering if

m.d.sync += imm.eq(i_imm.as(signed(32)))

is truncating or extending the value. as is simply too powerful for me to trust fully, I think.

[whitequark]

@ZirconiumX

To me it feels like a fundamental tenet of nMigen that things should not silently truncate

This is a good point---right no none of our operators silently truncate, and that is indeed a wonderful property that should be preserved. Of course, the .eq() statement does truncate, but it is easy to argue that this truncation is, at most, a necessary evil. (If we added .trunc(), we could then add an off-by-default lint triggered by silent truncation in .eq()).

I suppose this soundly excludes Proposal 3.

it tells me at point of use this is sign-extending.

This is actually not what I proposed. What I proposed results, for a v : unsigned(16), in essentially this:

v.extend(signed(32)) ≡ Cat(v, C(0, 16)).as_signed()

But what you describe as a good feature here is essentially:

v.extend(signed(32)) ≡ Cat(v.as_signed(), C(v[-1], 16)).as_signed()

Now, I think the semantics you like is definitely more useful. But there are two problems with it.

First, it's inherently ambiguous with the semantics I suggested. However, if it turns out that everyone intuitively understands v.extend(signed(32)) the same way you do, this isn't actually a problem.

Second, and more importantly, it makes nMigen's value promotion rules twice as complicated. Right now, if you have x as an operand of any operation, and that operation needs to make x wider, whether that does sign- or zero-extension depends only on the nature of x itself, i.e. whether it's signed or not. But with this semantics of extend, it depends only on the argument of extend, eating significantly into the complexity budget.

We could rescue it by saying that v.extend(shape) produces an error if the signedness of shape doesn't match the signedness of v. Compared to taking a width, this eliminates the confusion at the point of use: v.extend(32) is just v.extend(unsigned(32)). But it feels like an unsatisfying solution.

[Ravenslofty]

Right now, if you have x as an operand of any operation, and that operation needs to make x wider, whether that does sign- or zero-extension depends only on the nature of x itself, i.e. whether it's signed or not. But with this semantics of extend, it depends only on the argument of extend, eating significantly into the complexity budget.

Perhaps this points to shape being the wrong thing to disambiguate sign and zero extension. Does v.extend(signed(32)) extend and treat as signed (your semantics), or does it treat as signed and then extend (my semantics)? If after reading your proposed semantics I mixed it up, what will that mean for a beginner?

I fully agree that the operators should take shape because of the flexibility here, but perhaps it should look something like v.sign_extend(signed(32))/v.zero_extend(signed(32))?

[whitequark]

If after reading your proposed semantics I mixed it up, what will that mean for a beginner?

Indeed! I somehow forgot to document that (which worked out for the better), but this was actually my #1 concern about that proposal.

I suppose this soundly excludes Proposal 2.

I fully agree that the operators should take shape because of the flexibility here, but perhaps it should look something like v.sign_extend(signed(32))/v.zero_extend(signed(32))?

If v.sign_extend takes a shape, then v.sign_extend(32) must mean v.sign_extend(unsigned(32)). But getting an unsigned value as a result seems extremely counterintuitive and probably something you rarely if ever want when using that function.

[whitequark]

At this point the solutions I see are:

• go with Proposal 1 with a lint (probably off by default?) that warns if you are .extend()ing anything other than the result of .as_signed()/.as_unsigned(), to handle your use case
• go with something else entirely
• do nothing

It's hard to argue in favor of Proposal 1 because it ditches shapes. You could try to say that you treat .extend and .trunc as bit sequence functions (which generally take bit indexes, not shapes), but that doesn't work well because .extend and .trunc are solidly in the domain of arithmetic operations (they take the signedness from the operand), not in the domain of bit sequence operations (which are all unsigned).

[awygle]

I agree with @ZirconiumX in that I think of sign/zero extension as an operation not related to the "type" of the operand(s).

My main concern with the as(Shape) proposal is that I don't know how to get a shape except from an enum or similar, so I wouldn't consider it sufficient by itself (I assume there is a way that I just don't know but that weakly argues for it not being obvious).

I would like a variant of proposal 2, which is .trunc, .sign_extend and .zero_extend or .extend. The type of extension would depend only on which function is called.

ETA: I suppose this brings these functions back into the realm of "bit sequence operations".

[whitequark]

My main concern with the as(Shape) proposal is that I don't know how to get a shape except from an enum or similar

Anything you put into a Signal constructor is castable to Shape. So 1, unsigned(1), signed(8) are all shapes.

[whitequark]

I would like a variant of proposal 2, which is .trunc, .sign_extend and .zero_extend or .extend. The type of extension would depend only on which function is called.

The problem is that we have two things here: the type of extension (i.e. what bit is used for padding in this operation) and the shape of the result (i.e. what bit is used for padding in following operations), and it's not clear what sort of API makes it clear what's going on with both.

[Ravenslofty]

The problem is that we have two things here: the type of extension (i.e. what bit is used for padding in this operation) and the shape of the result (i.e. what bit is used for padding in following operations), and it's not clear what sort of API makes it clear what's going on with both.

This is going to be ugly, but I'll throw it out there: what if we don't combine the two? We have .as_{signed,unsigned} to communicate result signedness, and then we can use .sign_extend/.zero_extend to purely extend to a given width. Then we end up with a monstrosity like v.as_signed().sign_extend(32), which looks ugly, but it's difficult to argue about clarity. If possible we can mitigate the gotcha of sign_extend on an unsigned value returning unsigned by linting on it not having an explicit signedness.

[whitequark]

This is going to be ugly, but I'll throw it out there: what if we don't combine the two?

It's kind of ugly, but not that much. I've proposed something similar myself in #381 (comment).

Then we end up with a monstrosity like v.sign_extend(32).as_signed()

Is there a typo? Are you sure this is the right order?

[Ravenslofty]

Is there a typo? Are you sure this is the right order?

Ah, yes, it should be the other way round.

[whitequark]

Per IRC discussion it seems that the most reasonable way forward with this is to have:

• v.zero_extend(new_width) that works only on unsigned values, requires new_width >= len(v), and returns unsigned values,
• v.sign_extend(new_width) that works only on signed values, requires new_width >= len(v), and returns signed values,
• v.truncate(new_width) that works on values of either signedness, requires new_width <= len(v), returns a value of the same signedness as the input, and checks (in simulation and formal) that the truncated bits were all identical to 0 (for unsigned values) or the new MSB (for signed values).

[akukulanski]

Is it too ugly to make the new width a parameter of as_signed() and as_unsigned(), being the default value of that parameter the width (or shape?) of the signal? I think that the verbosity of the proposed alternatives (or the addition of new parameters) is because the intention to split two things that "have to go together" for the behaviour to be clear at a glance. That way you'll never use an extension without explicitly writing the signedness, which seems like a good practice when you handle signed values.

That way you just do:

x = Signal(32)
x.as_signed() # keeps the same functionality that the method already has
x.as_signed(4) # truncates
x.as_signed(64) # extends

Downside: the new operator can hide bugs caused by extension being used instead of truncation or vice versa

This will remain that way, but I'm not sure if that's bad. If you change the width to something that is not the correct number you expected (say 3 instead of 32) you'll have a hidden bug anyway. It'd not matter if the new width is higher or lower to the old one.

[Ravenslofty]

Downside: the new operator can hide bugs caused by extension being used instead of truncation or vice versa

This will remain that way, but I'm not sure if that's bad. If you change the width to something that is not the correct number you expected (say 3 instead of 32) you'll have a hidden bug anyway. It'd not matter if the new width is higher or lower to the old one.

I think nMigen generally avoids magic numbers like this, so if this was the accepted syntax it would likely look more like x.as_signed(width=4).

I have two objections to this, which I've already raised in this thread:

To me it feels like a fundamental tenet of nMigen that things should not silently truncate, and yet in generic code it would be quite easy to slip up and cause silent truncation with this. If you mean to extend, you should say so, and if you mean to truncate, you should say so; it helps nMigen catch bugs, and it helps the reader understand code. This was the reasoning that shot down Proposal 3.

But let's be constructive here: if the goal is to distinguish between truncation and extension, we could change the keyword arguments here to something like x.as_signed(extended_width=64) or x.as_signed(truncated_width=4). This is a little verbose, but it's got the bug-protection properties of before.

Okay, back to objecting. What is the semantic order here? Does it convert the value to signed and then extend, or extend and then convert to signed? That matters because if you have an unsigned value as input, the former sign-extends, and the latter zero-extends. What myself and WQ concluded was that it was difficult to specify a "fused" operator that is both concise and clear. This was the reasoning that shot down Proposal 2.

[akukulanski]

I think nMigen generally avoids magic numbers like this, so if this was the accepted syntax it would likely look more like x.as_signed(width=4).

You're right

we could change the keyword arguments here to something like x.as_signed(extended_width=64) or x.as_signed(truncated_width=4). This is a little verbose, but it's got the bug-protection properties of before.

I don't consider a change in a width a "silent" truncation, but I understand that it could lead to more hidden bugs than the other way, so I like this approach.

What is the semantic order here? Does it convert the value to signed and then extend, or extend and then convert to signed?

It should first convert to signed and then extend. The intention with as_signed/as_unsigned here is to be useful as an indicator of how the signal should be extended. The other way around you'd lose the capability of doing an easy sign extension. If you have a weird case where you want to sign extend but then have an unsigned signal you can do it with x.as_signed(extended_width=8).as_unsigned()

What myself and WQ concluded was that it was difficult to specify a "fused" operator that is both concise and clear.

I found this clear with your proposal about using kw args, but of course you can disagree :). I thought this could be a better alternative than adding two new operators with a very limited use, since that also seemed to be a concern here.

[programmerjake]

I would argue that the best course of action is to have the extend/truncate operators preserve the mathematical value during conversion, where if the true mathematical value is out of range, then it wraps modularly. This would mean that extend with sign conversion would always extend using the source's signedness then convert signedness. Both ways are identical for truncation.

The above is the same method used in C/C++, Rust and probably most other programming languages. I'm not aware of a single programming language that converts signedness then extends.

[akukulanski]

Maybe I'm missing something so please correct me if I'm wrong, but if you want an operation that keeps the signedness of the signals you'll already get the expected behavior by just doing the assignment (.eq()) to the signal with different width.

This methods that don't depend on the original signal signedness are useful for the use mode that @awygle and @ZirconiumX exposed, where that signedness is only considered at point of use if the operation requires it. The advantage of not depending on the signal declaration is that you don't always have an easy access to it (for example if you are working with standard interfaces and you don't want to duplicate every interface with a signed and an unsigned version).

I'm not aware of a single programming language that converts signedness then extends.

You may have a point there. Yet, I'm not sure if that's a fair comparison, since a width conversion in hdl should not necessarily match a cast behavior of a programming language where you have fixed data types.

[whitequark]

I would argue that the best course of action is to have the extend/truncate operators preserve the mathematical value during conversion, where if the true mathematical value is out of range, then it wraps modularly.

Just to double check, do you agree that this is the semantics I propose in #381 (comment) ?

[programmerjake]

I would argue that the best course of action is to have the extend/truncate operators preserve the mathematical value during conversion, where if the true mathematical value is out of range, then it wraps modularly.

Just to double check, do you agree that this is the semantics I propose in #381 (comment) ?

What you described should work and I'm fine with it, though I had intended the explanation of preserving the mathematical value to define what happens for something more like <Value>.convert_to(<Shape>) where the exact order of operations performed is not trivially obvious.

[whitequark]

On the previous meeting, we decided that @programmerjake's latest comment about preserving mathematical value added enough insight to the conversation that the RFC would have to be rewritten with that in mind. The new RFC is #464, and I'm closing this one in favor of that.