Page MenuHomePhabricator

[RISCV] Basic jump table lowering
ClosedPublic

Authored by nand on Nov 25 2020, 6:01 AM.

Details

Summary

This patch enables jump table lowering in the RISC-V backend.

In addition to the test case included, the new lowering was
tested by compiling the OCaml runtime and running it under qemu.

Diff Detail

Event Timeline

nand created this revision.Nov 25 2020, 6:01 AM
nand requested review of this revision.Nov 25 2020, 6:01 AM
lenary added inline comments.Nov 26 2020, 4:13 AM
llvm/test/CodeGen/RISCV/jumptable.ll
1–9

I *think* these tests need to be expanded to cover both the low code model (currently covered), and the medium code model (which uses auipc). I've added some RUN lines for you, if you take the suggestion, you'll need to re-run update_llc_test_checks.py

nand updated this revision to Diff 307833.Nov 26 2020, 4:53 AM

Expanded test to cover 32-bit/64-bit variants with small and medium code models

lenary added inline comments.Nov 26 2020, 4:57 AM
llvm/test/CodeGen/RISCV/jumptable.ll
10–11

update_llc_test_checks.py doesn't remove unused prefixes, so you can delete the RV32I-* lines :)

jrtc27 requested changes to this revision.Nov 26 2020, 4:57 AM
jrtc27 added inline comments.
llvm/test/CodeGen/RISCV/jumptable.ll
3

codemodel-lowering.ll uses -SMALL and -MEDIUM; please be consistent with that.

10–11

This whole set of check lines needs to go (and not sure how the formatting got messed up...).

This revision now requires changes to proceed.Nov 26 2020, 4:57 AM
jrtc27 added inline comments.Nov 26 2020, 5:01 AM
llvm/lib/Target/RISCV/RISCVExpandPseudoInsts.cpp
126 ↗(On Diff #307833)

Why is it that expandAuipcInstPair needs to handle this specially but there's no corresponding logic for medlow's plain LUI/ADDI?

nand updated this revision to Diff 307835.Nov 26 2020, 5:04 AM

consistent run lines

nand added inline comments.Nov 26 2020, 5:07 AM
llvm/lib/Target/RISCV/RISCVExpandPseudoInsts.cpp
126 ↗(On Diff #307833)

Based on my understanding, addDisp seems to be a generic method that produces an operand with an arbitrary offset from some reference, however it doesn't seem like offsets into jump tables are supported. Since the offset is always 0, the jump table index is handled separately. I might be wrong though.

lenary added inline comments.Nov 26 2020, 5:09 AM
llvm/lib/Target/RISCV/RISCVISelLowering.cpp
371

Let's make sure this doesn't have a major code size impact. I'm not sure the threshold GCC uses, something like 3 IIRC?

The problem for code size is that the sequence to hold the jump table and the calculate the jump index is longer than a chain of ifs, if there aren't too many entries.

jrtc27 added inline comments.Nov 26 2020, 5:09 AM
llvm/lib/Target/RISCV/RISCVExpandPseudoInsts.cpp
126 ↗(On Diff #307833)

Right, then surely the correct fix is to add an MO_JumpTableIndex case to addDisp that calls addJumpTableIndex?

@nand thank you for this patch, it's been something missing from the RISC-V backend for a while, which is why you're getting so much feedback so quickly.

nand added inline comments.Nov 26 2020, 5:14 AM
llvm/lib/Target/RISCV/RISCVExpandPseudoInsts.cpp
126 ↗(On Diff #307833)

addDisp is common to all architectures, so I am reluctant to change it. Furthermore, addDisp takes an offset operand and the only sensible value for jump tables is 0. I think handling jump tables separately is nicer than asserting in addDisp that off is 0.

llvm/lib/Target/RISCV/RISCVISelLowering.cpp
371

I am using this backend to compile OCaml in a weird way. I could try to build a bunch of OCaml binaries with various thresholds, report the results and maybe we can make a decision for a reasonable default?

nand marked an inline comment as not done.Nov 26 2020, 7:14 AM
nand added inline comments.
llvm/lib/Target/RISCV/RISCVISelLowering.cpp
371

I now realised that I cannot change this threshold in my code generator, so I cannot provide any measurements.

Based on my understanding of the code, unless the target explicitly overwrites it, the -min-jump-table-entries
argument is used, which defaults to 4. If that is reasonable, maybe there is no point in hardcoding a default value?

jrtc27 added inline comments.Nov 26 2020, 7:17 AM
llvm/lib/Target/RISCV/RISCVExpandPseudoInsts.cpp
126 ↗(On Diff #307833)

I disagree. It's a generic method meant to take any operand one would reasonably want to use. We already use it for the very-similar constant pool index. You also don't need to assert off is 0; that's not done for CPIs, and if you pass in non-zero then you get what you asked for, ie Symbol.getIndex() + off. The only reason it's not currently supported in addDisp is that nobody has yet needed it, as other backends tend to just duplicate lowering for the different hooks. Just mirror the CPI code for what is basically a special case of it.

jrtc27 added inline comments.Nov 26 2020, 7:19 AM
llvm/lib/Target/RISCV/RISCVExpandPseudoInsts.cpp
126 ↗(On Diff #307833)

Note that this has been done in the past for RISC-V too; see https://reviews.llvm.org/D60136 (needed for https://reviews.llvm.org/D54143).

jrtc27 added inline comments.Nov 26 2020, 7:26 AM
llvm/lib/Target/RISCV/RISCVExpandPseudoInsts.cpp
126 ↗(On Diff #307833)

I see, CreateJTI doesn't have an Offset. Well, IMO it should for completeness, but yes you probably want to assert the offset is 0 in addDisp then.

nand updated this revision to Diff 307881.Nov 26 2020, 8:42 AM
nand marked an inline comment as not done.

moved logic into addDisp

You still appear to have the old patch that doesn't change addDisp.

nand updated this revision to Diff 307885.Nov 26 2020, 8:50 AM

applied the changes on the correct checkout of the llvm repository this time...

This seems fine to me now other than the outstanding discussion about code size.

nand added a comment.Nov 28 2020, 7:49 AM

Is there anything I could do to test the impact on code size? As I mentioned previously, in my setting I cannot easily turn the use of jump tables off. Are there any binaries that are relatively easy to cross compile and are of interest?

There was a previous patch which had some feedback about thresholds: https://reviews.llvm.org/D48430

nand updated this revision to Diff 310932.Dec 10 2020, 9:15 AM

updated the minimum number of jump table entries

nand updated this revision to Diff 311058.Dec 10 2020, 4:19 PM

fixed test and added below/above threshold cases

lenary accepted this revision.Dec 11 2020, 2:46 AM

Cool. I think we can tweak the threshold later, but this should start us in a reasonable place. Thanks for your patience, I'm happy for this to land.

The previous discussion pointed out that GCC's default threshold on RISC-V was 5 (thanks @kito-cheng for the link). We match that here, so that should avoid the worst of the performance regressions.

jrtc27 accepted this revision.Dec 21 2020, 5:12 PM

I agree with @lenary, I think this is fine to land (with the whitespace fix :)) and if it turns out the threshold is too low then we'll soon find out and can adjust accordingly (but I imagine not, 5 feels like a sensible default). Or if it's too high!

llvm/test/CodeGen/RISCV/jumptable.ll
166

Nit: unwanted extra blank line

This revision is now accepted and ready to land.Dec 21 2020, 5:12 PM
nand updated this revision to Diff 313332.Dec 22 2020, 7:03 AM

removed newline

This revision was landed with ongoing or failed builds.Dec 22 2020, 7:43 AM
This revision was automatically updated to reflect the committed changes.