In the past, we struggled with LLVM for our targets, which do not support byte addressed memory. A topic that appears once in a while. Some patches are on the net.
Here, I want to present our approach to support these architectures without patching LLVM.
Comments are welcome.
When There Are No Bytes
Most common architectures have the same memory model: each byte is
addressable. But there are some special architectures for special
purposes, where addressing each byte is not required, eg on vector
processing architectures. The compiler infrastructure LLVM supports
the first set of architectures: the byte addressed architectures.
Once in a while the question appears to patch LLVM to support an
instance of the second set of architectures. This could be bit
addressed memory or word addressed memory. We call this target
addressed architectures. There is a set of patches for an old
version of LLVM, but these are incomplete and have not been upgraded
for newer versions of LLVM. In the past we applied these patches and
added new ones, but got stuck on LLVM version 3.4.2, while LLVM
version 7.0.0 was released.
In the following we present our approach: we perform target dependent
transformations without patching. This approach was first applied
to LLVM 7.0.0 as a feasibility study for a bit addressed
architecture and then implemented for a word addressed architecture.
Later we upgraded to LLVM 14.0.6 without problems.
The Idea
Our approach is to stay with LLVM’s byte address mode and make all
target address transformations explicitly. When we get in touch
with the architecture or its environment we transform the byte
address into a target address.
We touch the architecture or its environment when
- we load values from memory or store values to memory
- we access target address labels provided by the assembler
- function calling:
- we call system functions or legacy code, that might need a
target addresses - we are called from system functions or legacy code, that passes
target addresses
- we call system functions or legacy code, that might need a
In this approach it does not matter if the target address addresses 1
bit or 64-bits words; we implemented both.
Transforming Memory Access
In the first transformation step, we transform LLVM memory accesses,
which are implemented by ISD::LOAD and ISD::STORE
operations. There are other operations, but for the sake of
simplicity we stay with these two operations. These operations have a
byte addressed pointer which has to be transformed into target
addressed pointer. Therefore, we add 3 target operations:
TargetaddressconvertByteaddressToTargetaddressconvertTargetaddressToByteaddress
The first operation is a simple marker, that a transformation was done
and avoids endless recursion. The other two operations are the
explicit transformations. We keep them explicit to make optimizations
on these operations simpler.
During the legalize pass we replace the memory operations:
if (TargetISD::TargetAddress != Load.getBasePtr().getOpcode()) then
load(ptr) -> load(Targetaddress(convertByteaddressToTargetaddress(ptr)))
and
if (TargetISD::TargetAddress != Store.getBasePtr().getOpcode()) then
store(..,ptr,..) -> store(..,Targetaddress(convertByteaddressToTargetaddress(ptr)),..)
In a pre-ISel pass we remove the operation Targetaddress again:
Targetaddress(ptr) -> ptr
When we view a DAG before the isel pass, then the graph should look
quite familiar and ready for instruction selection.
Transforming Assembler Interaction
In the second transformation step, we transform all target addresses
provided by the assembler into byte addresses as needed by LLVM. In
general, these addresses are given in form of labels that were
generated by the compiler in assembler code, eg GlobalAddress,
FrameIndex, ConstantPool and the like to address data.
GlobalAddress -> Targetaddress(convertByteaddressToTargetaddress(GlobalAddress))
Instruction Selection
For instruction selection we have to implement instructions for the
operations convertByteaddressToTargetaddress and
convertTargetaddressToByteaddress. We keep them abstract throughout
the instruction selection pass as long as possible to have the
possibility to optimize these operations with their semantics and not
their implementation. In the code generator table-gen file we
specify the operations and add two pseudo instructions:
// the operations
def ConvertByteaddressToTargetaddress:
SDNode< "TargetISD::convertByteAddressToTargetAddress", SDTUnaryOp>;
def ConvertTargetaddressToByteaddress:
SDNode< "TargetISD::convertTargetAddressToByteAddress", SDTUnaryOp>;
// the pseudo instructions
let usesCustomInserter = 1 in {
def ConvertTargetaddressToByteaddress_rr:
Pseudo< (outs Regs:$dst), (ins Regs:$src),
"$dst := convertTargetaddressToByteaddress($src)",
[(set Regs:$dst,
(ConvertTargetaddressToByteaddress Regs:$src))]>;
def ConvertByteaddressToTargetaddress_rr:
Pseudo< (outs Regs:$dst), (ins Regs:$src),
"$dst := convertByteaddressToTargetaddress($src)",
[(set Regs:$dst,
(ConvertByteaddressToTargetaddress Regs:$src))]>;
}
We implement the function EmitInstrWithCustomInserter in the target
lowering by replacing these instruction by the instructions that
implement these abstract operation; in most cases shift
instructions.
MachineBasicBlock*
MyTargetLowering::EmitInstrWithCustomInserter(
MachineInstr &MI, MachineBasicBlock *BB) const {
switch (MI.getOpcode()) {
default:
break;
case Target::ConvertByteaddressToTargetaddress_rr:
return emitConvertByteaddressToTargetaddress(MI, BB);
case Target::ConvertTargetaddressToByteaddress_rr:
return emitConvertTargetaddressToByteaddress(MI, BB);
}
At this point it is possible to compile and run self-contained
applications that do not use external code.
Interaction With The System
We have to use existing target code, eg provided as libraries or even
hand-written assembler code. The functions in this code base will
probably use pointers as target addresses and not bytes addresses.
The most simpliest and most elegant solution is to use attributes to
annotate function prototypes and their parameters and results.
In the front-end (eg Clang) we add two attributes:
- byteaddress
- targetaddress
and handle these attributes by passing them to functions and their
parameters in the LLVM IR. We do use the attribute byteaddress
explicitly in functions, which are always inlined and loose their
attributes, to remind us that another attribute and its handling in
the function might lead to illegal code.
Additionally, while we edit the front-end we add two target builtins
to make address conversions in code explicit, again:
__builtin_target_convert_byteaddresstotargetaddress__builtin_target_convert_targetaddresstobyteaddress
In the front-end we transform them to intrinsics in LLVM IR.
The function prototype for an potentially hand-written external
function could be:
__attribute__((targetaddress)) int *
targetFooBar(int, __attribute__((targetaddress)) int*);
In a final transformation step during lowering, we lower the new
intrinsics to their corresponding operations. Then, we use the
function and parameter attributes
- to return pointer results (hint:
::LowerReturn) as- byte address or
- target address pointers depending on their attribute
- to pass parameter pointers (hint:
::LowerCall) as- byte address or
- target address pointers depending on their attribute
- to receive argument pointers (hint: ::LowerFormalArguments) and
transform them to bytes address pointers!
Optimizations
We haven’t mentioned code optimizations, yet. There are quite some. We
give here just some pointers.
Combining
convertByteaddressToTargetaddress(convertTargetaddressToByteaddress(ptr)) -> ptr
convertTargetaddressToByteaddress(convertByteaddressToTargetaddress(ptr)) -> ptr
Instructions Matching
"MV $dst, #($src1 <shift_op> <shift_imm>)",
[(set Regs:$dst, (ConvertTargetaddressToByteaddress tglobaladdr:$src1))]
Conclusion
We presented an approach to build back-ends in LLVM for targets, which
do not follow the principal of a byte addressed memory, without
patching LLVM. We keep all transformations on a high level and
transparent. We implemented two out-of-source back-ends following
this approach successfully. Additionally, we upgraded to newer
versions of LLVM without going through patching hell.
