Authors: Pedro Vicente (@pedroMVicente), Guilherme Lopes (@guilhermeglopess)
This post is continuation of the discussion for the bitextract and bitinsert instructions mentioned in [RFC] Add a New Byte Type to LLVM IR.
Summary
LLVM IR currently has no representation for extracting or inserting contiguous ranges of bits (efficiently) within the new Byte Type. For integer types, these operations are compiled to multiple instructions (shifts, masks, etc). However, these are not allowed for Byte Types. We propose two new instructions, bitextract and bitinsert, to address this gap in Byte types.
Motivation
-
Bitfield access: C and C++ bitfields require extracting and inserting contiguous ranges of bits from memory. Right now, bitwise integer operations are used to access bitfields, but it is desired to change these to bytes so the value of uninitialized memory can be switched to poison instead of undef. bitextract allows to extract a bitfield range directly from a byte value, and bitinsert allows modifying part of a byte. Without these instructions, bitfield access on Byte Type values is not possible to represent (technically, these could be represented by bitcasting to a vector and using shufflevector, but this is highly convoluted and inappropriate for a canonical representation).
-
Load widening: GVN and other optimizers merge together loads from multiple nearby locations, which can spread poison incorrectly. The original RFC fixed this by issuing a byte load and then trunc+lshr+cast to extract the individual values. However, these operations expect integer types, not byte.
Proposal
Bitextract
Syntax:
<result> = bitextract <ty>, <tx> <source>, i32 <offset>
Overview:
This instruction extracts a value from a byte.
Arguments:
The ‘bitextract’ instruction takes any first-class type ty (the return type), a Byte value source, and an offset.
Semantics:
The ‘bitextract’ instruction returns a value of the specified type. The returned value is first extracted from the source, starting at the bit specified by the offset, and then bitcasted to the return type. If the range offset+ty.bitwidth exceeds the source width, it returns poison.
Example:
%result = bitextract i8, b32 %src, i32 24 ; Extract the last 8 bits from %src and return an 8-bit integer
Bitinsert
Syntax:
<result> = bitinsert <tx> <base>, <ty> <val>, i32 <offset>
Overview:
This instruction inserts a value into a specific position within a byte.
Arguments:
The first argument (base) of bitinsert must be of a byte type. The second operand (val) must be an arbitrary type.
Semantics:
The returned value is of the same byte type as the first argument. It returns the first argument where the bits in the range [offset, offset + ty.bitlength - 1] have been replaced with val. If the range (offset + ty.bitwidth) is greater than the bitwidth of the first argument, it returns poison.
Example:
%result = bitinsert b32 %x, i8 %y, i32 3 ; Inserts the %y bits into %x with an offset of 3
Why not extend these for integers?
The possibility of extending these instructions to integer types has been considered, but it would represent a significant change to LLVM’s canonical form. For instance, the purpose of the trunc instruction would become ambiguous if bitextract was valid for all integers.
Why Instructions over Intrinsics?
Byte type is a first-class citizen, therefore basic manipulation operations should be in the IR. All types (ints, floats, arrays, vectors, etc) have IR instructions to manipulate them.
Open questions
- Should the offset be allowed to be a runtime register value, or would limiting it to an immediate be enough to cover all practical use cases?