Bits UInt type review

[sequencer]

These days I did some code review on Elements operators.
The original idea was trying to solve the the Intellij highlight issue.
But I encountered some strange designs which need to be recorded and discussed later.

Question 1: What is Bits?

I think Bits corresponds to these data structure in BlueSpec, SMT
However when I take a look at operator at Bits, there are some strange functions.

tail(n: Int) -> UInt
head(n: Int) -> UInt
apply(x: BigInt, y: BigInt) -> UInt
pad(that: Int) -> this.type
##(that: Bits) -> UInt

• Firstly, return type of tail, head, apply(x: BigInt, y: BigInt), ##(that: Bits) are certainly wrong.
  They should returns Bits, rather than a UInt.
• Secondly, what is pad(that: Int) -> this.type?
  this.type is defined here
  I don't know why it returns this.type, it's kind of dependent type thinking?

Question 2: UInt are used too much?

Basically, I think there exists a customary abuse to UInt: using UInt as Bits. I think if a user need a UInt, they are using +, -, *, / and other numerical related operators. But these operator only exists in UInt, while not exists in Bits:

&(that: UInt) -> UInt
|(that: UInt) -> UInt
^(that: UInt) -> UInt
orR -> Bool
andR -> Bool
xorR -> Bool
bitSet(off: UInt, dat: Bool) -> UInt
=/=(that: UInt) -> Bool
===(that: UInt) -> Bool

All of these operator are not related to number, while they should belong to Bits, and even the return type should be Bits:
what's the purpose of (a: UInt | b: UInt) + c: UInt? It's kind of strange to merge the usage between Bit Vector and UInt.

So, as the result, I think we may need to fix this to provide a more safe and concrete types to users.

Solution

1. Change the wrong return type in Bits.
2. Add missing operators to Bits.

[johnsbrew]

Hi @sequencer

I kind of agree with the underlying issue of UInt being often used as default type even where it is not justified.

I would like to point out a few things though.
sealed class UInt extends Bits with Num[UInt] as well as sealed class SInt extends Bits with Num[SInt]

• Bits intends to provide bitwise operations
• Traits Num[UInt] and Num[SInt] (implemented respectively in UInt & SInt) indend to provide the numerical operation which is just fine in theory: you cannot implement arithmetic operations in Bits without taking good care of the sign. The point you make here is that the actual implementation for the difference of behavior is handled by firrtl and not chisel.

Regarding type return types for operation declared in Bits, indeed in theory they should always be Bits.
The point is ... it can be really painful to be forced to cast asUInt the result when some downgraded Bits are returned after an operation on an UInt

For pad, the behavior is dependent on the subtype (sign extension for SInt) so returning a UIntor a Bits in all case would be consistently wrong so returning this.type is really what you want here (meaning respectively SInt or UInt here)
A more usual way of doing that would be to implement pad respectively in UInt and SInt (just like arithmetic operation) but this would be against the idea of Bits always providing bitwise operation and would also mean useless code duplication since, actually, the difference in behavior is provided by firrtl and not by chisel...

So, IMHO, for user-convenience this.type should be the return type of all bitwise operations.

And same goes if you want to merge Num[T] implementation into Bits: UInt + UInt shall return UInt and not Bits while SInt + SInt -> SInt (you cannot afford to lose sign information here!!!)
Note that it would require a matches on this.type for almost all operations to provide the return type to pushOp(DefPrim(sourceInfo, dest, op, this.ref, other.ref)) which might end up even more cumbersome than the current implementation...

[sequencer]

Regarding type return types for operation declared in Bits, indeed in theory they should always be Bits.
The point is ... it can be really painful to be forced to cast asUInt the result when some downgraded Bits are returned after an operation on an UInt
So, IMHO, for user-convenience this.type should be the return type of all bitwise operations.

I did some research on branch
I think return this.type is a good way. However there is another issue that: what's the behavior of | ^ &? they have two operators. Scala cannot decide which type to return at compile time.

[johnsbrew]

I think return this.type is a good way. However there is another issue that: what's the behavior of | ^ &? they have two operators. Scala cannot decide which type to return at compile time.

As warned:

Note that it would require a matches on this.type for almost all operations to provide the return type to pushOp(DefPrim(sourceInfo, dest, op, this.ref, other.ref)) which might end up even more cumbersome than the current implementation...

it means you have to do such kind of matches then cast:

def do_^ (that: Bits)(implicit sourceInfo: SourceInfo, compileOptions: CompileOptions): this.type = {
    lazy val res = binop(sourceInfo, cloneTypeWidth(this.width max that.width), BitXorOp, that)
    (this, that) match {
        case (UInt, UInt) => res // note that it is cloneTypeWidth which provides the asInstanceOf[this.type] cast
        case (SInt, SInt) => res
        case _ => throw new Exception("Not handled in current implem => shall we consider SInt ^ UInt -> SInt  while UInt ^ SInt -> UInt ...? Sounds not really pertinent") 
    }
}

Let's now list pros & cons of the proposal for readers (@jackkoenig ?)

Cons

• ugly implementation
• cannot be extended in the usual OOP way
  BUT Bits is sealed & non-public-facing so not intended for extension

Pros

• UX: in user design/generators it would be possible to assume that Bits do provide all bitwise operations and hence write more generic functions such as:

def compute[T <: Bits](a: T, b: T, c: T): T = (a ^ b) | c

Less ugly implementation options:

• add a type parameter to Bits, just like Num[T] (will be quite problematic for compatibility I think)
• add an abstract type member to Bits, to be set respectively to UInt& SInt in class definition

in both cases it would give access to some T, and allow to avoid the match / this.type

sealed abstract class Bits(private[chisel3] val width: Width) extends Element with ToBoolable {
// ...
  type T <: Bits
// ...
  def do_^ (that: T)(implicit sourceInfo: SourceInfo, compileOptions: CompileOptions): T = {
    binop(sourceInfo, cloneTypeWidth(this.width max that.width), BitXorOp, that)
  }
}

sealed class UInt /* ... */ {
  // ...
  type T = UInt
  // ...
}

with this last implementation, we keep the exact same behavior as now: only UInt [&^|] UInt -> UInt and SInt [&^|] SInt -> SInt will compile while above-mentioned this.type version will error at runtime

[Adam-Vandervorst]

An additional motivation may be to provide raw unchecked operations for loading constants.
Say you want to load a bitvector: UInt does not allow negative BigInts, and SInt does not allow for literal conversion to UInt (which is needed for the sign-less operations).
I believe that this, too, is a side-effect of the conflation of Bits and UInt.

[sequencer]

I do want to have a Chisel Type system specification in the following version of Chisel, including operator, lowering specification, data structure(including Scala Type and chisel dynamic type). I believe this can remove some warts from the old days of Chisel.