Syntax of format field access, encode and predicate functions

[AndreasKrall]

We are not happy with the current syntax of the format field access (decode), encode and predicate functions. Eventually there is also the need for additionally assembly encode and predicate functions:

In the OpenVADL AArch64 specification there are currently only the access functions defined (and we are all happy with the syntax for the access functions:

  format BitFieldMoveFormat: Instr =  // bit field move format
    { sf         : Bits1              // size field (enum SF), if (sf = 0) 32 bit operation else 64 bit
    , op         : Bits8              // opcode
    , N          : Bits1              // must be equal to sf, otherwise undefined
    , immr       : Bits6              // rotate right count (bit field low position)
    , imms       : Bits6              // bit field length -1 or high position
    , rn         : Index              // source register
    , rd         : Index              // destination register
    , leftWSize  = BitfieldLeftWSize  (imms(4..0))
    , leftXSize  = BitfieldLeftXSize  (imms)
    , rightWSize = BitfieldRightWSize (imms(4..0), immr(4..0))
    , rightXSize = BitfieldRightXSize (imms, immr)
    // current syntax
    : encode
      { imms => ToImmsWSize (leftWSize)
      , imms => ToImmsXSize (leftXSize)
      , immr => ToImmrWSize (leftWSize, rightWSize)
      , immr => ToImmrXSize (leftXSize, rightXSize)
      }
    : predicate
      { leftWSize  => true // as it is of type Bits<5>, must be changed if leftWSize is UInt32>
      , leftXSize  => true // as it is of type Bits<6>, must be changed if leftXSize is UInt64>
      , rightWSize => true // as it is of type Bits<5>, must be changed if rightWSize is UInt32>
      , rightXSize => true // as it is of type Bits<6>, must be changed if rightXSize is UInt64>
      }
    }

I personally do not like the encode and predicate section, I would prefer just the (different) operators as currently used, e.g.:

    , leftXSize  =  BitfieldLeftXSize  (imms)
    , rightXSize =  BitfieldRightXSize (imms, immr)
    , imms       <- ToImmsXSize (leftXSize)
    , immr       <- ToImmrXSize (leftXSize, rightXSize)
    , leftXSize  :- true // as it is of type Bits<6>, must be changed if leftXSize is UInt64>
    , rightXSize :- true // as it is of type Bits<6>, must be changed if rightXSize is UInt64>

Currently we can define the encoding of imms and immr separately, in the future it could be that more powerful solutions are required. We have the above presented case where we want to map two format fields to two immediate values and in the inverse case mapping 2 immediate values to 2 format fields.

decode: (imms, immr) -> (left, right)
encode: (left, right) -> (imms, immr)
predicate (left)
predicate (right)

The encoding and predicate is always connected to the decode, should we specify it like:

, (imms, immr) <- ToImmsImmr(left, right)

The implementation could be done using bit vector concatenation on the right side and bit vector splitting on the left side.

Another weird example is the imm13 example where with 2 different decode functions in 2 different instructions either a 32 bit or a 64 bit value is needed, but for macro simplification it would be easier if the name of the value is the same. It is also the case here in some way as left / right should have a predicate either on the range 0..31 or 0..63.

It is not always clear, if the type of the predicate arguments is the same as the type of the access function result.

In the discussion there have been proposals like:

format BitFieldMoveFormat: Instr =      // bit field move format
  { left      = ToLeft  (imms)          // <== reusable format field computation function
  , right     = ToRight (imms, immr)    // <== reusable format field computation function
  , To(immr)  = ToImmr  (left, right)   // <== reusable format field encoding function
  , To(imms)  = ToImms  (left)          // <== reusable format field encoding function
  , Is(left)  = IsLeft  (val: SInt<32>) // predicate for left
  , Is(right) = IsRight (val: SInt<32>) // predicate for right
}

A further already discussed extension is format inheritance where I currently see no need:

  format BitFieldMoveFormat: Instr =  // bit field move format
    { sf         : Bits1              // size field (enum SF), if (sf = 0) 32 bit operation else 64 bit
    , op         : Bits8              // opcode
    , N          : Bits1              // must be equal to sf, otherwise undefined
    , immr       : Bits6              // rotate right count (bit field low position)
    , imms       : Bits6              // bit field length -1 or high position
    , rn         : Index              // source register
    , rd         : Index              // destination register
    , leftWSize  = BitfieldLeftWSize  (imms(4..0))
    , leftXSize  = BitfieldLeftXSize  (imms)
    , rightWSize = BitfieldRightWSize (imms(4..0), immr(4..0))
    , rightXSize = BitfieldRightXSize (imms, immr)
    }
  format BitFieldMoveFormatExtension: BitFieldMoveFormat=  // bit field move format extension
    : encode
      { imms => ToImmsWSize (leftWSize)
      , imms => ToImmsXSize (leftXSize)
      , immr => ToImmrWSize (leftWSize, rightWSize)
      , immr => ToImmrXSize (leftXSize, rightXSize)
      }
    : predicate
      { leftWSize  => true // as it is of type Bits<5>, must be changed if leftWSize is UInt32>
      , leftXSize  => true // as it is of type Bits<6>, must be changed if leftXSize is UInt64>
      , rightWSize => true // as it is of type Bits<5>, must be changed if rightWSize is UInt32>
      , rightXSize => true // as it is of type Bits<6>, must be changed if rightXSize is UInt64>
      }
    }

[kper]

I think the new syntax is fine.

    , leftXSize  =  BitfieldLeftXSize  (imms)
    , rightXSize =  BitfieldRightXSize (imms, immr)
    , imms       <- ToImmsXSize (leftXSize)
    , immr       <- ToImmrXSize (leftXSize, rightXSize)
    , leftXSize  :- true // as it is of type Bits<6>, must be changed if leftXSize is UInt64>
    , rightXSize :- true // as it is of type Bits<6>, must be changed if rightXSize is UInt64>

I am not a fan of the alternative since I work regularly with formats and operands and don't understand it on first sight.

format BitFieldMoveFormat: Instr =      // bit field move format
  { left      = ToLeft  (imms)          // <== reusable format field computation function
  , right     = ToRight (imms, immr)    // <== reusable format field computation function
  , To(immr)  = ToImmr  (left, right)   // <== reusable format field encoding function
  , To(imms)  = ToImms  (left)          // <== reusable format field encoding function
  , Is(left)  = IsLeft  (val: SInt<32>) // predicate for left
  , Is(right) = IsRight (val: SInt<32>) // predicate for right
}

I see also no point in allowing inheritance.

[AndreasKrall]

I think the new syntax is fine.

    , leftXSize  =  BitfieldLeftXSize  (imms)
    , rightXSize =  BitfieldRightXSize (imms, immr)
    , imms       <- ToImmsXSize (leftXSize)
    , immr       <- ToImmrXSize (leftXSize, rightXSize)
    , leftXSize  :- true // as it is of type Bits<6>, must be changed if leftXSize is UInt64>
    , rightXSize :- true // as it is of type Bits<6>, must be changed if rightXSize is UInt64>

Here an example with the new syntax (with the assignment operator as suggested by Johannes and the if symbol :- from the programming lange Prolog):

format BitFieldMoveFormat: Instr = // bit field move format
  { sf         :  Bits1            // size field (enum SF), if (sf = 0) 32 bit operation else 64 bit
  , op         :  Bits8            // opcode
  , N          :  Bits1            // must be equal to sf, otherwise undefined
  , immr       :  Bits6            // rotate right count (bit field low position)
  , imms       :  Bits6            // bit field length -1 or high position
  , rn         :  Index            // source register
  , rd         :  Index            // destination register
  , leftWSize  =  -1 as Bits5 - imms(4..0)            // leftWSize is Bits5
  , leftXSize  =  -1 as Bits6 - imms                  // leftXSize is Bits6
  , rightWSize =  immr(4..0) - imms(4..0) - 1         // rightWSize is Bits5
  , rightXSize =  immr - imms - 1                     // rightXSize is Bits6
  , imms       := (-1 as Bits5 - leftWSize) as Bits6
  , imms       :=  -1 as Bits6 - leftXSize
  , immr       := (rightWSize - leftWSize) as Bits6
  , immr       :=  rightXSize - leftXSize
  , leftWSize  :- true             // true because any 5 bit value for leftWSize is valid
  , leftXSize  :- true             // true because any 6 bit value for leftXSize is valid
  , rightWSize :- true             // true because any 5 bit value for rightWSize is valid
  , rightXSize :- true             // true because any 6 bit value for rightXSize is valid
  }

We also should talk about the semantics. Types are as usual derived automatically or specified using as. So the type checker knows that leftWSize is of type Bits5. Therefore, the predicate functions could be omitted because all values of Bits5 are valid. It would be different, if leftWSize would be declared as BitsX:

format BitFieldMoveFormat: Instr = // bit field move format
  { sf         :  Bits1            // size field (enum SF), if (sf = 0) 32 bit operation else 64 bit
  , op         :  Bits8            // opcode
  , N          :  Bits1            // must be equal to sf, otherwise undefined
  , immr       :  Bits6            // rotate right count (bit field low position)
  , imms       :  Bits6            // bit field length -1 or high position
  , rn         :  Index            // source register
  , rd         :  Index            // destination register
  , leftWSize  =  (-1 as Bits5 - imms(4..0)) as BitsX
  , leftXSize  =  (-1 as Bits6 - imms) as BitsX
  , rightWSize =  (immr(4..0) - imms(4..0) - 1) as BitsX
  , rightXSize =  (immr - imms - 1) as BitsX
  , imms       :=  -1 as Bits5 - leftWSize as Bits6
  , imms       :=  -1 as Bits6 - leftXSize as Bits6
  , immr       := (rightWSize - leftWSize) as Bits6
  , immr       := (rightXSize - leftXSize) as Bits6
  , leftWSize  :- leftWSize  as Bits5 as BitsX = leftWSize
  , leftXSize  :- leftXSize  <= 63
  , rightWSize :- rightWSize <= 31
  , rightXSize :- rightXSize as Bits6 as BitsX = rightXSize
  }

Of course the type checker has to check a lot of additional things, e.g. that there is only one encode function used in an instruction (as any number for the same field is allowed). It has to be checked, that there are encode functions when they cannot be derived automatically.

[AndreasKrall]

format BitFieldMoveFormat: Instr = // bit field move format
  { sf         :  Bits1            // size field (enum SF), if (sf = 0) 32 bit operation else 64 bit
  , op         :  Bits8            // opcode
  , N          :  Bits1            // must be equal to sf, otherwise undefined
  , immr       :  Bits6            // rotate right count (bit field low position)
  , imms       :  Bits6            // bit field length -1 or high position
  , rn         :  Index            // source register
  , rd         :  Index            // destination register
  , leftWSize  =  (-1 as Bits5 - imms(4..0)) as BitsX
  , leftXSize  =  (-1 as Bits6 - imms) as BitsX
  , rightWSize =  (immr(4..0) - imms(4..0) - 1) as BitsX
  , rightXSize =  (immr - imms - 1) as BitsX
  , imms       :=  -1 as Bits5 - leftWSize as Bits6
  , imms       :=  -1 as Bits6 - leftXSize as Bits6
  , immr       := (rightWSize - leftWSize) as Bits6
  , immr       := (rightXSize - leftXSize) as Bits6
  , leftWSize  :- leftWSize  as Bits5 as BitsX = leftWSize
  , leftXSize  :- leftXSize  <= 63
  , rightWSize :- rightWSize <= 31
  , rightXSize :- rightXSize as Bits6 as BitsX = rightXSize
  }

A nice syntax extension could be a concat on the left side of the assignment symbol for the encode functions, e.g.:

immX             =  imm13Decode(N, immr, imms)   // returns the 64 bit immediate value as BitsX
(N, immer, imms) := nImmrImmsEncode(immX)

Another semantic question, is it allowed to use any field and access function name in any expression as long as there is no cyclic reference?

[AndreasKrall]

I see also no point in allowing inheritance.

The problem arises if you extend an ISA and you want to add access or encode functions and predicates. Without inheritance you have to do this in the original format definition or copy the format definition with a new name.

[AndreasKrall]

format BitFieldMoveFormat: Instr = // bit field move format
  { sf         :  Bits1            // size field (enum SF), if (sf = 0) 32 bit operation else 64 bit
  , op         :  Bits8            // opcode
  , N          :  Bits1            // must be equal to sf, otherwise undefined
  , immr       :  Bits6            // rotate right count (bit field low position)
  , imms       :  Bits6            // bit field length -1 or high position
  , rn         :  Index            // source register
  , rd         :  Index            // destination register
  , leftWSize  =  (-1 as Bits5 - imms(4..0)) as BitsX
  , leftXSize  =  (-1 as Bits6 - imms) as BitsX
  , rightWSize =  (immr(4..0) - imms(4..0) - 1) as BitsX
  , rightXSize =  (immr - imms - 1) as BitsX
  , imms       :=  -1 as Bits5 - leftWSize as Bits6
  , imms       :=  -1 as Bits6 - leftXSize as Bits6
  , immr       := (rightWSize - leftWSize) as Bits6
  , immr       := (rightXSize - leftXSize) as Bits6
  , leftWSize  :- leftWSize  as Bits5 as BitsX = leftWSize
  , leftXSize  :- leftXSize  <= 63
  , rightWSize :- rightWSize <= 31
  , rightXSize :- rightXSize as Bits6 as BitsX = rightXSize
  }

Another semantic question, is it allowed to use any field and access function name in any expression as long as there is no cyclic reference?

I would say no. If the reuse of an access function would make sense, it is possible to define a function and pass the field as argument.
On the lhs of = only distinct new access function names are allowed.
On the rhs of = only existing field names are allowed, no other access function names.
On the lhs of := only existing field names are allowed. They can occur multiple times, but in a concrete instruction the field names must be distinct.
On the rhs of := only existing access function names are allowed.
On both sides of :- only existing access function names are allowed.
On the rhs they can occur multiple times.
On the lhs they can occur multiple times, but in a concrete instruction the access function names must be distinct.

[kper]

I would prefer the := syntax for encoding over <-.

[Jozott00]

@AndreasKrall for predicates, is it allowed to have other access functions on the rhs than the access function itself?

E.g.

rightWSize :- leftWSize = rightWSize

[AndreasKrall]

I assume yes.

[Jozott00]

@AndreasKrall @kper is the following check valid:
If e1 and e2 have the same target field, e1.accessFunctions mustn’t be a subset of e2.accessFunctions.

E.g.

  format Format: Bits<32> =
  { one   [31..15]
  , two   [14..10]
  , ...
  , accFunc = one as SInt
  , accFuncTwo = two as SInt
  , one := accFunc
  , one := accFunc + accFuncTwo as SInt<17>
  }

Where the first encoding has the same target as the second one and operates on a subset of field accesses.

This would raise the following error

error: Conflicting field access encodings
     ╭──[file:///Users/jozott/development/uni/dipl/iss-dev/code/open-vadl/out/test.vadl:79:5]
     │
  78 │   , one := accFunc
     │     -------------- This field access encoding uses a subset of field accesses.
     │
  79 │   , one := accFunc + accFuncTwo as SInt<17>
     │     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Field `one` is already target field for a subset of field accesses.
     │ 

[kper]

It depends on the instruction which uses the Format.
Does it only use accFunc? Then it is fine.
Does it use accFunc and accFuncTwo? Then it is not clear which to use

[Jozott00]

Yeah, so it can be considered illegal, if the only way to use the second encoding is illegal, right?

[kper]

Yes, so an error would be expected

[kper]

I am currently in the processing of implementing this and I want to document a few problems a meeting.

The concept of field access functions fits nicely into LLVM when we have 1:1 relationship between field and field access function. However, it seems that it doesn't fit so properly anymore when a field gets encoded by multiple field access functions.

Consider the following example

leftWSize  =  (-1 as Bits5 - imms(4..0)) as BitsX
rightWSize =  (immr(4..0) - imms(4..0) - 1) as BitsX
immr       := (rightWSize - leftWSize) as Bits6

We have two field access functions leftWSize and rightWSize. We want to encode immr based on both.
Imagine we have an instruction with 3 operands. The output is a register and the two inputs are immediates with leftWSize and rightWSize.
Let's image LLVM's instruction selector selected this instruction and wants to encode it. It would need two encoding functions because each operand has its own.