LLVM Development Diary
This is just a general dump of notes I make as I work on implementing an LLVM backend for MUPS/16.
20250904
Looking at function calls again.
20250828
Fixing the bad offsets from last week, I think this is the problem, in Disassembler/Mups16Disassembler.cpp:
DecodeStatus decodeJumpTarget(MCInst &Inst, unsigned Offset,
uint64_t Address, const void *Decoder)
{
Inst.addOperand(MCOperand::createImm((SignExtend32<11>(Offset) * 2) + 2));
return MCDisassembler::Success;
}
That +2 at the end looks wrong. We're meant to be reconstructing the sequence of MCInst objects here, so the encoded instruction must match what we would have got from creating the instruction in the compiler backend, which does not have the +2.
Note for improvement: we should have the disassembler print the operand as a computed address, not an offset, to better match the assembler output. This looks like it needs the DecoderMethod for the branch and jump instructions set to a custom function, then we can implement something like the Sparc DecodeCall function.
Back to function calls. Somewhat-related note to check later: do we need to define RA as an implicit def for jal and jalr calls?
20250821
Disassembling with llvm-objdump still shows one issue:
c: 8e 3a sw -6(r5), r1 e: 30 00 j 2 10: 61 da lw r1, -6(r5)
compared to the Python disassembler:
c: 8e 3a sw (-6)r5, r1 # 10001 110 001 11010 e: 30 00 j 0 # 00110 00000000000 10: 61 da lw r1, (-6)r5 # 01100 001 110 11010
Which has the correct offset for j? I think Python.
20250429
Function call notes
Main source file: Mups16ISelLowering.cpp
20250421
I made a lot of progress on the frame lowering, and learnt a lot while doing it. Firstly, some basics.
Frame layout and frame pointers
When accessing items on the stack (either incoming arguments, local variables or the return value), the compiler accesses them at an offset from one of two pointer registers: the stack pointer (which points at the current lowest address in the stack) or the frame pointer, which points to the highest address in the current stack frame (with a bit of hand-waving here about what exactly is the highest address, which we'll get to later).
The key difference between the stack pointer and the frame pointer is that the frame pointer is fixed for the lifetime of the function, whereas the stack pointer can move as code enters and leaves scopes, etc.
In general, it's possible for the compiler to use either register to address a variable, since the compiler usually knows exactly how big the stack frame is at any point, and so can compute a positive offset from the stack pointer or a negative offset from the frame pointer for any variable (or a positive offset from the frame pointer for incoming arguments). If this is the case, why do we waste a precious register on the frame pointer, if we could make do with just the stack pointer? There are two main reasons:
- firstly, if we use a frame pointer then debuggers can use this to trivially walk back up the stack. Since every function needs to use the frame pointer, the first thing they all have to do is to push the previous value of the frame pointer onto the stack, so it can be restored on function exit. This means that whatever function the debugger is in, it can find the frame pointer of the calling function at some offset from the current frame pointer, and then it can in turn use that frame pointer to find the next, etc. looking at a function always look at convention that it pushes the value of the frame pointer as the first element on its stack. It is much more difficult (and sometimes impossible) to do the same using the stack pointer, since its value depends on which code paths have been taken.
- secondly, there are a couple of cases where the compiler cannot know at compile time how big the stack is. One of these is variable-length arrays (e.g. int local_array[n]), added in C99. As soon as one of these appears on the stack, the compiler now can't know exactly how far away from the start of the frame the stack pointer is, and hence needs a frame pointer to be able to access locals and arguments. The same applies if the function uses alloca to dynamically allocate an array on the stack.
The first reason is a quality-of-life improvement, but optional, so the convention is that at optimisation level 0 all functions will use a frame pointer, but at -O1 and higher the --fomit-frame-pointer option is turned on, and the compiler will try to avoid using it. The exception is that if the second bullet point applies, the compiler is forced to keep the frame pointer. These days it's generally considered an unnecessary optimisation, but on architectures like Mups16, which only has 7 general-purpose registers (R1-R5, SP, RA), two of which are already effectively off-limits (SP and RA), losing one more to a frame pointer is expensive.
Register scavenging
There are various places in the frame lowering code where we need to offset addresses from registers by a constant, or add/subtract a constant from a register. Since the instruction set only allows for 5-bit immediates in any of the load/store or addi instructions, if the constant is outside the range -15..16 then we need to use a combination of li (or lui and lui) to get the constant into a register, then use either lw (0)rX or add rX, rX, rY to do the full-range calculation.
This requires that we have a spare register to use for loading the constant. If our function doesn't use all the registers, we can just use one of the unused ones. In most functions, though, all four or five GPRs will be used. We could reserve a special register just for this purpose (I think the old Sparc architecture used to do this), but given we only have five this seems very wasteful. The alternative is that we need a way to temporarily spill one of the in-use registers to the stack, use it to load the constant, then restore it. LLVM already includes a mechanism for doing this, called register scavenging.
Using this requires overriding a couple of virtual functions to indicate that we want a RegisterScavenger set up before calls to certain functions. The overrides are:
- Mups16RegisterInfo::requiresRegisterScavenging, which controls overall enabling of the feature;
- Mups16RegisterInfo::requiresFrameIndexScavenging, which controls whether it is enabled specifically when calling eliminateFrameIndex. We need this on.
In order for the scavenger to be able to spill the contents of one of the registers and then restore it, we need to allocate an extra slot in the stack frame for it to use. This is done in the Mups16FrameLowering::determineCalleeSaves function, by creating an artificial stack object in the frame, and then telling the register scavenger to use it.
Anyway, enough background. For the Mups16 backend, the bits that I had to change to get this working were:
- Mups16FrameLowering::hasFP, which indicates whether a function needs a frame pointer, and which now returns true if either the function has been annotated to disable frame-pointer optimisations, or if it contains dynamic allocations, and false otherwise.
- Mups16FrameLowering::emitPrologue: uses information about the stack frame to emit the machine instructions to set up the frame. This involves saving the old stack pointer, and then adjusting it to account for the stack size. If we need a frame pointer then we also need to save the old frame pointer and then set it to point to the first element on the stack (which is the old frame pointer we just saved). There's also a trivial optimisation we can make here, where, if a function doesn't use the stack at all, we don't modify anything. This may come back to bite me, so I might remove it (the compiler does a very good job of removing the prologue and epilogue at higher optimisation levels anyway).
- Mups16FrameLowering::emitEpilogue: the converse of the above, cleans up the stack frame by restoring the old stack pointer, and optionally the old frame pointer.
- Mups16FrameLowering::determineCalleeSaves: this computes a bit vector containing one bit for every register, and is responsible for deciding which registers need to be saved. In our case it also includes the extra stack slot for register scavenging (see above)
- Mups16InstrInfo::storeRegToStackSlot: this emits code to store a register to the stack, as the name suggests. The only catch is that we don't know enough to emit an actual machine instruction yet, so we emit a 'dummy' instruction that has the FrameIndex
With this, I think it's finally time to start expanding out the test program to include calls to external functions, and some structures. I'm sure that will break lots of things again.
20250420 - update
I've been looking at my function entry and exit code. The frame lowering is very crude at the moment, and always sets up a stack, spills r5 (used as a frame pointer) and then sets up sp, even if the function doesn't use the stack. It also has some obvious bugs. For example:
int itoa(unsigned int val_, char* buf_)
{
return val_;
}
gives the following (hand-annotated with some extra comments):
.text
.file "iconv.c"
.globl itoa ; -- Begin function itoa
.p2align 1
.type itoa,@function
itoa: ; @itoa
; %bb.0: ; %entry
sw -2(sp), r5 ; save callee r5 register
addi r5, sp, -2 ; set r5 (base pointer) to sp-2
addi sp, sp, -2 ; set sp to sp-2 (why?)
lw r1, 2(r5) ; load val_ from stack (pushed by caller)
lw r1, r5 ; move val_ to return register
lw r1, r5 ; again (why is this duplicated?)
addi sp, r5, 0 ; restore sp from r5 (incorrect, it's off-by-two!)
lw r5, -4(r5) ; restore callee r5 (incorrect, it should be lw r5, 0(r5)
jr ra ; return
.Lfunc_end0:
.size itoa, .Lfunc_end0-itoa
; -- End function
For future reference, code locations involved in this:
- Mups16FrameLowering.cpp, has explicit code for emitting prologue and epilog, and spilling saved registers. Contains hasFP.
- Mups16RegisterInfo.cpp, has eliminateFrameIndex, which realises the virtual frame index that LLVM uses with a real register, as well as info on reserved, callee-saved and caller-saved registers (esp. Mups16RegisterInfo::getFrameRegister)
- Mups16InstrInfo.cpp, contains loadRegFromStackSlot, storeRegToStackSlot etc.
20250420
I fixed up the load and jr/jalr instructions the same way as I'd already fixed stores, and I finally have something that seems to compile my test program as an ELF object file and correctly encode all the instructions, and can disassemble it again! As a reminder, here's the C program:
char* const CONSOLE=(char* const)0xA00;
void print()
{
static const char* const msg = "Hello, world!";
const char* ptr = msg;
while (*ptr)
{
*CONSOLE = *ptr;
}
}
and the post-compilation output:
$ bin/llvm-objdump -d --all-headers main.o --triple mups16
main.o: file format elf32-unknown
architecture: unknown
start address: 0x00000000
Program Header:
Dynamic Section:
Sections:
Idx Name Size VMA Type
0 00000000 00000000
1 .strtab 0000005c 00000000
2 .text 00000028 00000000 TEXT
3 .rela.text 00000018 00000000
4 .rodata 00000004 00000000 DATA
5 .rela.rodata 0000000c 00000000
6 .rodata.str1.1 0000000e 00000000 DATA
7 .symtab 00000070 00000000
SYMBOL TABLE:
00000000 l df *ABS* 00000000 main.c
00000000 l O .rodata.str1.1 0000000e .str
00000002 l O .rodata 00000002 print.msg
00000000 l d .rodata.str1.1 00000000 .rodata.str1.1
00000000 g O .rodata 00000002 CONSOLE
00000000 g F .text 00000028 print
Disassembly of section .text:
00000000 <print>:
0: 8d de sw -2(sp), r5
2: 06 be addi r5, sp, -2
4: 05 bc addi sp, sp, -4
6: 71 00 liu r1, 0
00000006: R_MUPS16_LO8 .rodata.str1.1
8: 79 00 lui r1, 0
00000008: R_MUPS16_HI8 .rodata.str1.1
a: 8e 20 sw r5, r1
c: 30 00 j 2
e: 61 c0 lw r1, r5
10: 59 20 lbu r1, r1
12: b1 07 bz r1, 16
14: 30 00 j 2
16: 61 c0 lw r1, r5
18: 59 20 lbu r1, r1
1a: 76 00 liu r5, 0
1c: 7e 0a lui r5, 10
1e: 86 20 sb r5, r1
20: 37 f6 j -18
22: 05 c0 addi sp, r5, 0
24: 66 dc lw r5, -4(r5)
26: 47 00 jr ra
The main changes needed were to templatise the encoding and decoding of memory operands to account for the difference in the immediate size between the load/store instructions (with a 5-bit immediate) and the jump reg ones (with an 8-bit immediate).
Note that there are still some obvious bugs here, in the prologue and epilogue (which I'll write up when I have a moment). I'll look at those next.
I should also really start adding unit tests for things like instruction encoding and decoding, so that I don't end up breaking things again. Eyeballing raw bytes and disassembly output isn't always the best way to test correctness of a compiler.
20250419
Turns out my issue with branches was very simple, though very annoying: I had failed to match up the names of the operands in the instruction definitions with those in instruction formats. In Mups16InstrInfo.td I had:
def BZ : InstMupsII1<22, (ins IntReg:$rs1, brtarget:$offset),
"bz $rs1, $offset",
[(brcond (i16 (seteq IntReg:$rs1, 0)), bb:$offset)]>;
with the definition in Mups16InstrFormats.td:
class InstMupsII1<bits<5> opcode, dag ins, string asmstr, list<dag> pattern>
: InstMups<opcode, (outs), ins, asmstr, pattern>
{
bits<3> rs1;
bits<8> imm8;
let Inst{10-8} = rs1;
let Inst{7-0} = imm8;
}
Since $offset doesn't appear in the instruction class, it seems to just default to operand 0 somehow. I wasted an hour chasing my tail when I thought I'd realised this and changed it $offset to $imm5 out of habit, forgetting that branches have 8-bit offsets. In desperation, I tried creating a new instruction class just for branches with reg and offset fields, and changed the names in the instruction definitions to match, and everything worked. Working backwards to see what the minimum difference from the broken setup was made me notice the mismatch in names. It's a pity tablegen doesn't seem to give any warnings about this.
Anyway, with that fixed, I think we now have a working ELF object file! I'm pretty sure I've broken llvm-based disassembly somewhere in all these changes, so I'll go back and fix that now, just for completeness. Then I can start making the test program slightly more complex, to see what breaks next.
TODO:
- fix up load instructions the same way stores are done
20250418
I did a bit of cleanup of instruction encodings, to correct a couple more places I'd found where operands were being encoded in the wrong order. There are a few remaining problems in the test program:
Disassembly of section .text:
0: 8d de sw (-2)sp, r5
2: 06 be addi r5, sp, -2
4: 05 bc addi sp, sp, -4
6: 71 00 liu r1, 0
8: 79 00 lui r1, 0
a: 8e 20 sw r5, r1
c: 30 00 j 0
e: 61 26 lw r1, (6)r1
10: 59 21 lbu r1, (1)r1
12: b1 01 bz r1, 2
14: 30 00 j 0
16: 61 26 lw r1, (6)r1
18: 59 21 lbu r1, (1)r1
1a: 76 00 liu r5, 0
1c: 7e 0a lui r5, 10
1e: 86 20 sb r5, r1
20: 37 f6 j -20
22: 05 c0 addi sp, r5, 0
24: 66 c6 lw r5, (6)r5
26: 47 00 jr ra
Firstly, why is the branch offset 2 at byte 0x12, when it should be jumping forward 14 bytes?
...
bz r1, .LBB0_3
j .LBB0_2
.LBB0_2: ; %while.body
; in Loop: Header=BB0_1 Depth=1
lw r1, r5
lbu r1, r1
liu r5, 0
lui r5, 10
sb r5, r1
j .LBB0_1
.LBB0_3: ; %while.end
Secondly, I still haven't looked at why the load instructions have bad offsets applied. Maybe I'll look at that next, for a break from branches.
Yep, sure enough, the operand encoding is wrong again here. From Mups16GenMCCodeEmitter.inc:
case MUPS::LB:
case MUPS::LBU:
case MUPS::LW: {
// op: rdd
op = getMachineOpValue(MI, MI.getOperand(0), Fixups, STI);
op &= UINT64_C(7);
op <<= 8;
Value |= op;
// op: rs1
op = getMachineOpValue(MI, MI.getOperand(0), Fixups, STI);
op &= UINT64_C(7);
op <<= 5;
Value |= op;
// op: imm5
op = getMachineOpValue(MI, MI.getOperand(1), Fixups, STI);
op &= UINT64_C(31);
Value |= op;
break;
}
It's using operand zero for both the dest and source registers, then operand one for the immediate.
Well, this one has me stumped. I tried all sorts of things to fix this, but nothing seemed to work, even though I had made exactly the same fixes that worked for the sw and sb instructions earlier. In the end, through sheer desperation, I tried renaming the operands in the Mups16InstrFormats.td file, and suddenly everything worked. It's very strange. This breaks:
class InstMupsMemLoad<bits<5> opcode, dag outs, dag ins, string asmstr, list<dag> pattern>
: InstMups<opcode, outs, ins, asmstr, pattern>
{
bits<3> rdd;
bits<3> rs2;
bits<5> imm5;
let Inst{10-8} = rdd;
let Inst{7-5} = rs2;
let Inst{4-0} = imm5;
}
but if I change the name of the first bitfield to anything else, it's fine. So, I ended up with just
class InstMupsMemLoad<bits<5> opcode, dag outs, dag ins, string asmstr, list<dag> pattern>
: InstMups<opcode, outs, ins, asmstr, pattern>
{
bits<3> rd;
bits<3> rs2;
bits<5> imm5;
let Inst{10-8} = rd;
let Inst{7-5} = rs2;
let Inst{4-0} = imm5;
}
I cannot see what's special about rdd. It doesn't seem to be referenced specially anywhere, and I've used it in other instructions with no issues. I'll have to come back to this at some point, but for now I'm tired of it and going to look at the dodgy branches again.
Well, I wanted a break from tablegen weirdness, and guess where I've ended up: right back in Mups16GenMCCodeEmitter.inc. The generated code for branch instructions looks wrong:
case MUPS::BNZ:
case MUPS::BZ: {
// op: rs1
op = getMachineOpValue(MI, MI.getOperand(0), Fixups, STI);
op &= UINT64_C(7);
op <<= 8;
Value |= op;
// op: imm8
op = getMachineOpValue(MI, MI.getOperand(0), Fixups, STI);
op &= UINT64_C(255);
Value |= op;
break;
}
Compare this to the jump ones:
case MUPS::J:
case MUPS::JAL: {
// op: imm11
op = getJumpTargetOpValue(MI, 0, Fixups, STI);
op &= UINT64_C(2047);
Value |= op;
break;
}
Jumps are correctly using the custom getJumpTargetOpValue, but branches are a) using the general operand encoder instead of getBranchTargetOpValue, and b) have the same annoying problem with using operand 0 for both rs1 and imm8. I guess I can't punt on trying to understand this issue.
20250417
I found a few more issues with the fixups. Firstly, in Mups16AsmBackend.cpp, the code for adjustFixupValue was always updating only the second byte of an instruction. This is correct for the lui and liu instructions and branches (all of which have an 8-bit immediate in the lower byte of the instruction), but it's wrong for J-type instructions, where the 11-bit immediate extends into the top half. There was a second bug in Mups16InstrInfo.td, where the jump instructions were re-using the brtarget operand type, which both meant that jumps were limited to 8-bit offsets, and also was causing their fixups to be emitted as type fixup_mups16_br8, instead of fixup_mups16_j11. Fixing this (by adding a new jtarget operand) almost had jumps and branches working.
There was another bug in the branch and jump target fixups, in Mups16MCCodeEmitter::getJumpTargetOpValue: it looks like the value that is passed in is just the full byte offset, which needs to have 2 subtracted (to account for the fact that PC has already been incremented when the jump or branch destination address is calculated), and then divided by two (since that's how we encode offsets, with an implicit 0 in the bottom bit).
This gives slightly better output now:
Disassembly of section .text:
0: 8d de sw (-2)sp, r5
2: 06 be addi r5, sp, -2
4: 05 bc addi sp, sp, -4
6: 71 00 liu r1, 0
8: 79 00 lui r1, 0
a: 8e 20 sw (0)r5, r1
c: 30 00 j 0
e: 61 c1 lw r1, (1)r5
10: 59 21 lbu r1, (1)r1
12: b1 01 bz r1, 2
14: 30 00 j 0
16: 61 c1 lw r1, (1)r5
18: 59 21 lbu r1, (1)r1
1a: 76 00 liu r5, 0
1c: 7e 0a lui r5, 10
1e: 86 20 sb (0)r5, r1
20: 37 f6 j -20
22: 05 c0 addi sp, r5, 0
24: 66 c6 lw r5, (6)r5
26: 47 00 jr ra, 0
20250416
I've been down a few blind alleys, largely because the fragment data is stored in a SmallVector that has two sets of storage (one inline array for arrays of 32 or fewer bytes, and one for vectors bigger than that). When I was inspecting the state I was accidentally always looking at the inline section, and that, annoyingly, always looked correct. It was only when I realised the mistake that I started being able to see the bad data:
(lldb) bt 5
* thread #1, queue = 'com.apple.main-thread', stop reason = step in
* frame #0: 0x00000001011ebccc llc`llvm::MCEncodedFragmentWithContents<32u>::getContents(this=0x0000600003c1b480) const at MCFragment.h:188:61
frame #1: 0x00000001011ed970 llc`writeFragment(OS=0x00006000031181d0, Asm=0x0000000146017600, Layout=0x000000016fdfd040, F=0x0000600003c1b480) at MCAssembler.cpp:569:35
frame #2: 0x00000001011ed258 llc`llvm::MCAssembler::writeSectionData(this=0x0000000146017600, OS=0x00006000031181d0, Sec=0x00000001460190f8, Layout=0x000000016fdfd040) const at MCAssembler.cpp:725:5
frame #3: 0x00000001011ca934 llc`(anonymous namespace)::ELFWriter::writeSectionData(this=0x000000016fdfcf88, Asm=0x0000000146017600, Sec=0x00000001460190f8, Layout=0x000000016fdfd040) at ELFObjectWriter.cpp:858:9
frame #4: 0x00000001011c9504 llc`(anonymous namespace)::ELFWriter::writeObject(this=0x000000016fdfcf88, Asm=0x0000000146017600, Layout=0x000000016fdfd040) at ELFObjectWriter.cpp:1102:5
(lldb) x/8bx &Contents.InlineElts
0x600003c1b4d8: 0x8d 0xde 0x06 0xbe 0x05 0xbc 0x71 0x00
(lldb) x/8bx Contents.BeginX
0x6000020154f0: 0x8d 0xee 0x06 0xbe 0x05 0xbc 0x71 0x00
The first has the correct 0x8d 0xde pair, the second shows the corrupted one.
With that waste of time out of the way, I went back up the stack a few frames and started looking at the MCAssembler::layout function. This has some handy debug output I'd not seen before, so I turned on -debug-only=mc-dump. This dumps the contents of the section at various points as it's laid out. Looking at the final output, though, I had:
assembler backend - final-layout
--
<MCAssembler
...
<MCDataFragment<MCFragment 0x600000c3b480 LayoutOrder:3 Offset:0 HasInstructions:1 BundlePadding:0>
Contents:[8D,DE,06,BE,05,BC,71,00,79,00,8E,20,30,00,61,C1,59,21,B1,01,30,00,61,C1,59,21,76,00,7E,0A,86,20,30,00,05,C0,66,C6,40,07] (40 bytes),
This is still correct. There is one final bit of code after this log line, though, and it does fixups, which is interesting. So, I added a new debug line at the end, recompiled, and now the second byte is wrong:
assembler backend - post-fixups
--
<MCAssembler
...
<MCDataFragment<MCFragment 0x600000c3b480 LayoutOrder:3 Offset:0 HasInstructions:1 BundlePadding:0>
Contents:[8D,EE,06,BE,05,BC,71,00,79,00,8E,20,30,00,61,C1,59,21,B1,01,30,00,61,C1,59,21,76,00,7E,0A,86,20,30,00,05,C0,66,C6,40,07] (40 bytes),
So, it is fixups. And, sure enough, now I know where to look, I stepped through the fixup applications, and lo and behold, found this gem in Mups16AsmBackend::applyFixup:
MCContext &Ctx = Asm.getContext();
Value = adjustFixupValue(Fixup, Value, Ctx);
if (!Value)
{
return; // Doesn't change encoding (we already encoded zero)
}
// We could get info on which bits change from the fixup, but so far we only
// have two cases, both of which just change the bottom byte of the
// instruction word, so we can hard-code this for now. Where do we start in
Data[1] = Value;
Yeah. Data in this case is the entire code buffer, not just the bytes starting at the fixup location. So that means that we're always modifying the second byte of the whole .text segment, instead of the second byte of the fixup. For now, I changed the last line to
Data[Fixup.getOffset() + 1] = Value;
And with that, a quick recompile later, and we have:
$ python3 -m mups16.utils.disassemble_elf ~/git/llvm-project/build/main.o
Disassembly of section .text:
0: 8d de sw (-2)sp, r5
2: 06 be addi r5, sp, -2
4: 05 bc addi sp, sp, -4
6: 71 00 liu r1, 0
8: 79 00 lui r1, 0
a: 8e 20 sw (0)r5, r1
c: 30 02 j 4
e: 61 c1 lw r1, (1)r5
10: 59 21 lbu r1, (1)r1
12: b1 01 bz r1, 2
14: 30 02 j 4
16: 61 c1 lw r1, (1)r5
18: 59 21 lbu r1, (1)r1
1a: 76 00 liu r5, 0
1c: 7e 0a lui r5, 10
1e: 86 20 sb (0)r5, r1
20: 30 ee j 476
22: 05 c0 addi sp, r5, 0
24: 66 c6 lw r5, (6)r5
26: 40 07 jr zero, 14
Finally, the first word is correct. There are still problems with the jumps, and the odd offsets to the load instructions, and the final jump is meant to be jr ra, but it's some progress.
20250412
Looking at the last issue from the previous debugging, it's quite interesting. In the output binary, the first two bytes of the text section are 8d ee. If I run the assembly through customasm, which is my reference for correct binary output, then I get 8d de. So, the second byte of the section is wrong. If I run llc under the debugger, all the operands etc. look correct. More interestingly, if I run llc with debug output on I can clearly see what looks like the correct bytes in the second MCDataFragment in the debug output:
<MCAssembler
Sections:[
<MCSection Fragments:[
<MCDataFragment<MCFragment 0x600000fa81e0 LayoutOrder:0 Offset:0 HasInstructions:0 BundlePadding:0>
Contents:[] (0 bytes)>,
<MCAlignFragment<MCFragment 0x6000013a43c0 LayoutOrder:1 Offset:0 HasInstructions:0> (emit nops)
Alignment:4 Value:0 ValueSize:1 MaxBytesToEmit:4>>,
<MCAlignFragment<MCFragment 0x6000013a1180 LayoutOrder:2 Offset:0 HasInstructions:0> (emit nops)
Alignment:2 Value:0 ValueSize:1 MaxBytesToEmit:2>>,
<MCDataFragment<MCFragment 0x600000fac000 LayoutOrder:3 Offset:0 HasInstructions:1 BundlePadding:0>
Contents:[8D,DE,06,BE,05,BC,71,00,79,00,8E,20,30,00,61,C1,59,21,B1,01,30,00,61,C1,59,21,76,00,7E,0A,86,20,30,00,05,C0,66,C6,40,07] (40 bytes),
Fixups:[<MCFixup Offset:6 Value:%lo(.str) Kind:128>,
<MCFixup Offset:8 Value:%hi(.str) Kind:129>,
<MCFixup Offset:12 Value:.LBB0_1 Kind:130>,
<MCFixup Offset:20 Value:.LBB0_2 Kind:130>,
<MCFixup Offset:32 Value:.LBB0_1 Kind:130>]>]>,
and confirming that 8d de looks correct:
$ python3 -m mups16.io_board.disassemble '8d de'
sw (-2)sp, r5 # TypeIInstruction(bits=bitarray('1000110111011110'), name='sw', opcode=17, rdd=<Register.SP: 5>, rs0=<Register.R5: 6>, imm=-2)
So, how is the data changing between the final output of the MCAssembler component, and the file? Time to dig out the debugger again...
20250330
I had a couple of flights and time in airports, so I've made a bit more progress on the backend. Going back to the last time I looked, in December, one obvious issue was that the registers were completely wrong in the generated ELF binary. From the notes below it's clear that the ordering of the operands is just wrong. With a combination of manual inspection of the tablegen output files (mainly Mups16GenRegisterInfo.inc and Mups16GenMCCodeEmitter.inc) and sticking llc in the debugger, I tracked this down to a couple of issues. Firstly, I needed to add the HWEncoding field to my register definitions:
class Mups16Reg<bits<16> num, string n> : Register<n> {
let HWEncoding = num;
let Namespace = "MUPS";
}
Without this it seems that everything ends up mapping to register zero if the code is generated by pattern matching, at least. That would explain why most of the registers in the ELF output seemed to be zero. The only exceptions were ones that were in instructions I'd manually created from C++, in things like the frame lowering code at the start of the function.
The second issue was more annoying. I had tried to cut down on duplication in my instruction definitions by using the following:
class InstMupsI<bits<5> opcode, dag outs, dag ins, string asmstr, list<dag> pattern>
: InstMups<opcode, outs, ins, asmstr, pattern>
{
bits<5> imm5;
let Inst{4-0} = imm5;
}
// ...
class InstMupsI2<bits<5> opcode, dag ins, string asmstr, list<dag> pattern>
: InstMupsI<opcode, (outs), ins, asmstr, pattern>
{
bits<3> rs1;
bits<3> rs2;
let Inst{10-8} = rs1;
let Inst{7-5} = rs2;
}
The I2 variant derives from the I one, and adds the register info. However, it seems that it's not enough that the bit indices in the Inst part are correct; the ordering that the bits<x> definitions appear also seems to be significant. Since the imm5 field is in the base class it's initialised first, and so the instruction encoding code in Mups16GenMCCodeEmitter.inc expects the imm operand to be the first one. I'm not sure what the best fix for this is, but for now I've taken the expedient step of just removing the inheritance and just defining fully-spec'ed instruction formats. For example, my memory instructions like sw, sb etc. now use:
class InstMupsMemI2<bits<5> opcode, dag ins, string asmstr, list<dag> pattern>
: InstMups<opcode, (outs), ins, asmstr, pattern>
{
bits<3> rs1;
bits<5> imm5;
bits<3> rs2;
let Inst{10-8} = rs1;
let Inst{4-0} = imm5;
let Inst{7-5} = rs2;
}
With this fix in the output looks better, though still not completely correct. I hacked up a python script that reads the ELF file, and passes the bytes in the .text section through my own disassembler, to let me concentrate on getting the ELF output right without fighting bugs in my LLVM disassembler at the same time:
$ python3 -m mups16.utils.disassemble_elf ~/git/llvm-project/build/main.o
Disassembly of section .text:
0: 8d ee sw (14)sp, ra
2: 06 be addi r5, sp, -2
4: 05 bc addi sp, sp, -4
6: 71 00 liu r1, 0
8: 79 00 lui r1, 0
a: 8e 20 sw (0)r5, r1
c: 30 00 j 0
e: 61 c1 lw r1, (1)r5
10: 59 21 lbu r1, (1)r1
12: b1 01 bz r1, 2
14: 30 00 j 0
16: 61 c1 lw r1, (1)r5
18: 59 21 lbu r1, (1)r1
1a: 76 00 liu r5, 0
1c: 7e 0a lui r5, 10
1e: 86 20 sb (0)r5, r1
20: 30 00 j 0
22: 05 c0 addi sp, r5, 0
24: 66 c6 lw r5, (6)r5
26: 40 07 jr zero, 14
The first instruction is still wrong, but the next few look much better. There are still a few issues:
- the liu/lui pair have zero operands because I'm not handling the fixups in the disassembler. That's not an output problem, though
- the load instructions at address 0xe, 0x10, etc. all seem to have an erroneous 1 offset
- the very first instruction still has incorrect immediate and register operands
20241201
OK, further investigation into the bad code output: firstly, the code in Mups16GenMCCodeEmitter.inc just seems plain wrong. For example, this is the output for the two load operations:
case MUPS::LB:
case MUPS::LBU:
case MUPS::LW: {
// op: imm5
op = getMachineOpValue(MI, MI.getOperand(0), Fixups, STI);
op &= UINT64_C(31);
Value |= op;
// op: rdd
op = getMachineOpValue(MI, MI.getOperand(0), Fixups, STI);
op &= UINT64_C(7);
op <<= 8;
Value |= op;
// op: rs1
op = getMachineOpValue(MI, MI.getOperand(1), Fixups, STI);
op &= UINT64_C(7);
op <<= 5;
Value |= op;
break;
}
This is using operand 0 (the destination register) for both the destination and the immediate, then using operand 1 (the source register) for the immediate. No wonder things are wrong. Similarly, I see the branch instructions using operand 0 for both operands (the test register and the immediate branch distance). Both these cases use custom operand types, so I suspect it's something to do with the way I've defined them in Mups16InstrInfo.td.
The second problem might explain the bad registers in instructions unaffected by the first problem, though. In Mups16GenRegisterInfo.inc, tablegen has output this:
namespace MUPS {
enum {
NoRegister,
FLG = 1,
PC = 2,
RA = 3,
SP = 4,
SPC = 5,
TMP = 6,
TSP = 7,
R0 = 8,
R1 = 9,
R2 = 10,
R3 = 11,
R4 = 12,
R5 = 13,
S1 = 14,
S2 = 15,
S3 = 16,
NUM_TARGET_REGS // 17
};
} // end namespace MUPS
The ordering of those registers seems completely wrong.
20241130
Haven't had time to look at this for a couple of weeks, but coming back tonight I think I was trying to get the disassembler to work. Current state of the world isn't great. If I dump my process as assembly directly from llc, I see
$ bin/llc -O0 -march=mups16 -relocation-model=static -filetype=asm main.bc -o main.s && cat main.s
.text
.file "main.c"
.globl print ; -- Begin function print
.p2align 1
.type print,@function
print: ; @print
; %bb.0: ; %entry
sw -2(sp), r5
addi r5, sp, -2
addi sp, sp, -4
liu r1, %lo(.str)
lui r1, %hi(.str)
sw r5, r1
j .LBB0_1
...
Compiling to a .o file and then disassembling, I get:
$ bin/llvm-objdump -d main.o --triple mups16
main.o: file format elf32-unknown
Disassembly of section .text:
00000000 <print>:
0: 8e ee sw 14(r0), spc
2: 00 1e addi r0, r0, 30
4: 00 1c addi r0, r0, 28
6: 70 00 liu r0, 0
8: 78 00 lui r0, 0
a: 88 00 sw r0, spc
c: 30 00 j 2
e: 60 00 lw spc, r0
10: 58 00 lbu spc, spc
12: b0 00 bz r0, llvm-objdump: /home/ali/git/llvm-project/llvm/include/llvm/ADT/SmallVector.h:180: const T& llvm::SmallVectorTemplateCommon<T, <template-parameter-1-2> >::operator[](llvm::SmallVectorTemplateCommon<T, <template-parameter-1-2> >::size_type) const [with T = llvm::MCOperand; <template-parameter-1-2> = void; llvm::SmallVectorTemplateCommon<T, <template-parameter-1-2> >::const_reference = const llvm::MCOperand&; llvm::SmallVectorTemplateCommon<T, <template-parameter-1-2> >::size_type = long unsigned int]: Assertion `idx < size()' failed.
There are a lot of things wrong here. It looks like all offsets are being treated as unsigned instead of signed (hence 30 instead of -2 in the second instruction), and all the registers are wrong. The registers aren't even consistently wrong (r5 in the first instruction is printed as spc, but at address 0xa it's printed as r0. At address 0x2 it even manages to print r0 for two different registers).
I hacked up a quick Python script to disassemble a hex string (based on code I'd already used and verified in the io_board shell, for watching the instruction stream), and got this:
$ PYTHONPATH=. python3 mups16/io_board/disassemble.py '8e ee 00 1e 00 1c 70 00 78 00 88 00 30 00'
sw (14)r5, ra # TypeIInstruction(bits=bitarray('1000111011101110'), name='sw', opcode=17, rdd=<Register.R5: 6>, rs0=<Register.RA: 7>, imm=14)
addi zero, zero, -2 # TypeIInstruction(bits=bitarray('0000000000011110'), name='addi', opcode=0, rdd=<Register.Zero: 0>, rs0=<Register.Zero: 0>, imm=-2)
addi zero, zero, -4 # TypeIInstruction(bits=bitarray('0000000000011100'), name='addi', opcode=0, rdd=<Register.Zero: 0>, rs0=<Register.Zero: 0>, imm=-4)
liu zero, 0 # TypeIIInstruction(bits=bitarray('0111000000000000'), name='liu', opcode=14, rdd=<Register.Zero: 0>, imm=0)
lui zero, 0 # TypeIIInstruction(bits=bitarray('0111100000000000'), name='lui', opcode=15, rdd=<Register.Zero: 0>, imm=0)
sw (0)zero, zero # TypeIInstruction(bits=bitarray('1000100000000000'), name='sw', opcode=17, rdd=<Register.Zero: 0>, rs0=<Register.Zero: 0>, imm=0)
j 0 # TypeJInstruction(bits=bitarray('0011000000000000'), name='j', opcode=6, imm=0)
Which is similar, but not quite the same as the disassembler output. This is interesting, since it seems like there are two separate problems here: the disassembler is wrong, but so is the binary being generated in the first place. The immediate in the first is wrong, the register indices are wrong. Only the opcode seems solid.
Just verifying, I ran the instructions from the generated .s file through my customasm version to check what the bytes output should be, and I get
0:0 | 0 | 8d de sw [-2]sp, r5 2:0 | 2 | 06 be addi r5, sp, -2 4:0 | 4 | 05 bc addi sp, sp, -4 6:0 | 6 | 71 00 liu r1, 0 8:0 | 8 | 79 00 lui r1, 0 a:0 | a | 8e 20 sw r5, r1
confirming that the binary is indeed wrong, too. Comparing some of the instructions in binary, there's no obvious pattern:
Correct: 10001 101 110 11110 Incorrect: 10001 110 111 01110 Correct: 00000 110 101 11110 Incorrect: 00000 000 000 11110 Correct: 10001 110 001 00000 Incorrect: 10001 000 000 00000
Some have all zero register bits, some just have bad ones. Some have correct immediates, some have incorrect. Weird. Time to get the debugger out to look at how I'm generating the bits for the output. I thought it was all table-generated (and presumably would be correct, given that the assembly output looks correct), but obviously not...
Well, this looks like the culprit:
Breakpoint 2, llvm::Mups16MCCodeEmitter::getBinaryCodeForInstr (this=0x5555599bfdb0, MI=..., Fixups=..., STI=...) at /home/ali/git/llvm-project/build/lib/Target/Mups16/Mups16GenMCCodeEmitter.inc:295
295 op = getMachineOpValue(MI, MI.getOperand(0), Fixups, STI);
(gdb) p MI.getOperand(0)
$4 = (const llvm::MCOperand &) @0x7fffffffd040: {Kind = llvm::MCOperand::kRegister, {RegVal = 4, ImmVal = 4, FPImmVal = 1.9762625833649862e-323, ExprVal = 0x4, InstVal = 0x4}}
(gdb) p MI.getOperand(1)
$5 = (const llvm::MCOperand &) @0x7fffffffd050: {Kind = llvm::MCOperand::kImmediate, {RegVal = 4294967294, ImmVal = -2, FPImmVal = -nan(0xffffffffffffe), ExprVal = 0xfffffffffffffffe, InstVal = 0xfffffffffffffffe}}
(gdb) p MI.getOperand(2)
$6 = (const llvm::MCOperand &) @0x7fffffffd060: {Kind = llvm::MCOperand::kRegister, {RegVal = 13, ImmVal = 13, FPImmVal = 6.4228533959362051e-323, ExprVal = 0xd, InstVal = 0xd}}
Looking at the generated code, we have:
case MUPS::SB:
case MUPS::SW: {
// op: imm5
op = getMachineOpValue(MI, MI.getOperand(0), Fixups, STI);
op &= UINT64_C(31);
Value |= op;
// op: rs1
op = getMachineOpValue(MI, MI.getOperand(1), Fixups, STI);
op &= UINT64_C(7);
op <<= 8;
Value |= op;
// op: rs2
op = getMachineOpValue(MI, MI.getOperand(2), Fixups, STI);
op &= UINT64_C(7);
op <<= 5;
Value |= op;
break;
}
For some reason a) the operands are in the wrong order (0 is a register, but is being treated as the immediate) and the register values seem wrong, too. Tomorrow I'll have a look at how the assembler output uses these, since it seems to get it right.
20241118
Well, that's annoying. I spent ages trying to work out why I was seeing
LLVM ERROR: Undefined temporary symbol .LBB0_2
when compiling with llc now, digging around my lowering code, checking I hadn't messed up anything in the MCStreamer changes I made, etc. In the end, it turned out to just be that I'd forgotten to mark my jump and branch instructions with isBranch and isTerminator. I added
let isBranch = 1, isTerminator = 1 in {
...
}
around the definitions of the 6 jump/branch instructions, and now it's working again.
20241113
I was wondering why operands are incorrect in the ELF output, when they seem to be correct in assembly output, so I tried re-generating the main.s file for the first time in a couple of days, and now I'm seeing what looks like the same problem showing up there (which is good, in some ways; at least it's consistent):
$ bin/llc -O0 -march=mups16 -relocation-model=static -filetype=asm main.bc -o main.s && cat main.s llc: /home/ali/git/llvm-project/llvm/lib/Target/Mups16/MCTargetDesc/Mups16InstPrinter.cpp:76: void llvm::Mups16InstPrinter::printMemOperand(const llvm::MCInst*, unsigned int, llvm::raw_ostream&, const char*): Assertion `Disp.isImm() && "Expected immediate in displacement field"' failed. ... #10 0x000055f06cbe75e3 llvm::Mups16InstPrinter::printMemOperand(llvm::MCInst const*, unsigned int, llvm::raw_ostream&, char const*) /home/ali/git/llvm-project/llvm/lib/Target/Mups16/MCTargetDesc/Mups16InstPrinter.cpp:77:22 #11 0x000055f06cbe70fe llvm::Mups16InstPrinter::printInstruction(llvm::MCInst const*, unsigned long, llvm::raw_ostream&) /home/ali/git/llvm-project/build/lib/Target/Mups16/Mups16GenAsmWriter.inc:347:10 #12 0x000055f06cbe73b4 llvm::Mups16InstPrinter::printInst(llvm::MCInst const*, unsigned long, llvm::StringRef, llvm::MCSubtargetInfo const&, llvm::raw_ostream&) /home/ali/git/llvm-project/llvm/lib/Target/Mups16/MCTargetDesc/Mups16InstPrinter.cpp:34:18 #13 0x000055f06d95896e (anonymous namespace)::MCAsmStreamer::emitInstruction(llvm::MCInst const&, llvm::MCSubtargetInfo const&) /home/ali/git/llvm-project/llvm/lib/MC/MCAsmStreamer.cpp:2049:27
Ahhh, I think this specific error is because at some point I swapped the order of the operands for sw in Mups16InstrInfo.td, and I didn't adjust it somewhere else to match. Stupid error.
In my debugging, though, I think I did work out a bit more about why the operands looked so odd in the gdb output yesterday: the contents of the RegVal field is not the register number, but an index. To get the raw bit value, we need to call
return Ctx.getRegisterInfo()->getEncodingValue(MO.getReg());
which I am already doing in Mups16MCCodeEmitter::getMachineOpValue, so not sure why it wasn't working. Well, at least it's one mystery solved.
Swapped the order back for now (I only changed it to see if it helped with using my custom decoder for disassembly, and it didn't). Now I'm hitting a more expected error, since I made some return 0; stubs into assertions, to force me to implement more bits.
I added two new fixup types: br8, for 8-bit PC-relative branch targets, and j11, for 11-bit PC-relative jump targets. I had to add these in three places:
- MCTargetDesc/Mups16FixupKinds.h
- MCTargetDesc/Mups16ELFObjectWriter.cpp
- MCTargetDesc/Mups16AsmBackend.cpp
I think I also need to define a new operand type for the J and JAL instructions, so that it can be encoded with the different fixup type.
Now we have a more interesting problem:
LLVM ERROR: Undefined temporary symbol .LBB0_2 ... #10 0x000055879c2ea51f (anonymous namespace)::ELFWriter::computeSymbolTable(llvm::MCAssembler&, llvm::MCAsmLayout const&, llvm::DenseMap<llvm::MCSectionELF const*, unsigned int, llvm::DenseMapInfo<llvm::MCSectionELF const*>, llvm::detail::DenseMapPair<llvm::MCSectionELF const*, unsigned int> > const&, llvm::DenseMap<llvm::MCSymbol const*, unsigned int, llvm::DenseMapInfo<llvm::MCSymbol const*>, llvm::detail::DenseMapPair<llvm::MCSymbol const*, unsigned int> > const&, std::map<llvm::MCSectionELF const*, std::pair<unsigned long, unsigned long>, std::less<llvm::MCSectionELF const*>, std::allocator<std::pair<llvm::MCSectionELF const* const, std::pair<unsigned long, unsigned long> > > >&) /home/ali/git/llvm-project/llvm/lib/MC/ELFObjectWriter.cpp:644:7
This matches something I noticed yesterday in the generated assembly, but hadn't had a chance to look at yet:
sw r5, r1
j .LBB0_1
.LBB0_1: ; %while.cond
; =>This Inner Loop Header: Depth=1
lw r1, r5
lbu r1, r1
bz r1, .LBB0_3
j .LBB0_2
; %bb.2: ; %while.body
; in Loop: Header=BB0_1 Depth=1
lw r1, r5
lbu r1, r1
liu r5, 0
lui r5, 10
sb r5, r1
j .LBB0_1
.LBB0_3: ; %while.end
addi sp, r5, 0
Note that there's a j .LBB0_2, but no .LBB0_2 label defined. A quick search suggests that maybe I'm missing something in my instruction lowering, so I'll go poke there. Once I've remembered where it is (that was the bit I did years ago, and I haven't touched it since).
20241112
Notes from implementing the decoder:
Based on the CPU0 decoder, since it seems simpler than any of the other targets. The table of registers has to match the physical order of the register encodings. The various static DecodeXX are called by the auto-generated decoder, based on the values of the DecoderMethod fields in Mups16InstrInfo.td.
Interestingly, with the three I needed to add to get llvm-objdump to build, (DecodeIntRegsRegisterClass, DecodeSysRegsRegisterClass and DecodeBranchTarget), I get an error when decoding my main.o, but from the instruction printer, not decoder. For some reason the PrintMethod of an operand is called when printing disassembly, but not when outputting asm files, which is strange. I'll try just not defining my own PrintMethod, and use whatever the default is (I think I only had my own to try to match the customasm format anyway).
Hmm, on further investigation, something is very wrong with the output binary for the instructions, too. Looking at the contents of the main.o file with readelf, I see:
Section Headers: [Nr] Name Type Address Off Size ES Flg Lk Inf Al [ 0] NULL 00000000 000000 000000 00 0 0 0 [ 1] .strtab STRTAB 00000000 0000ec 000057 00 0 0 1 [ 2] .text PROGBITS 00000000 000034 000028 00 AX 0 0 4
So, the code should start at address 0x34 in the file, and continue for 0x28 bytes. Looking with hexdump, though, I see:
$ hexdump main.o -s 0x34 -n 0x28 0000034 0088 0000 0000 0070 0078 0088 0030 0060 0000044 0058 00b0 0030 0060 0058 0070 0078 0080 0000054 0030 0000 0060 0040
Allowing for the fact that hexdump shows the output in little-endian format, the first few instructions are:
0x88 0x00: 0b1000 1000 0000 0000 ; sw 0x00 0x00: 0b0000 0000 0000 0000 ; addi 0x00 0x00: 0b0000 0000 0000 0000 ; addi 0x70 0x00: 0b0111 0000 0000 0000 ; liu 0x78 0x00: 0b0111 1000 0000 0000 ; liu 0x88 0x00: 0b1000 1000 0000 0000 ; sw 0x30 0x00: 0b0011 0000 0000 0000 ; j
What's noticeable here is that we're only getting the opcode output - everything else is zero. Otherwise, this matches the instruction sequence from the assembly file:
sw -2($sp), $r5
addi $r5, $sp, -2
addi $sp, $sp, -4
liu $r1, %lo(print.msg)
lui $r1, %hi(print.msg)
lw $r1, 0($r1)
sw 0($r5), $r1
j .LBB0_1
Why is everything else zero?
Looking at the code in Mups16MCCodeEmitter, which I think is what's being called to generate the binary, I see a call to getBinaryCodeForInstr to generate the bits for the instruction. That seems to be doing the right thing, too: in build/lib/Target/Mups16/Mups16GenMCCodeEmitter.inc we have:
case MUPS::SW: {
// op: imm5
op = getMachineOpValue(MI, MI.getOperand(0), Fixups, STI);
op &= UINT64_C(31);
Value |= op;
// op: rs1
op = getMachineOpValue(MI, MI.getOperand(1), Fixups, STI);
op &= UINT64_C(7);
op <<= 8;
Value |= op;
// op: rs2
op = getMachineOpValue(MI, MI.getOperand(0), Fixups, STI);
op &= UINT64_C(7);
op <<= 5;
Value |= op;
break;
}
which seems reasonable. Time to get llc in the debugger, I think.
$ gdb --arg bin/llc -O0 -march=mups16 -relocation-model=static -filetype=obj main.bc -o main.o
Ugh, OK, that was obvious in retrospect. The case statement above calls getMachineOpValue, which is defined back in Mups16::MCCodeEmitter, which defines it as... return 0;. Whoops.
OK, with that fixed (hopefully? I just copied the Sparc one pretty much as-is) I get an assertion from llc:
llc: /home/ali/git/llvm-project/llvm/lib/MC/MCAsmBackend.cpp:102: virtual const llvm::MCFixupKindInfo& llvm::MCAsmBackend::getFixupKindInfo(llvm::MCFixupKind) const: Assertion `(size_t)Kind <= array_lengthof(Builtins) && "Unknown fixup kind"' failed. PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace. Stack dump: 0. Program arguments: bin/llc -O0 -march=mups16 -relocation-model=static -filetype=obj main.bc -o main.o #0 0x000055f10106f995 llvm::sys::PrintStackTrace(llvm::raw_ostream&) /home/ali/git/llvm-project/llvm/lib/Support/Unix/Signals.inc:564:22 #1 0x000055f10106fa35 PrintStackTraceSignalHandler(void*) /home/ali/git/llvm-project/llvm/lib/Support/Unix/Signals.inc:625:1 #2 0x000055f10106d6db llvm::sys::RunSignalHandlers() /home/ali/git/llvm-project/llvm/lib/Support/Signals.cpp:68:20 #3 0x000055f10106f2c4 SignalHandler(int) /home/ali/git/llvm-project/llvm/lib/Support/Unix/Signals.inc:406:1 #4 0x00007fbf3dad1520 (/lib/x86_64-linux-gnu/libc.so.6+0x42520) #5 0x00007fbf3db259fc pthread_kill ./nptl/./nptl/pthread_kill.c:44:76 #6 0x00007fbf3dad1476 raise ./signal/../sysdeps/posix/raise.c:27:6 #7 0x00007fbf3dab77f3 abort ./stdlib/./stdlib/abort.c:81:7 #8 0x00007fbf3dab771b ./intl/./intl/loadmsgcat.c:1177:9 #9 0x00007fbf3dac8e96 (/lib/x86_64-linux-gnu/libc.so.6+0x39e96) #10 0x000055f1007a808d llvm::MCAsmBackend::getFixupKindInfo(llvm::MCFixupKind) const /home/ali/git/llvm-project/llvm/lib/MC/MCAsmBackend.cpp:103:19 #11 0x000055f1007b86ee llvm::MCAssembler::evaluateFixup(llvm::MCAsmLayout const&, llvm::MCFixup const&, llvm::MCFragment const*, llvm::MCValue&, unsigned long&, bool&) const /home/ali/git/llvm-project/llvm/lib/MC/MCAssembler.cpp:221:70 #12 0x000055f1007bacd0 llvm::MCAssembler::handleFixup(llvm::MCAsmLayout const&, llvm::MCFragment&, llvm::MCFixup const&) /home/ali/git/llvm-project/llvm/lib/MC/MCAssembler.cpp:737:34 #13 0x000055f1007bb984 llvm::MCAssembler::layout(llvm::MCAsmLayout&) /home/ali/git/llvm-project/llvm/lib/MC/MCAssembler.cpp:878:17 #14 0x000055f1007bbb1d llvm::MCAssembler::Finish() /home/ali/git/llvm-project/llvm/lib/MC/MCAssembler.cpp:893:34 #15 0x000055f10081ccd0 llvm::MCObjectStreamer::finishImpl() /home/ali/git/llvm-project/llvm/lib/MC/MCObjectStreamer.cpp:781:1 #16 0x000055f1007fc265 llvm::MCELFStreamer::finishImpl() /home/ali/git/llvm-project/llvm/lib/MC/MCELFStreamer.cpp:678:1 #17 0x000055f10082b49b llvm::MCStreamer::Finish() /home/ali/git/llvm-project/llvm/lib/MC/MCStreamer.cpp:962:1 #18 0x000055f0ffd76b63 llvm::AsmPrinter::doFinalization(llvm::Module&) /home/ali/git/llvm-project/llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp:1752:14
Looks like I missed registering a fixup somewhere. llvm/lib/MC/MCAssembler.cpp:221 is
bool IsTarget = getBackendPtr()->getFixupKindInfo(Fixup.getKind()).Flags & MCFixupKindInfo::FKF_IsTarget;
which looks promising. I guess I probably need to override getFixupKindInfo in my assembler backend.
OK, with that done, the output looks different, but still wrong. It seems like the order of the operands isn't what I was expecting. Looking at the operands in the debugger in getBinaryCodeForInstr, we have:
(gdb) p MI.getOperand(0)
$5 = (const llvm::MCOperand &) @0x7fffffffd030: {Kind = llvm::MCOperand::kRegister, {RegVal = 4, ImmVal = 4, FPImmVal = 1.9762625833649862e-323, ExprVal = 0x4, InstVal = 0x4}}
(gdb) p MI.getOperand(1)
$6 = (const llvm::MCOperand &) @0x7fffffffd040: {Kind = llvm::MCOperand::kImmediate, {RegVal = 4294967294, ImmVal = -2, FPImmVal = -nan(0xffffffffffffe), ExprVal = 0xfffffffffffffffe, InstVal = 0xfffffffffffffffe}}
(gdb) p MI.getOperand(2)
$7 = (const llvm::MCOperand &) @0x7fffffffd050: {Kind = llvm::MCOperand::kRegister, {RegVal = 13, ImmVal = 13, FPImmVal = 6.4228533959362051e-323, ExprVal = 0xd, InstVal = 0xd}}
Considering the instruction is sw -2($sp), $r5, the only bit that makes sense is the immediate: sp is register 5, and register 13 is tmp. Time to remind myself how the operands are encoded in the first place.
Actually, while looking at the register encodings to find the indexes above I noticed something in Mups16RegisterInfo.td: we have r0 in IntRegs, even though it's not usable as a general register. It doesn't seem to be getting used in any generated code, though. Something else must be stopping it.
20241111
It looks like I fixed the wrong bit on Friday (well, it was going to need fixing anyway, but it wasn't what was actually causing the assertion error). Using the same message for a lot of different places when I first copied the files from the Sparc build was a bit short-sighted.
The current error is:
Invalid fixup kind UNREACHABLE executed at ... Stack dump: 0. Program arguments: bin/llc -O0 -march=mups16 -relocation-model=static -filetype=obj main.bc -o main.o ... #7 0x00007fa6b31bc7f3 abort ./stdlib/./stdlib/abort.c:81:7 #8 0x0000557802909942 bindingsErrorHandler(void*, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, bool) /home/.../git/llvm-project/llvm/lib/Support/ErrorHandling.cpp:219:55 #9 0x00005578013998f4 llvm::createMups16ELFObjectWriter(unsigned char) /home/.../git/llvm-project/llvm/lib/Target/Mups16/MCTargetDesc/Mups16ELFObjectWriter.cpp:56:50 #10 0x00005578021de057 (anonymous namespace)::ELFObjectWriter::recordRelocation(llvm::MCAssembler&, llvm::MCAsmLayout const&, llvm::MCFragment const*, llvm::MCFixup const&, llvm::MCValue, unsigned long&) /home/.../git/llvm-project/llvm/lib/MC/ELFObjectWriter.cpp:1475:51 #11 0x0000557802110b47 llvm::MCAssembler::handleFixup(llvm::MCAsmLayout const&, llvm::MCFragment&, llvm::MCFixup const&) /home/.../git/llvm-project/llvm/lib/MC/MCAssembler.cpp:760:35 #12 0x00005578021115ec llvm::MCAssembler::layout(llvm::MCAsmLayout&) /home/.../git/llvm-project/llvm/lib/MC/MCAssembler.cpp:878:17
The stack trace is a bit misleading, since it seems to show the assertion triggering in the createMups16ELFObjectWriter function (which does nothing but construct the writer, and has no assertions). Looking one up the call stack, however (in ELFObjectWriter::recordRelocation) shows
unsigned Type = TargetObjectWriter->getRelocType(Ctx, Target, Fixup, IsPCRel);
which makes more sense (getRelocType in the Mups16 object writer has an llvm_unreachable("Invalid fixup kind");).
So, I need to map my custom fixups to ELF types.
It looks like I have to add my custom relocation types to a new file called include/llvm/BinaryFormat/ELFRelocs/Mups16.def, and then modify include/llvm/BinaryFormat/ELF.h to include it, and similarly in lib/Object/ELF.cpp. Then I can modify Mups16ELFObjectWriter::getRelocType to convert my custom Mups16::fixup_mups16_lo8 and Mups16::fixup_mups16_hi8 to ELF::R_MUPS16_LO8 and ELF::R_MUPS16_HI8 respectively.
With that, I'm now getting a failure in Mups16AsmBackend::applyFixup for another unhandled fixup type, so back to that to see what needs adding. There seem to be a bunch of builtin relocations, so I might need to handle some of those.
Turned out for the simple test program I have I just needed to add handlers for FK_Data_1/2/4, and with that, I have a compiled ELF .o file!
$ bin/llvm-readelf -a main.o
ELF Header:
Magic: 7f 45 4c 46 01 01 01 ff 00 00 00 00 00 00 00 00
Class: ELF32
Data: 2's complement, little endian
Version: 1 (current)
OS/ABI: Standalone App
ABI Version: 0
Type: REL (Relocatable file)
Machine: MUPS/16 processor
Version: 0x1
Entry point address: 0x0
Start of program headers: 0 (bytes into file)
Start of section headers: 324 (bytes into file)
Flags: 0x0
Size of this header: 52 (bytes)
Size of program headers: 0 (bytes)
Number of program headers: 0
Size of section headers: 40 (bytes)
Number of section headers: 7
Section header string table index: 1
There are 7 section headers, starting at offset 0x144:
Section Headers:
[Nr] Name Type Address Off Size ES Flg Lk Inf Al
[ 0] NULL 00000000 000000 000000 00 0 0 0
[ 1] .strtab STRTAB 00000000 0000ec 000057 00 0 0 1
[ 2] .text PROGBITS 00000000 000034 000028 00 AX 0 0 4
[ 3] .rodata PROGBITS 00000000 00005c 000004 00 A 0 0 2
[ 4] .rela.rodata RELA 00000000 0000e0 00000c 0c 6 3 4
[ 5] .rodata.str1.1 PROGBITS 00000000 000060 00000e 01 AMS 0 0 1
[ 6] .symtab SYMTAB 00000000 000070 000070 10 1 5 4
Key to Flags:
W (write), A (alloc), X (execute), M (merge), S (strings), I (info),
L (link order), O (extra OS processing required), G (group), T (TLS),
C (compressed), x (unknown), o (OS specific), E (exclude),
p (processor specific)
Elf file type is REL (Relocatable file)
Entry point 0x0
There are 0 program headers, starting at offset 0
Program Headers:
Type Offset VirtAddr PhysAddr FileSiz MemSiz Flg Align
Section to Segment mapping:
Segment Sections...
None .strtab .text .rodata .rela.rodata .rodata.str1.1 .symtab
Relocation section '.rela.rodata' at offset 0xe0 contains 1 entries:
Offset Info Type Sym. Value Symbol's Name + Addend
00000002 00000402 R_MUPS16_16 00000000 .rodata.str1.1 + 0
Symbol table '.symtab' contains 7 entries:
Num: Value Size Type Bind Vis Ndx Name
0: 00000000 0 NOTYPE LOCAL DEFAULT UND
1: 00000000 0 FILE LOCAL DEFAULT ABS main.c
2: 00000000 14 OBJECT LOCAL DEFAULT 5 .str
3: 00000002 2 OBJECT LOCAL DEFAULT 3 print.msg
4: 00000000 0 SECTION LOCAL DEFAULT 5 .rodata.str1.1
5: 00000000 2 OBJECT GLOBAL DEFAULT 3 CONSOLE
6: 00000000 40 FUNC GLOBAL DEFAULT 2 print
There are no section groups in this file.
That's based on this trivial file:
char* const CONSOLE=(char* const)0xA00;
void print()
{
static const char* const msg = "Hello, world!";
const char* ptr = msg;
while (*ptr)
{
*CONSOLE = *ptr;
}
}
(note that the odd construction with msg and ptr being separate is just me trying to exercise different code paths in LLVM).
Next up, either getting disassembly working (so I can run llvm-objdump -d) or perhaps trying to get linking with lld working.
Update I decided to try lld first. Re-configuring to add it to the build:
cmake -DCMAKE_BUILD_TYPE=Debug -DLLVM_ENABLE_PROJECTS="clang;lld" -D LLVM_TARGETS_TO_BUILD="Mips" -D LLVM_EXPERIMENTAL_TARGETS_TO_BUILD="Mups16" -DLLVM_OPTIMIZED_TABLEGEN=On ../llvm
I probably don't need to keep building Mips, come to think of it...
Success! Adding a basic skeleton of Mups16 support to lld was surprisingly easy. I copied lld/ELF/Arch/Hexagon.cpp to lld/ELF/Arch/Mups16.cpp, removed almost everything except the constructor, getRelExpr and relocate functions, added a TargetInfo *elf::getMups16TargetInfo() function, added a forward declaration of that function to lld/ELF/Target.h, modified elf::getTarget in lld/ELF/Target.cpp to handle EM_MUPS16, and finally added my new Arch/Mups16.cpp file to lld/ELF/CMakeLists.txt. With that, I have a linker that does...something?
$ bin/ld.lld main.o
ld.lld: warning: cannot find entry symbol _start; defaulting to 0x101C8
$ ELF Header:
Magic: 7f 45 4c 46 01 01 01 ff 00 00 00 00 00 00 00 00
Class: ELF32
Data: 2's complement, little endian
Version: 1 (current)
OS/ABI: Standalone App
ABI Version: 0
Type: EXEC (Executable file)
Machine: MUPS/16 processor
Version: 0x1
Entry point address: 0x101C8
Start of program headers: 52 (bytes into file)
Start of section headers: 528 (bytes into file)
Flags: 0x0
Size of this header: 52 (bytes)
Size of program headers: 32 (bytes)
Number of program headers: 4
Size of section headers: 40 (bytes)
Number of section headers: 7
Section header string table index: 5
There are 7 section headers, starting at offset 0x210:
Section Headers:
[Nr] Name Type Address Off Size ES Flg Lk Inf Al
[ 0] NULL 00000000 000000 000000 00 0 0 0
[ 1] .rodata PROGBITS 000100b4 0000b4 000012 00 AMS 0 0 2
[ 2] .text PROGBITS 000101c8 0000c8 000028 00 AX 0 0 4
[ 3] .comment PROGBITS 00000000 0000f0 000067 01 MS 0 0 1
[ 4] .symtab SYMTAB 00000000 000158 000060 10 6 4 4
[ 5] .shstrtab STRTAB 00000000 0001b8 000032 00 0 0 1
[ 6] .strtab STRTAB 00000000 0001ea 000025 00 0 0 1
Key to Flags:
W (write), A (alloc), X (execute), M (merge), S (strings), I (info),
L (link order), O (extra OS processing required), G (group), T (TLS),
C (compressed), x (unknown), o (OS specific), E (exclude),
p (processor specific)
Elf file type is EXEC (Executable file)
Entry point 0x101c8
There are 4 program headers, starting at offset 52
Program Headers:
Type Offset VirtAddr PhysAddr FileSiz MemSiz Flg Align
PHDR 0x000034 0x00010034 0x00010034 0x00080 0x00080 R 0x4
LOAD 0x000000 0x00010000 0x00010000 0x000c6 0x000c6 R 0x100
LOAD 0x0000c8 0x000101c8 0x000101c8 0x00028 0x00028 R E 0x100
GNU_STACK 0x000000 0x00000000 0x00000000 0x00000 0x00000 RW 0x0
Section to Segment mapping:
Segment Sections...
00
01 .rodata
02 .text
03
None .comment .symtab .shstrtab .strtab
There are no relocations in this file.
Symbol table '.symtab' contains 6 entries:
Num: Value Size Type Bind Vis Ndx Name
0: 00000000 0 NOTYPE LOCAL DEFAULT UND
1: 00000000 0 FILE LOCAL DEFAULT ABS main.c
2: 000100b8 14 OBJECT LOCAL DEFAULT 1 .str
3: 000100b6 2 OBJECT LOCAL DEFAULT 1 print.msg
4: 000100b4 2 OBJECT GLOBAL DEFAULT 1 CONSOLE
5: 000101c8 40 FUNC GLOBAL DEFAULT 2 print
There are no section groups in this file.
I guess I really need to add disassembly support to be able to see what relocations have been applied, etc., but it's a good start.
Other notes:
- the default base address in lld seems to be hard-coded to 0x10000, which isn't ideal for us. I think we want to use something closer to 0x600 (leaving a few pages for interrupt vectors, basic kernel syscall-handling code, a small stack, and one page of memory-mapped devices).
- disassembly looks like it requires some manual coding, based on https://jonathan2251.github.io/lbd/elf.html#disas
20241109
OK, change of plan. It looks like I could get most of the way to getting customasm-compatible output by hacking at MCAsmStreamer and adding a target streamer for Mups16 that handles changeSection to use #bank instead, but there are enough hacks here to wonder if it might be better to try to get ELF output working. In theory, if I could do that then I could also use lld to link, and then either implement an ELF runtime loader, or (to start with) have a pre-process stage before uploading to ROM that rewrites the ELF file into the much simpler format I've already got implemented in my loader.
I'll stash my hacks to the ASM output in case I want to come back to them, and give ELF output a go.
First problem I can see is applying fixups. This isn't handled at all yet (Mups16AsmBackend::applyFixup contains just a call to llvmUnreachable). It looks like it's fairly easy to handle the only two cases we've got so far (%hi and %lo, which take the upper and lower bytes of the value respectively), but other implementations seem to have info on which bits in the output change encoded into the MCFixup object itself. Where is that info coming from? Somewhere in the tablegen? I guess for now I can hard-code it, since both these cases just replace the lower byte of the instruction word.
20241107
It doesn't seem that there's any easy way to swap in a custom replacement for MCAsmStreamer, so I've taken the ugly route of just modifying the existing one in-place. It's not like I'm ever going to use this branch for compiling anything else, anyway.
One other thing I need to modify is the way that registers and memory addresses are printed. They're currently outputting as
lw $r1, 0($r5)
whereas we want
lw r1, [0]r5
This is defined in Mups16/MCTargetDesc/Mups16InstPrinter.cpp, in printOperand and printMemOperand. Nice and easy to fix.
Next significant fix is to change the way sections are output to use #bank instead.
20241106
Nope, no dice. It looks like only a small subset of things can be overridden in the generated assembly output (via parameters in the Mups16MCAsmInfo class), but a lot is hard-coded to as syntax. For example, it seems to always output a .align or .alignp2 directive before a global symbol, whereas we want #align. The as syntax also assumes that alignment is specified in bytes, or powers-of-2 bytes, but we need bits, etc.
Maybe we can change some things via an override of MCTargetStreamer? Looks like that might let us fix section output via changeSection, which might let us output #bank text instead of .text, but I still can't see any way to make things like globals output in a customasm-friendly format.
It seems I'm not the only one to run into this. OK, it seems like I might have to just copy MCAsmStreamer.cpp completely, and define a new MCCustomasmStreamer that does what I want. Hopefully that should be easy enough to try out.
20241105
Notes on actually adding hi/lo output for globals.
First, I need to add custom types of machine codes for the relocations, so that we have something to emit in Mups16TargetLowering::makeAddress. This means a new MCTargetDesc/Mups16MCExpr.h file, with a Mups16MCExpr class in it. Also needed to add the fixup types to MCTargetDesc/Mups16FixupKinds.h
Mups16ISelLowering.cpp needs modifying so that
This got me a bit further. Now I'm getting errors trying to lower the machine instruction to MCInst, since that doesn't know about the lo and hi flags I just added. This is in Mups16MCInstLower.cpp.
Amazingly, with this added, we get something that looks vaguely like a compiled function, including the correct liu/lui pair for the message:
.text
.file "main.c"
.globl print ; -- Begin function print
.p2align 1
.type print,@function
print: ; @print
; %bb.0: ; %entry
sw -2($sp), $r5
addi $r5, $sp, -2
addi $sp, $sp, -4
liu $r1, %lo(print.msg)
lui $r1, %hi(print.msg)
lw $r1, 0($r1)
sw 0($r5), $r1
j .LBB0_1
.LBB0_1: ; %while.cond
; =>This Inner Loop Header: Depth=1
lw $r1, 0($r5)
lbu $r1, 0($r1)
bz $r1, .LBB0_3
j .LBB0_2
; %bb.2: ; %while.body
; in Loop: Header=BB0_1 Depth=1
lw $r1, 0($r5)
lbu $r1, 0($r1)
liu $r5, 0
lui $r5, 10
sb 0($r5), $r1
j .LBB0_1
.LBB0_3: ; %while.end
addi $sp, $r5, 0
lw $r5, -4($r5)
jr 0($ra)
.size print, .Lfunc_end0-print
; -- End function
.type CONSOLE,@object ; @CONSOLE
.section .rodata,"a",@progbits
.globl CONSOLE
.p2align 1
CONSOLE:
.short 2560
.size CONSOLE, 2
.type print.msg,@object ; @print.msg
.data
.p2align 1
print.msg:
.short .str
.size print.msg, 2
.type .str,@object ; @.str
.section .rodata.str1.1,"aMS",@progbits,1
.str:
.asciz "Hello, world!"
.size .str, 14
.ident "clang version 11.0.0 (git@github.com:pottsali/llvm-project.git 00b00b895627181004ba8934e102fb52d649acb4)"
.section ".note.GNU-stack","",@progbits
The output format is wrong for customasm (registers shouldn't be prefixed with $, and the section and data definitions are completely different), but it's a very good start. Hopefully most of the necessary changes here are localised to Mups16AsmPrinter.cpp.
20241101
Since the hardware is now actually working, back to trying to get something working in LLVM. I had a bit of a think about how to handle the assembler side of relocations, etc., and I realised I think I can do most of it inside customasm. We can't do proper relocations, as far as I know, but what I can do is modify the LLVM assembler output (TODO: which file?) so that names that need relocation are emitted as-is. In other words, if we have this source:
void foo()
{
char* msg = "Hello, world";
}
we'll end up with a global symbol for the string itself, and an assignment to a register. We need to output something along the lines of
#bank data
msg:
#d "Hello, world"
#bank text
foo:
; some preamble to save registers
liu r1, lo(msg)
lui r1, hi(msg)
where lo and hi are functions defined elsewhere in the customasm machine def. I think that should be enough, provided we're happy to assemble the whole project in one go, since customasm will be able to see and resolve all symbols. If we want proper multi-translation unit assembly then we need to either extend customasm or complete the assembler in LLVM.
20240711
No progress, but some reading on the train:
- https://lwn.net/Articles/276782/ - Ian Lance Taylor's (author of the Gold linker) series on how linkers work
- http://www.staroceans.org/e-book/LinkersAndLoaders.pdf - the classic Linkers and Loaders book. I used to have a copy of this book, but I think it got loaned to the library at work and never came back. Might have to order another copy.
20240709
OK, sometimes it's better to step back and not just keep hacking at things when you're tired. Thinking a bit more about the address problem, of course I can't do what I was trying to do (resolve addresses to constant loads at compile time). Things like global variables don't really have an address until they're fully linked, since we don't know exactly where in the .data segment they will end up (that depends on what other translation units define), or even necessarily what the address of the instruction that's referencing the variable is (again, that depends on how objects are linked together). It seems blindingly obvious in retrospect, but that's why both the MIPS and Sparc backends jump through hoops to emit custom assembler directives wrapping the address. For Sparc, what gets generated is something like:
sethi %hi(msg),%o1 or %o1,%lo(msg),%o1
where %hi and %lo are assembler operators that emit relocations for their parameter (of type R_SPARC_HI22 and R_SPARC_LO10 respectively). The linker then takes care of extracting the high 22 or low 10 bits of the final address once it's known. More info on relocation types.
So, I guess I need to do something similar, and I will need those custom node types after all. Hopefully it's a bit simpler now I think I understand why it's doing what it's doing.
Plan:
- add a new custom instruction selection DAG node (other targets call this Wrapper - I prefer something a little more descriptive, like Address. We'll see.)
- add a pair of type flags that can be associated with the address in Mups16MCExpr (which doesn't exist yet)
- implement a printImpl function in this new class that looks at the type of the operation and if it's one of the new ones, wraps the expression in either %hi() or %lo() (not sure about the naming, but these seem good enough). Presumably this will also require some support in the assembly parsing code, too
- change the address lowering functions to extract the address and convert it to a TargetXXAddress twice, once with a 'hi' flag, and once with a 'low' one.
- change the return of the address lowering functions to be an SDNode with the new MUPS16ISD::Address type
20240708
Progress, of a sort. I now have my test function compiling and producing assembly output. The output is wrong, but at least we're getting somewhere.
The main change is I started looking at the Sparc backend for inspiration, instead of the MIPS one. There are so many ways of expressing things in tablegen that even though they're doing largely the same thing with large immediates (splitting into low and high parts, and using multiple instructions to assemble the value into a register). The main difference between what they do and what Mups16 does is that in both Sparc and MIPS architectures, the 'load high' instruction (lui for MIPS, sethi for Sparc), zeros out the bottom part of the target register. This means they use something like (assuming I can remember my Sparc syntax):
sethi 0xA,%r5 // Load 0x0A into high part ori 0x1,%r5,%r5 // Load 0x01 into low part
That said, the basic idea should be the same. While I was digging, I thought I understood the tablegen matching a bit better, and perhaps I could actually do this without lots of wrappers and custom code, since a lot of that seemed to be about supporting various code models, PIC, etc., none of which I'm trying to support.
So, the next step was to simplify the loading of normal, non-address immediates, using this idea, to see if it was viable. Changing the immediate definition to
def : Pat<(i16 imm:$imm), (LUI (LIU (LO8 imm:$imm)), (HI8 imm:$imm))>;
seems to actually work for actual integer constants, without needing a pseudo-instruction at all.
So, I tried changing my Mups16TargetLowering::LowerGlobalAddress function back to just outputting DAG.getTargetGlobalAddress(...) directly (no ISD::Wrapper), and tried doing exactly the same for tglobaladdr. No joy, though:
def : Pat<(i16 tglobaladdr:$in), (LUI (LIU (LO8 tglobaladdr:$in)), (HI8 tglobaladdr:$in))>;
This doesn't seem to get matched. The generated IR just tries to use the address directly in a lw instruction, and dies producing assembly output. Last IR dump before failure:
# *** IR Dump After Live DEBUG_VALUE analysis ***: ... renamable $r1 = LW @print.msg, 0 :: (dereferenceable load 2 from @print.msg)
and the error:
.globl print ; -- Begin function print
.p2align 1
.type print,@function
print: ; @print
; %bb.0: ; %entry
sw -2($sp), $r5
addi $r5, $sp, -2
addi $sp, $sp, -4
lw $r1, 0($llc: /home/ali/git/llvm-project/llvm/include/llvm/MC/MCInst.h:65: unsigned int llvm::MCOperand::getReg() const: Assertion `isReg() && "This is not a register operand!"' failed.
with llvm::Mups16InstPrinter::printMemOperand further in the stack. I get exactly the same error if my pattern is removed, too, which means it's not being used.
Thinking about this a bit more, though, I wonder if I'm barking up the wrong tree. Can we actually know the value of a global at compile time? Surely that's deferred until the link stage? In which case this approach just can't work.
20240706
Following on from yesterday, some progress on globals. It seems that what we need is something that matches the global address and turns it into a LI/LUI pair. It looks like tablegen turns the global address into a tglobaladdress, so in theory it seems like we should be able to just define a pattern that matches i16 tglobaladdr:$addr and converts to LoadImm tglobaladdr:$addr (my pseudo-instruction that resolves to a LI/LUI pair). I didn't try that, since https://discourse.llvm.org/t/a-few-questions-from-a-newbie/12771 suggests that it will result in a cycle, so I followed what every other target does and added C++ code to match GlobalAddress and convert it to a Wrapper node in the DAG that contains the global address.
Added to Mups16TargetLowering::LowerOperation:
case ISD::GlobalAddress: return LowerGlobalAddress(Op, DAG);
and added a Mups16TargetLowering::LowerGlobalAddress that creates a Mups16ISD::Wrapper node wrapping the address.
This gets further now, failing with:
llc: /home/ali/git/llvm-project/llvm/include/llvm/CodeGen/MachineOperand.h:536: int64_t llvm::MachineOperand::getImm() const: Assertion `isImm() && "Wrong MachineOperand accessor"' failed.
Re-running with --debug-pass=Details to see where it's failing gives
[2024-07-06 09:44:32.146747150] 0x55a0b6de7220 Executing Pass 'Post-RA pseudo instruction expansion pass' on Function 'print'... 0x55a0b6dec930 Required Analyses: Machine Module Information llc: /home/ali/git/llvm-project/llvm/include/llvm/CodeGen/MachineOperand.h:536: int64_t llvm::MachineOperand::getImm() const: Assertion `isImm() && "Wrong MachineOperand accessor"' failed.
So, it's a lot further on. Running with --print-after-all, this is the last dump (and presumably what's getting fed into the failing pass):
# *** IR Dump After Prologue/Epilogue Insertion & Frame Finalization ***: # Machine code for function print: NoPHIs, TracksLiveness, NoVRegs, TiedOpsRewritten Frame Objects: fi#0: size=2, align=2, at location [SP-2] bb.0.entry: successors: %bb.1(0x80000000); %bb.1(100.00%) frame-setup SW $sp, -2, $r5 $r5 = frame-setup ADDI $sp, -2 $sp = frame-setup ADDI $sp, -4 renamable $r1 = LoadImm @print.msg renamable $r1 = LW killed renamable $r1, 0 :: (dereferenceable load 2 from @print.msg) SW $r5, 0, killed renamable $r1 :: (store 2 into %ir.ptr) J %bb.1 bb.1.while.cond: ; predecessors: %bb.0, %bb.2 successors: %bb.2, %bb.3 renamable $r1 = LW $r5, 0 :: (dereferenceable load 2 from %ir.ptr) renamable $r1 = LBU killed renamable $r1, 0 :: (load 1 from %ir.1) BZ killed renamable $r1, %bb.3 J %bb.2 bb.2.while.body: ; predecessors: %bb.1 successors: %bb.1(0x80000000); %bb.1(100.00%) renamable $r1 = LW $r5, 0 :: (dereferenceable load 2 from %ir.ptr) renamable $r1 = LBU killed renamable $r1, 0 :: (load 1 from %ir.3) renamable $r5 = LoadImm 2560 SB killed renamable $r1, killed renamable $r5, 0 :: (store 1 into `i8* inttoptr (i16 2560 to i8*)`) J %bb.1 bb.3.while.end: ; predecessors: %bb.1 $sp = ADDI $r5, 0 $r5 = LW $r5, -4 RetRA # End machine code for function print.
The pass name and error together suggest that the problem might be a pseudo-instruction that expects an immediate and isn't getting one. Perhaps it's that renamable $r1 = LoadImm @print.msg? Actually, looking more closely, that seems almost certain. The stack trace has
#11 0x00005586f645384d llvm::Mups16InstrInfo::expandLoadImm(llvm::MachineBasicBlock&, llvm::MachineInstrBundleIterator<llvm::MachineInstr, false>)
Catching this assertion failure in GDB, we have
(gdb) p *this
$1 = {OpKind = 10, SubReg_TargetFlags = 0, TiedTo = 15, IsDef = 1, IsImp = 1, IsDeadOrKill = 1, IsRenamable = 1, IsUndef = 1, IsInternalRead = 1, IsEarlyClobber = 1, IsDebug = 1, SmallContents = {
RegNo = 0, OffsetLo = 0}, ParentMI = 0x5555599ced00, Contents = {MBB = 0x5555599967f0, CFP = 0x5555599967f0, CI = 0x5555599967f0, ImmVal = 93825063806960, RegMask = 0x5555599967f0,
MD = 0x5555599967f0, Sym = 0x5555599967f0, CFIIndex = 1503225840, IntrinsicID = 1503225840, Pred = 1503225840, ShuffleMask = {Data = 0x5555599967f0, Length = 140733193388032}, Reg = {
Prev = 0x5555599967f0, Next = 0x7fff00000000}, OffsetedInfo = {Val = {Index = 1503225840, SymbolName = 0x5555599967f0 " \202\232YUU", GV = 0x5555599967f0, BA = 0x5555599967f0}, OffsetHi = 0}}}
(gdb)
and sure enough, OpKind of 10 means GlobalAddress, not Immediate:
(gdb) ptype MachineOperandType
type = enum llvm::MachineOperand::MachineOperandType : unsigned char {llvm::MachineOperand::MO_Register, llvm::MachineOperand::MO_Immediate, llvm::MachineOperand::MO_CImmediate,
llvm::MachineOperand::MO_FPImmediate, llvm::MachineOperand::MO_MachineBasicBlock, llvm::MachineOperand::MO_FrameIndex, llvm::MachineOperand::MO_ConstantPoolIndex,
llvm::MachineOperand::MO_TargetIndex, llvm::MachineOperand::MO_JumpTableIndex, llvm::MachineOperand::MO_ExternalSymbol,
// ----- here ----->
llvm::MachineOperand::MO_GlobalAddress,
// <----- here -----
llvm::MachineOperand::MO_BlockAddress, llvm::MachineOperand::MO_RegisterMask, llvm::MachineOperand::MO_RegisterLiveOut, llvm::MachineOperand::MO_Metadata, llvm::MachineOperand::MO_MCSymbol,
llvm::MachineOperand::MO_CFIIndex, llvm::MachineOperand::MO_IntrinsicID, llvm::MachineOperand::MO_Predicate, llvm::MachineOperand::MO_ShuffleMask, llvm::MachineOperand::MO_Last = 19}
We obviously need to convert the address to a value somehow. Alternatively, I wonder if this is because I'm trying to convert the address to a LoadImm instruction, which is a pseudo-instruction, and somehow this is off the beaten path?
Two options suggest themselves:
- Try explicitly handling address types in the Mups16InstrInfo::expandLoadImm function
- Try Mips-style explicitly building the address from high and low parts;
The first looks like less work, so I'll try that first.
Update: first option seems like a bit of a dead end. Firstly, no other target does this, which suggests maybe it's a bad idea. Secondly, there doesn't seem to be a way to extract the actual constant value out of a GlobalValue. The best I can see is getUniqueInteger(), but that only works if the type is exactly ConstantInt or a vector of them. Time to try the second option.
20240705
Getting back to this after a few years (!) while I wait for my new control unit boards to arrive, and making some quick notes on how to build LLVM, since I've forgotten everything.
Building
cd git git clone git@github.com:pottsali/llvm-project.git cd llvm-project gco feature/mups16
Configure:
mkdir build cd build cmake ../llvm
Build everything (could probably skip this stage and only build the Mups16 backend, but I can kick it off and let it build over lunch).
cmake --build . -j8
Linking failed first time around with OOM errors, so trying again without -j to re-do the link step one at a time. Looks like linking libLTO.so alone requires ~25GB RAM. Linking without -j worked.
Building with better options, including clang:
cmake -DCMAKE_BUILD_TYPE=Debug -DLLVM_ENABLE_PROJECTS="clang" -D LLVM_TARGETS_TO_BUILD="Mips" -D LLVM_EXPERIMENTAL_TARGETS_TO_BUILD="Mups16" -DLLVM_OPTIMIZED_TABLEGEN=On ../llvm cmake --build . -j8
This just builds the Mups16 and MIPS targets.
You can also just build llc for slightly faster iteration:
cmake --build . --target llc -j8
Running
With that built, I get a promising failure in the assembler when compiling
unsigned short* const CONSOLE=(unsigned short*const)0xA00;
void print()
{
*CONSOLE = 'H';
}
into object code:
$ ./bin/clang -target mups16 -c ~/git/cpu/cpp/target/hello_world/main.c /tmp/main-b5d338.s: Assembler messages: /tmp/main-b5d338.s:7: Error: no such instruction: `sw -2($sp),$fp' /tmp/main-b5d338.s:8: Error: no such instruction: `addi $fp,$sp,-2' /tmp/main-b5d338.s:9: Error: no such instruction: `addi $sp,$sp,-4' /tmp/main-b5d338.s:10: Error: no such instruction: `sw -2($fp),$r2' /tmp/main-b5d338.s:11: Error: no such instruction: `li $r1,72' /tmp/main-b5d338.s:12: Error: no such instruction: `liu $r2,0' /tmp/main-b5d338.s:13: Error: no such instruction: `lui $r2,10' /tmp/main-b5d338.s:14: Error: no such instruction: `sw 0($r2),$r1' /tmp/main-b5d338.s:15: Error: no such instruction: `lw $r2,-2($fp)' /tmp/main-b5d338.s:16: Error: no such instruction: `addi $sp,$fp,0' /tmp/main-b5d338.s:17: Error: no such instruction: `lw $fp,-4($fp)' /tmp/main-b5d338.s:18: Error: no such instruction: `jr 0($ra)' clang-11: error: assembler command failed with exit code 1 (use -v to see invocation)
Obviously I got a bit further 4 years ago than I remembered. Trying to expand this to a loop failed, though:
unsigned short* const CONSOLE=(unsigned short*const)0xA00;
void print()
{
static const char* msg = "Hello, world!";
const char* ptr = msg;
while (*ptr)
{
*CONSOLE = *ptr;
}
}
$ ./bin/clang -target mups16 -c ~/git/cpu/cpp/target/hello_world/main.c -emit-llvm
.text
.file "main.c"
LLVM ERROR: Cannot select: t1: i16 = GlobalAddress<i8** @print.msg> 0
In function: print
PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace.
Stack dump:
0. Program arguments: bin/llc -O0 -march=mups16 -relocation-model=static -filetype=asm main.bc -o -
1. Running pass 'Function Pass Manager' on module 'main.bc'.
2. Running pass 'Mups16 DAG->DAG Pattern Instruction Selection' on function '@print'
...
Debugging
Build IR with clang first:
$ ./bin/clang -target mups16 -c ~/git/cpu/cpp/target/hello_world/main.c -emit-llvm
Then compile with llc:
bin/llc -O0 -march=mups16 -relocation-model=static -filetype=asm main.bc -o -debug --debug-only=isel
For some reason running with -debug doesn't actually show any debugging. I'm not sure why, but it seems that --debug-only=isel gives a bit more of what I want:
===== Instruction selection begins: %bb.0 'entry' ISEL: Starting selection on root node: t8: ch = br t6, BasicBlock:ch<while.cond 0x56124dbca610> ISEL: Starting pattern match Morphed node: t8: ch = J BasicBlock:ch<while.cond 0x56124dbca610>, t6 ISEL: Match complete! ISEL: Starting selection on root node: t6: ch = store<(store 2 into %ir.ptr)> t4:1, t4, FrameIndex:i16<0>, undef:i16 ISEL: Starting pattern match Initial Opcode index to 82 Skipped scope entry (due to false predicate) at index 92, continuing at 108 Morphed node: t6: ch = SW<Mem:(store 2 into %ir.ptr)> TargetFrameIndex:i16<0>, TargetConstant:i16<0>, t4, t4:1 ISEL: Match complete! ISEL: Starting selection on root node: t4: i16,ch = load<(dereferenceable load 2 from @print.msg)> t0, GlobalAddress:i16<i8** @print.msg> 0, undef:i16 ISEL: Starting pattern match Initial Opcode index to 4 Skipped scope entry (due to false predicate) at index 13, continuing at 29 Skipped scope entry (due to false predicate) at index 30, continuing at 46 Morphed node: t4: i16,ch = LW<Mem:(dereferenceable load 2 from @print.msg)> GlobalAddress:i16<i8** @print.msg> 0, TargetConstant:i16<0>, t0 ISEL: Match complete! ISEL: Starting selection on root node: t7: ch = BasicBlock<while.cond 0x56124dbca610> ISEL: Starting selection on root node: t1: i16 = GlobalAddress<i8** @print.msg> 0 ISEL: Starting pattern match Initial Opcode index to 0 Match failed at index 0 LLVM ERROR: Cannot select: t1: i16 = GlobalAddress<i8** @print.msg> 0
Still not sure why, but at least there's something to go on.
OK, after a couple of hours of digging, I think this is what is going on. In Mups16ISelLowering.cpp, we have
setOperationAction(ISD::GlobalAddress, MVT::i16, Custom);
This indicates that we'll handle the lowering of global addresses ourselves, in the Mups16TargetLowering::LowerOperation function. However, this is the current contents of that function:
SDValue Mups16TargetLowering::LowerOperation(SDValue Op, SelectionDAG &DAG) const
{
switch (Op.getOpcode())
{
}
return {};
}
Not only does this not handle anything, but it doesn't even fail. Changing this to
SDValue Mups16TargetLowering::LowerOperation(SDValue Op, SelectionDAG &DAG) const
{
switch (Op.getOpcode())
{
default:
llvm_unreachable("unimplemented operand");
}
return {};
}
confirms that we're failing here:
$ bin/llc -O0 -march=mups16 -relocation-model=static -filetype=asm main.bc -o -debug --debug-only=all unimplemented operand UNREACHABLE executed at /home/ali/git/llvm-project/llvm/lib/Target/Mups16/Mups16ISelLowering.cpp:327!
I don't think we actually need to do anything special with global addresses. We don't have a global data pointer to use via offsets or anything nice like that, so maybe I can just change the Custom to Expand and let it just load literals?
Update: nope. Same error we started with. Looking at all the other targets, they all use Custom, so I guess I'll have to write some code. Not today.
20201010
Spent a while trying to work out how to load large (>255) constants into registers. The instruction sequence that needs to be generated is simple. For 0x4280 we need:
liu $r1, 0x80 lui $r1, 0x42
I thought this would be an easy pattern to express, but couldn't find a way to do it in tablegen.
I looked at what other RISC-y backends do, and they all work in roughly the same way, with a large immediate load expanding to something equivalent to
lui $r1, 0x42 ori $r1, $r1, 0x80
This works because they're using 32-bit instructions and can encode a halfword in the immediate field of their ori instruction. I can't, with only 5 bits available.
In order to load a register in two cycles I have to use two single-register instructions, as they're the only ones with 8-bit immediates, and my lui instruction has to have slightly unusual semantics, in that it leaves the low 8 bits untouched (most instruction sets that have a lui set the low 8 bits to 0). This works nicely, but the problem now is that the lui instruction effectively uses its register operand as both a source and destination (what it does is effectively reg = (reg & 0xff) | (imm << 8) in a single instruction). I couldn't find a way to express this cleanly in the .td file.
My first attempt was a basic pattern:
def : Pat<(i16 imm:$imm), (LUI (LIU (LO8 imm:$imm)), (HI8 imm:$imm))>;
where LO8 and HI8 are just SDNodeXForms that extract the low and high byte respectively. This doesn't work, as the lui node isn't defined to take an input register. I played around with a few variations on this, before deciding that I'd just use a pseudo-instruction and expand it in code.
def LoadImm: MupsPseudo<(outs IntReg:$rdd), (ins imm16:$imm),
[(set IntReg:$rdd, imm:$imm)]>;
and expanded in Mups16InstrInfo.cpp as
void Mups16InstrInfo::expandLoadImm(MachineBasicBlock &MBB, MachineBasicBlock::iterator I) const
{
auto& reg = I->getOperand(0);
BuildMI(MBB, I, I->getDebugLoc(), get(MUPS::LIU))
.addReg(reg.getReg())
.addImm(I->getOperand(1).getImm() & 0xff);
BuildMI(MBB, I, I->getDebugLoc(), get(MUPS::LUI))
.addReg(reg.getReg())
.addImm((I->getOperand(1).getImm() >> 8) & 0xff);
}
which seems to work, with the intermediate DAG node %3:intregs = LoadImm 256 expanding to
liu $r2, 0 lui $r2, 1
Next up: try loops again.
20201008
No progress, worked on soldering up the memory board instead
20201007
Spent a couple of frustrating evenings trying to work out why LLVM was failing to match byte loads:
ISEL: Starting selection on root node: t17: i16,ch = load<(load 1 from %ir.0), anyext from i8> t6, t7, undef:i16 ISEL: Starting pattern match Initial Opcode index to 4 Skipped scope entry (due to false predicate) at index 13, continuing at 29 Skipped scope entry (due to false predicate) at index 30, continuing at 46 Skipped scope entry (due to false predicate) at index 47, continuing at 61 Match failed at index 11 LLVM ERROR: Cannot select: t17: i16,ch = load<(load 1 from %ir.0), anyext from i8> t6, t7, undef:i16
I have a pair of byte-loading instructions defined:
def LB : InstMupsID1<10, (outs IntReg:$rdd), (ins memsrc:$src), │Included from /home/ali/git/llvm-project/llvm/lib/Target/Mups16/Mups16.td:19:
"lb $rdd, $src", │/home/ali/git/llvm-project/llvm/lib/Target/Mups16/Mups16InstrInfo.td:334:58: error: expected ')' in dag init
[(set IntReg:$rdd, (sextloadi8 addr:$src))]>; │def : Pat<(i16 imm:$imm), (LUI (LIU (LO8 imm:$imm)), HI8 imm:$imm)>;
def LBU : InstMupsID1<11, (outs IntReg:$rdd), (ins memsrc:$src), │[7/27] Building Mups16GenInstrInfo.inc...
"lbu $rdd, $src", │FAILED: lib/Target/Mups16/Mups16GenInstrInfo.inc
[(set IntReg:$rdd, (zextloadi8 addr:$src))]>;
i.e. there's one for sign-extending loads (sextloadi8) and one for zero-extended loads (zextloadi8).
Wasted a lot of time thinking it was something to do with the instruction having two register arguments instead of reg+imm, but that was just me getting confused by the t6 argument, which I think is just the ch result of the previous instruction, passed in as part of instruction chaining.
Next suspicion was that it was because the load doesn't have a frame index, and that this would somehow screw up matching with the addr operand (defined as def addr: ComplexPattern<iPTR, 2, "selectAddr", [frameindex], []>;), checking the C++ selectAddr function, etc.). No joy here.
Finally came across this article about the LLVM backend which had a very useful hint to look in the generated matching table in build/lib/Target/Mups16/Mups16GenDAGISel.inc, to see which predicates were actually failing. Lo and behold, it's pretty obvious:
static const unsigned char MatcherTable[] = {
/* 0*/ OPC_SwitchOpcode /*9 cases */, 75, TARGET_VAL(ISD::LOAD),// ->79
/* 4*/ OPC_RecordMemRef,
/* 5*/ OPC_RecordNode, // #0 = 'ld' chained node
/* 6*/ OPC_RecordChild1, // #1 = $src
/* 7*/ OPC_CheckPredicate, 0, // Predicate_unindexedload
/* 9*/ OPC_CheckType, MVT::i16,
/* 11*/ OPC_Scope, 16, /*->29*/ // 4 children in Scope
/* 13*/ OPC_CheckPredicate, 1, // Predicate_sextload
/* 15*/ OPC_CheckPredicate, 2, // Predicate_sextloadi8
/* 17*/ OPC_CheckComplexPat, /*CP*/0, /*#*/1, // selectAddr:$src #2 #3
/* 20*/ OPC_EmitMergeInputChains1_0,
/* 21*/ OPC_MorphNodeTo1, TARGET_VAL(MUPS::LB), 0|OPFL_Chain|OPFL_MemRefs,
MVT::i16, 2/*#Ops*/, 2, 3,
// Src: (ld:{ *:[i16] } addr:{ *:[iPTR] }:$src)<<P:Predicate_unindexedload>><<P:Predicate_sextload>><<P:Predicate_sextloadi8>> - Complexity = 13
// Dst: (LB:{ *:[i16] } addr:{ *:[i16] }:$src)
/* 29*/ /*Scope*/ 16, /*->46*/
/* 30*/ OPC_CheckPredicate, 3, // Predicate_zextload
/* 32*/ OPC_CheckPredicate, 2, // Predicate_zextloadi8
/* 34*/ OPC_CheckComplexPat, /*CP*/0, /*#*/1, // selectAddr:$src #2 #3
/* 37*/ OPC_EmitMergeInputChains1_0,
/* 38*/ OPC_MorphNodeTo1, TARGET_VAL(MUPS::LBU), 0|OPFL_Chain|OPFL_MemRefs,
MVT::i16, 2/*#Ops*/, 2, 3,
// Src: (ld:{ *:[i16] } addr:{ *:[iPTR] }:$src)<<P:Predicate_unindexedload>><<P:Predicate_zextload>><<P:Predicate_zextloadi8>> - Complexity = 13
// Dst: (LBU:{ *:[i16] } addr:{ *:[i16] }:$src)
/* 46*/ /*Scope*/ 14, /*->61*/
/* 47*/ OPC_CheckPredicate, 4, // Predicate_load
/* 49*/ OPC_CheckComplexPat, /*CP*/0, /*#*/1, // selectAddr:$src #2 #3
/* 52*/ OPC_EmitMergeInputChains1_0,
/* 53*/ OPC_MorphNodeTo1, TARGET_VAL(MUPS::LW), 0|OPFL_Chain|OPFL_MemRefs,
MVT::i16, 2/*#Ops*/, 2, 3,
// Src: (ld:{ *:[i16] } addr:{ *:[iPTR] }:$src)<<P:Predicate_unindexedload>><<P:Predicate_load>> - Complexity = 13
// Dst: (LW:{ *:[i16] } addr:{ *:[i16] }:$src)
/* 61*/ 0, /*End of Scope*/
Matching to the Skipped scope entry (due to false predicate) at index XX messages this gives a pretty clear picture:
/* 13*/ OPC_CheckPredicate, 1, // Predicate_sextload
/* 30*/ OPC_CheckPredicate, 3, // Predicate_zextload
/* 47*/ OPC_CheckPredicate, 4, // Predicate_load
Further down in the file, we have the predicate-matching code:
case 1: {
// Predicate_sextload
SDNode *N = Node;
(void)N;
if (cast<LoadSDNode>(N)->getExtensionType() != ISD::SEXTLOAD) return false;
return true;
}
// skipping 2...
}
case 3: {
// Predicate_zextload
SDNode *N = Node;
(void)N;
if (cast<LoadSDNode>(N)->getExtensionType() != ISD::ZEXTLOAD) return false;
return true;
}
case 4: {
// Predicate_load
SDNode *N = Node;
(void)N;
if (cast<LoadSDNode>(N)->getExtensionType() != ISD::NON_EXTLOAD) return false;
return true;
}
So, these will only match if the extension type is one of SEXTLOAD, ZEXTLOAD or NON_EXTLOAD, but apparently not EXTLOAD (which is what anyext maps to in C++). I naively assumed that anyext would happily match either sign- or zero-extended loads, but apparently it doesn't.
Borrowing from the Lanai backend again I added a standalone pattern for anyext loads that maps to the LBU instruction (I don't think we generally want sign extension unless it's specifically requested):
// Pattern for anyext loads, since they don't seem to match either of the above def : Pat<(extloadi8 addr:$src), (i16 (LBU addr:$src))>;
and with that the load matched:
ISEL: Starting selection on root node: t17: i16,ch = load<(load 1 from %ir.0), anyext from i8> t6, t7, undef:i16 ISEL: Starting pattern match Initial Opcode index to 4 Skipped scope entry (due to false predicate) at index 13, continuing at 29 Skipped scope entry (due to false predicate) at index 30, continuing at 46 Skipped scope entry (due to false predicate) at index 47, continuing at 61 Morphed node: t17: i16,ch = LBU<Mem:(load 1 from %ir.0)> t7, TargetConstant:i16<0>, t6 ISEL: Match complete!
Next failure is one I knew was coming: loading immediates >= 256 into a register, since it can't be done in a single instruction. Hopefully another simple pattern can fix that.
20201004
Implemented eliminateFrameIndex, and got my first successful compile of a function! Admittedly it was the empty print function, but still.
Spent a while tracking down this error:
Use of %1 does not have a corresponding definition on every path: 48r %1:intregs = LI %1:intregs LLVM ERROR: Use not jointly dominated by defs.
This should have been moving the constant 42 into $r1 prior to returning it, but somehow the DAG
t0: ch = EntryToken
t2: i16,ch = CopyFromReg t0, Register:i16 %0
t6: ch = store<(store 2 into %ir.str.addr)> t0, t2, FrameIndex:i16<0>, undef:i16
t9: ch,glue = CopyToReg t6, Register:i16 $r1, Constant:i16<42>
t10: ch = Mups16ISD::Ret t9, Register:i16 $r1, t9:1
was getting transformed into
t0: ch = EntryToken
t7: i16 = LI t7
t2: i16,ch = CopyFromReg t0, Register:i16 %0
t6: ch = SW<Mem:(store 2 into %ir.str.addr)> t2, TargetFrameIndex:i16<0>, TargetConstant:i16<0>, t0
t9: ch,glue = CopyToReg t6, Register:i16 $r1, t7
t10: ch = RetRA Register:i16 $r1, t9, t9:1
The load of Constant:i16<42> had disappeared, replaced by t7: i16 = LI t7. Turned out to be just that the li instruction was defined as
def LI : InstMupsIID<13, (outs IntReg:$rdd), (ins imm8:$imm8),
"li $rdd, $imm8",
[(set IntReg:$rdd, i16:$imm8)]>;
Changing the pattern in the last line to [(set IntReg:$rdd, imm8:$imm8)]>; fixed it.
Further minor problem: sw instructions that are generated from a pattern (rather than the ones created explicitly in the lowering C++ functions) had the operands round the wrong way, leading to an assertion printing the instructions:
Assertion `Disp.isImm() && "Expected immediate in displacement field"' failed.
Easily fixed by swapping the operands in the instruction definition, to match the sw <dest_addr>, <source_reg> layout:
// Incorrect def SW : InstMupsI2<17, (IntReg:$rs2, ins memdst:$dst), ... // Correct def SW : InstMupsI2<17, (ins memdst:$dst, IntReg:$rs2), ...
20201003
Progress. Decided to try compiling a completely empty function, just to try to make some progress on the structure. My function now looks like:
static char* const TERM_ADDR=(char*)0x100
void print(const char* str_)
{
}
With this, I immediately get an assertion that I put in my Mups16FrameLowering::emitPrologue function, which is good. Decided to use register 5 (the old PC) as a frame pointer for now, just for simplicity.
Other piece of good news is I found a much simpler example to copy from: the Google Lanai backend. That appears to be a very straightforward 32-bit RISC CPU, and the backend code is very concise. I've adapted its emitPrologue and emitEpilogue functions, and now llc is hanging, which is good news. I think that means I need to implement eliminateFrameIndex, judging from a few comments I've seen in code (mainly in the CPU0 backend, I think). Makes a pleasant change to have a hang instead of a crash.
20201002
No new code today. Spent a couple of hours trying to understand how the prologue/epilogue generation works in LLVM. Still somewhat confused. I'm wondering how this works at all if you don't have a frame register (every example I can see does have one). Maybe I'll have to sacrifice one of my precious general-purpose registers as a frame register. Might turn out to be really useful that I redesigned the program counter as a dedicated circuit and freed up register 6.
Got distracted reading about liveness analysis, after seeing lots of calls to .live_in() and .kill() in various places in the register spilling/popping.
20201001
After much fruitless banging of head against wall, I decided to debug this the old-fashioned way. No, not with printf, the other way: by deleting half the code from the print() function I'm compiling and seeing if my problem goes away. Hopefully I should be able to work out if it's the branch instructions or the load/store ones that're causing the problems.
Removing the branches, so the function is just a straightforward
static char* const TERM_ADDR=(char*)0x100
void print(const char* str_)
{
*TERM_ADDR = *str_;
}
got me a little further, to a segfault in LowerReturn, which wasn't surprising since I hadn't implemented that function yet. Implemented that based mostly on CPU0 and RISCV examples. Only wrinkle was what to do with the ret instruction, which isn't natively supported. Ended up doing something like CPU0, and adding a ret pseudo-instruction (Mups16ISD::Ret) that's expanded in a post-register-allocation pass by the Mups16InstrInfo::expandPostRAPseudo function into
BuildMI(MBB, I, I->getDebugLoc(), get(MUPS::JR)).addReg(MUPS::RA);
There's probably a simpler way, but this seems to work. Next problem is missing function prologue/epilogue code.
20200923
I'm wondering if the assertion from last night is something to do with LLVM not knowing that my load instructions are actually loads (there's an offhand comment in the llvm CodeGenerator doc that says "We don’t automatically infer flags like isStore/isLoad yet"). Most other backends seem to have implemented the isLoadFromStackSlot function in the XXXInstrInfo.cpp file. I'll try adding that. Straws firmly clutched.
Update: nope.
20200922
Decided to take a break from beating my head against the br_cc problem, and look at load/store instead. Partly just for a change, but also in case it turns out that llvm is trying to match the whole fragment I mentioned yesterday, in which case it will need the load pattern anyway.
First stab at this:
def memsrc : Operand<i16> {
let PrintMethod = "printMemOperand";
let MIOperandInfo = (ops IntReg, imm5);
let ParserMatchClass = MemAsmOperand;
}
def LB : InstMupsID1<10, (outs IntReg:$rdd), (ins memsrc:$src),
"lb $rdd, $src",
[(set IntReg:$rdd, (sextloadi8 memsrc:$src))]>;
This doesn't work. It appears that memsrc isn't a valid leaf in the dag:
Unknown leaf kind: memsrc:{ *:[i16] }:$src
Attempt two was to use iPTR for the type:
[(set IntReg:$rdd, (sextloadi8 iPTR:$src))]>;
which gives a more interesting error:
LB: (LB:{ *:[i16] } iPTR:{ *:[i16] }:$src)
Included from /xx/git/llvm-project/llvm/lib/Target/Mups16/Mups16.td:19:
/home/ali/git/llvm-project/llvm/lib/Target/Mups16/Mups16InstrInfo.td:118:1: error: In LB: Instruction 'LB' expects more than the provided 1 operands!
Presumably this is because the instruction is defined to take memsrc as its input operand, which is a compound operand that takes an IntReg, imm5 pair to allow for the constant offset from the source register. Maybe I need to add a custom pattern that can match this?
Later:
Success! Not only on memory loads, but on the br_cc problem from yesterday.
Memory first: adding a ComplexPattern and some code to match the base+offset seems to have worked. In the Mups16InstrInfo.td file:
// Leaf pattern for matching memory addresses
def addr: ComplexPattern<iPTR, 2, "selectAddr", [frameindex]>;
// ...
def LB : InstMupsID1<10, (outs IntReg:$rdd), (ins memsrc:$src),
"lb $rdd, $src",
[(set IntReg:$rdd, (sextloadi8 addr:$src))]>;
with a matching Mups16DAGToDAGISel::selectAddr(SDValue Addr, SDValue &Base, SDValue &Offset) worked a treat. This function is called whenever an address is matched, and can set the Base and Offset ref arguments.
The br_cc fix was embarrassingly simple: just change the definitions in the legalisation DAG in Mups16ISelLowering.cpp to expand br_cc, and make brcond legal:
setOperationAction(ISD::BR_CC, MVT::i8, Promote); setOperationAction(ISD::BR_CC, MVT::i16, Expand); setOperationAction(ISD::BRCOND, MVT::Other, Legal);
With store patterns added for sw and sb, the selection now gets as far as the second load before failing:
===== Instruction selection begins: %bb.0 'entry' ISEL: Starting selection on root node: t23: ch = br t26, BasicBlock:ch<if.then 0x7fffed961eb0> ISEL: Starting pattern match Skipped scope entry (due to false predicate) at index 2, continuing at 63 Skipped scope entry (due to false predicate) at index 64, continuing at 111 Skipped scope entry (due to false predicate) at index 112, continuing at 161 Skipped scope entry (due to false predicate) at index 162, continuing at 175 Morphed node: t23: ch = J BasicBlock:ch<if.then 0x7fffed961eb0>, t26 ISEL: Match complete! ISEL: Starting selection on root node: t26: ch = brcond t29, t31, BasicBlock:ch<if.end 0x7fffed961f88> ISEL: Starting pattern match Skipped scope entry (due to false predicate) at index 2, continuing at 63 Skipped scope entry (due to false predicate) at index 64, continuing at 111 Morphed node: t26: ch = BZ t36, BasicBlock:ch<if.end 0x7fffed961f88>, t29 ISEL: Match complete! ISEL: Starting selection on root node: t36: i16,ch = load<(dereferenceable load 1 from %ir.b), zext from i8> t29, FrameIndex:i16<1>, undef:i16 ISEL: Starting pattern match Skipped scope entry (due to false predicate) at index 14, continuing at 30 Creating constant: t38: i16 = TargetConstant<0> Morphed node: t36: i16,ch = LBU<Mem:(dereferenceable load 1 from %ir.b)> TargetFrameIndex:i16<1>, TargetConstant:i16<0>, t29 ISEL: Match complete! ISEL: Starting selection on root node: t29: ch = store<(store 1 into %ir.b), trunc to i8> t28:1, t28, FrameIndex:i16<1>, undef:i16 ISEL: Starting pattern match Skipped scope entry (due to false predicate) at index 2, continuing at 63 Morphed node: t29: ch = SB<Mem:(store 1 into %ir.b)> TargetFrameIndex:i16<1>, TargetConstant:i16<0>, t28, t28:1 ISEL: Match complete! ISEL: Starting selection on root node: t28: i16,ch = load<(load 1 from %ir.0), anyext from i8> t10, t7, undef:i16 ISEL: Starting pattern match Skipped scope entry (due to false predicate) at index 14, continuing at 30 Skipped scope entry (due to false predicate) at index 31, continuing at 47 Skipped scope entry (due to false predicate) at index 48, continuing at 62 Match failed at index 12 Continuing at 63 Match failed at index 64 Continuing at 111 Match failed at index 112 Continuing at 161 Match failed at index 162 Continuing at 175 Match failed at index 176 Continuing at 193 llc: /home/ali/git/llvm-project/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp:900: bool llvm::SelectionDAG::RemoveNodeFromCSEMaps(llvm::SDNode*): Assertion `N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!"' failed.
I've no idea what's going on here. Tomorrow's problem.
20200921
Some progress with llvm, and lots of frustration. Good news is that I got my Mups16 instruction selected from an llvm one:
===== Instruction selection begins: %bb.0 'entry' ISEL: Starting selection on root node: t23: ch = br t37, BasicBlock:ch<if.then 0x7fffc3fd73b0> ISEL: Starting pattern match Morphed node: t23: ch = J BasicBlock:ch<if.then 0x7fffc3fd73b0>, t37 ISEL: Match complete!
Unfortunately, the next instruction is a conditional branch, and I can't for the life of me work out how to match that:
ISEL: Starting selection on root node: t37: ch = br_cc t29, seteq:ch, t36, Constant:i16<0>, BasicBlock:ch<if.end 0x7fffc3fd7488>
ISEL: Starting pattern match
Initial Opcode index to 0
Match failed at index 0
LLVM ERROR: Cannot select: t37: ch = br_cc t29, seteq:ch, t36, Constant:i16<0>, BasicBlock:ch<if.end 0x7fffc3fd7488>
t36: i16,ch = load<(dereferenceable load 1 from %ir.b), zext from i8> t29, FrameIndex:i16<1>, undef:i16
t12: i16 = FrameIndex<1>
t5: i16 = undef
t27: i16 = Constant<0>
In function: print
I've tried what seemed obvious:
def BZ : InstMupsII1<20, (ins IntReg:$rs1, brtarget:$offset),
"bz $rs1, $offset",
[(brcond (i16 (seteq IntReg:$rs1, 0)), bb:$offset)]>;
and made sure that the unsupported comparisons are expanded in the legalisation DAG:
setOperationAction(ISD::SETCC, MVT::i8, Promote); // Valid condcode actions (which comparisons are natively supported by the CPU) setCondCodeAction(ISD::SETOLE, MVT::i16, Expand); setCondCodeAction(ISD::SETOGE, MVT::i16, Expand); setCondCodeAction(ISD::SETOGT, MVT::i16, Expand); setCondCodeAction(ISD::SETULE, MVT::i16, Expand); setCondCodeAction(ISD::SETUGE, MVT::i16, Expand); setCondCodeAction(ISD::SETUGT, MVT::i16, Expand);
which should, if I understand it right, mean that comparisons like A <= B get transformed into !(B < A), which is supported by the slt instruction.
What's a little frustrating is that I can't see any references to a br_cc LLVM instruction (ISD::BR_CC exists in the code, but you can't pattern match on br_cc in the TD files), and most other examples I can see online show conditional branches represented as brcond.
I'm wondering now if it's actually a problem with the conditional branch at all now. Perhaps LLVM is trying to match the entire block, and the error is coming from the fact that I haven't added patterns for load yet?
20200920
Managed to get past the sentinel assertion in llc