This is an archive of the discontinued LLVM Phabricator instance.

[GlobalISel][IRTranslator] Change switch table translation to generate jump tables and range checks.
ClosedPublic

Authored by aemerson on Jun 11 2019, 2:39 PM.

Details

Summary

This change makes use of the newly refactored SwitchLoweringUtils code from SelectionDAG to in order to generate jump tables and range checks where appropriate.

Much of this code is ported from SDAG with some modifications. We generate G_JUMP_TABLE and G_BRJT instructions when JT opportunities are found. This means that targets which previously relied on the naive one MBB per case stmt translation will now start falling back until they add support for the new opcodes.

For range checks, we don't generate any previously unused operations. This just recognizes contiguous ranges of case values and generates a single block per range. Single case value blocks are just a special case of ranges so we get that support almost for free.

There are still some optimizations missing that I haven't ported over, and bit-tests are also unimplemented. This patch series is already complex enough.

Actual arm64 support for selection of jump tables is coming in a later patch.

Diff Detail

Event Timeline

aemerson created this revision.Jun 11 2019, 2:39 PM
paquette added inline comments.Jun 17 2019, 9:52 AM
llvm/include/llvm/CodeGen/GlobalISel/IRTranslator.h
526

I think you can capitalize irt etc. in here

Also, can irt ever be null (I doubt it, but still)? Should there be an assert?

llvm/lib/CodeGen/GlobalISel/IRTranslator.cpp
440

for (auto &I : ... )?

441

Is *I.getCaseSuccessor() always guaranteed to not be nullptr?

444–446

Could this use the above IRTranslator::getEdgeProbability function? Then you don't have to check BPI here.

452

This (and the remainder of this function) seems like it could be factored out into a clusterAdjacentCases helper function.

506

to appease the llvm style gods, this should be nextBlock

535

Is it worth pulling JTH.SValue out into a variable?

661

llvm::stable_sort?

670–679

I feel like this is somewhat unintuitive. Is there a way to simplify this using some STL magic?

702

This switch makes this function rather large. Would it make sense to factor it out into a helper function?

704

Debug output would be nice here

740–743

remove braces to appease llvm style gods

788–789

brace formatting seems wonky here

2069

Just curious, why 16?

2181

capital i to appease the llvm style gods, but I'll pretend I didn't see this ;)

aemerson marked 13 inline comments as done.Jun 17 2019, 1:13 PM
aemerson added inline comments.
llvm/include/llvm/CodeGen/GlobalISel/IRTranslator.h
526

It's a deliberate choice for me. I'm not sure if it's correct but there's some precedent for this around the codebase. I prefer in cases where we have identically named member variables and parameters to just use lower case for the very short lived parameters.

It won't be null since it's used in one place, I'll put an assert anyway.

llvm/lib/CodeGen/GlobalISel/IRTranslator.cpp
440

Ok.

441

Yes I think so.

444–446

I don't think it computes exactly the same thing, SI.getNumCases() + 1 can't be replaced because the successors of SI's parent BB is not necessarily the same as the successors of the switchinst itself.

452

Not sure what you mean here, the clustering is already done in this call to sortAndRangeify(). The rest of the function is unrelated.

506

Ok.

535

Ok.

661

I don't think the Low values can overlap, so we don't need stable sort here.

704

Ok.

740–743

Ok.

788–789

Because switch cases aren't indented relative to the switch.

2069

Pointer storage is cheap, and set growth is expensive, just a rough guess.

2181

Ok.

aemerson updated this revision to Diff 205226.Jun 17 2019, 5:58 PM
paquette added inline comments.Jun 20 2019, 4:06 PM
llvm/lib/CodeGen/GlobalISel/IRTranslator.cpp
411

Just return after this to eliminate the else?

462–464

clang-format for braces

506–511

Does this function have to exist at all? Can you just use getNextNode?

549–565

I think this can probably be simplified to reduce nesting, since the if case is much longer than the else if here.

E.g.

if (JTH.OmitRangeCheck && JT.MBB != nextBlock(SwitchBB)) {
    MIB.buildBr(*JT.MBB);
    return true;
}

auto Cst...
return true;
584–586

clang-format

760

I think we should check the function attributes for optnone here as well.

aemerson updated this revision to Diff 205929.Jun 20 2019, 5:28 PM
aemerson marked an inline comment as done.

Addressed comments.

This revision is now accepted and ready to land.Jun 21 2019, 9:03 AM
This revision was automatically updated to reflect the committed changes.

@aemerson Hi, I committed rL364124 to fix the link error on -DBUILD_SHARED_LIBS=on builds, but I am not sure if the dependency should be added. Can you take a look?

@aemerson Hi, I committed rL364124 to fix the link error on -DBUILD_SHARED_LIBS=on builds, but I am not sure if the dependency should be added. Can you take a look?

Thanks, I think it might be able to remove that dependency from this commit but until I do that fix looks fine.

Amara