Branch relaxation at assembler level (RISCV)

Hi all,

I'm trying to implement the same branch relaxation mechanism implemented
in CodeGen in the MC layer of RISCV.

beqz t1, L1

=>

bnez t1, L2

j L1

That's because LLVM does not apply the CodeGen optimizations when
compiling directly from assembly code.

What I'd like to do would be to add a pass that does that on the MC
instructions or at least to find a way to implement this relaxation in
the MC assembler.

Any suggestions on where/how to do it? Or any existing fixes?

Many thanks,

Paolo Savini

Hi all,

I'm trying to implement the same branch relaxation mechanism implemented
in CodeGen in the MC layer of RISCV.

beqz t1, L1

=>

bnez t1, L2

j L1

That's because LLVM does not apply the CodeGen optimizations when
compiling directly from assembly code.

What I'd like to do would be to add a pass that does that on the MC
instructions or at least to find a way to implement this relaxation in
the MC assembler.

Any suggestions on where/how to do it? Or any existing fixes?

Many thanks,

Paolo Savini

The RISCV assembler already has code for similar transforms; see RISCVAsmBackend::mayNeedRelaxation and RISCVAsmBackend::relaxInstruction. The only tricky bit is that the relaxation interface doesn't expect one instruction to be relaxed to two instructions... probably not too hard to change, though, if necessary.

That said, I'm a little skeptical this is actually a good idea; the more "smart" the assembler is, the harder it becomes to understand what it's doing. No other in-tree target does this sort of transform.

-Eli

Thank you Eli for the quick reply,

Well, I had seen the RISCVAsmBackend and yes, I agree it wouldn't be a
good idea to make it handle this niche issue.
We thought that we might work at the MC emission level and see what we
can do there.

Thanks
Paolo

Note that it is extremely important that RISC-V relaxations only ever make the code shorter, never longer.

If the instructions stay the same size, it can not be permitted to replace one instruction with two.

Changing a 32 bit instruction to two 16 bit instructions could be ok, but I’m struggling to think of an example when that would be beneficial.

We're talking about assembler "relaxations" (basically, the assembler trying to resolve an ambiguous branch instruction), not RISCV linker relaxations.

-Eli

Hi,

This discussion caught my eye because we are also looking at a very similar problem on PowerPC.
We have a situation where we want to align a given instruction to a 64 byte boundary. If it’s not already aligned we just add nops until it is aligned (We plan to do this in a custom PPCStreamer). If the branch and the target of that branch are far enough away adding a few nops in-between may actually overflow the 14 bits we have to represent the offset in the branch instruction and in that case we have to do something special and replace the branch with something else that, once again, is not a single instruction.

If mayNeedRelaxation and relaxInstruction are not the way to do this is there any other better way?

Thanks,
Stefan

That's normally something you'd handle in code generation. There's a target-independent pass in lib/CodeGen/BranchRelaxation.cpp, but it looks like PowerPC uses its own implementation in lib/Target/PowerPC/PPCBranchSelector.cpp . Either way, the key is to ensure that the size of each instruction is computed conservatively (so it should treat your "aligned" instruction as a 64-byte instruction, since there will be 60 bytes of padding in the worst case).

-Eli