32 bit shift instructions are using missing libgcc symbols

[seanmkauffman]

LSHR and SHL with i32 operands are producing calls to libgcc symbols which don't exist. LSHR produces a call to __lshrsi3 and SHL produces a call to __ashlsi3.

The following programs demonstrate the problem.

LSHR:

define i32 @run(i32 %a, i32 %b) #0 {
  %1 = lshr i32 %a, %b
  ret i32 %1
}
define i32 @main() #1 {
  %1 = call i32 @run(i32 31, i32 31)
  ret i32 %1
}

SHL:

define i32 @run(i32 %a, i32 %b) #0 {
  %1 = shl nsw i32 %a, %b
  ret i32 %1
}
define i32 @main() #1 {
  %1 = call i32 @run(i32 31, i32 31)
  ret i32 %1
}

[dylanmckay]

Nonmenclature note: LLVM has a concept of legal and illegal types. Legal types are those that are properly supported by the architecture (as in, can be held in a single register), whereas illegal types are those that can not (i.e. u64 is illegal on a 32-bit processor).

It's a little bit sad that AVR does not have variable bit-shifts (the only shift instructions operate one bit at a time, so you must use n instructions to shift n bits.

Due to this, we tell LLVM to handle bit shifts manually here.

As we do not handle 32-bit shifts manually, LLVM uses the default legalisation action - "expand". This will either expand it into two 16-bit shifts, or a call to a runtime library function which will do the shifts itself.

LLVM chooses to expand into two 16-bit shifts if u16 is an illegal type - why expand from u32 to u16 if both are illegal anyway. If u16 is legal, it will emit a runtime library call.

The problem is that LLVM assumes that the largest legal ("properly supported") type, is the type of the largest register. This presents a problem - it is an 8-bit microcontroller, but it has three (which only one can really be used) 16-bit registers, so u16 is legal, even though very few operations can be performed on them.

This is currently a big problem we are facing - LLVM assuming that the largest register type is legal, even though it is only legal for a few operations.

---

The underlying problem is that we have no control over how LLVM interprets the "expand" legalization action. It makes decisions based on the largest legal type, which for AVR, should really not be legal.

It would be possible to add custom handling code for u32 here, but this would leave u64 and u128 broken as well.

We have an entire file (~1400 lines of code) of expansion code for "fake" instructions we define in this file. This works around the fact that LLVM determines u16 to be legal, so instead of fixing LLVM, we pretend it really is legal and, going along with it and manually expand dozens of 16-bit instructions into 8-bit in a custom pass. This is extremely messy as it duplicates logic that LLVM has itself.

[dylanmckay]

damn this problem sucks

[shepmaster]

damn this problem sucks

Is there any hope for splitting up the concept of "pointer size" and "legal size"?

[dylanmckay]

I started a big refactor of LegalizeDAG.cpp once, got a lot of the work done. The main issue is the code can be really hard to trace, I think the isLegalType has about 5 indirections?

There is some hope, some time just needs to be invested.

[dylanmckay]

It looks like libgcc always uses efficient codegen for 32-bit shifts and only bothers lowering 64-bit shifts to libcalls. This explains why there is no 32-bit libcall in the runtime library.

[dylanmckay]

Interestingly, the __lshrsi3 libcall does not even exist in compiler-rt, and yet LLVM is still generating it.