[CodeGen] Unsigned Offsets and isLegalAddressingMode in LoopStrengthReduction

Hi all,

I’ve been working on a 6502 backend in my off hours (yeah, I know). I’ve gotten surprisingly good results so far, but I’ve run into a bit of a pickle.

Amongst its many difficulties, the 6502 has 16-bit pointers and 8-bit offsets in its indexed addressing modes. These offsets are unsigned, so there’s no way to go backwards from the fixed 16-bit base pointer. If you reach the end of a 256-byte page, you go forward to the next page; you don’t wrap around. Thus, the index math is equivalent to zext-ing the 8-bit offset, not sext-ing it.

Unfortunately, when I tried to compile my first real loop, the ScalarEvolution pass in its infinite wisdom chose to run the induction variable from -33 to 0. This is great, since it ends with an ICmp 0, which is faster on my target. All good. Except I can’t actually find an efficient way to index via a negative number.

isLegalAddressingMode seems too coarse to make the real distinction between whether a given SCEV can be used as a BaseReg or not for the 6502. In particular, there’s no way to differentiate between Formula with isKnownPositive (if that function works the way I think it does) SCEV and those that may be negative (or known negative). The latter would require a soft 16-bit addition, which is rather expensive (unless there’s some better way to do it that I’m missing). I’m considering adding an alternative that actually passes in the SCEV and using it in key places in LoopStrengthReduction.


Is this target particularly weird in having unsigned-only offsets of <pointer width?
If not, where can I look for inspiration?

Is extending isLegalAddressingMode (in my fork) the right place to address this?
Is there a better mechanism already in LLVM somewhere? On the right/wrong track?

Daniel Thornburgh