Page MenuHomePhabricator

[SimplifyCFG] Enable switch to lookup table for more types.
ClosedPublic

Authored by craig.topper on Jul 31 2021, 4:50 PM.

Details

Summary

This transform has been restricted to legal types since
https://reviews.llvm.org/rG65df808f6254617b9eee931d00e95d900610b660
in 2012.

This is particularly restrictive on RISCV64 which only has i64
as a legal integer type. i32 is a very common type in code
generated from C, but we won't form a lookup table with it.
This also effects other common types like i8/i16 types on ARM,
AArch64, RISCV, etc.

This patch proposes to allow power of 2 types larger than 8 bit, if
they will fit in the largest legal integer type in DataLayout.
These types are common in C code so generally well handled in
the backends.

We could probably do this for other types like i24 and rely on
alignment and padding to allow the backend to use a single wider
load. This isn't my main concern right now and it will need more
tests.

We could also allow larger types up to some limit and let the
backend split into multiple loads, but we need to define that
limit. It's also not my main concern right now.

Diff Detail

Event Timeline

craig.topper created this revision.Jul 31 2021, 4:50 PM
craig.topper requested review of this revision.Jul 31 2021, 4:50 PM
Herald added a project: Restricted Project. · View Herald TranscriptJul 31 2021, 4:50 PM
Herald added a subscriber: MaskRay. · View Herald Transcript

Can we just revert rL168970?
What exactly was the rdar://12779436 about, can anyone look it up?

Matt added a subscriber: Matt.Aug 2 2021, 1:15 PM
fhahn added a comment.Aug 3 2021, 6:43 AM

Can we just revert rL168970?
What exactly was the rdar://12779436 about, can anyone look it up?

It's an Apple-internal bug report of a crash that was the reason for the revert. As long as the test that has been added in rL168970 passes that should be fine. I can also verify against the original C++ source.

Can we just revert rL168970?
What exactly was the rdar://12779436 about, can anyone look it up?

It's an Apple-internal bug report of a crash that was the reason for the revert. As long as the test that has been added in rL168970 passes that should be fine. I can also verify against the original C++ source.

Note that most people don't have access to any such internal bugtrackers.
What was the crast?

fhahn added a comment.Aug 3 2021, 6:57 AM

Can we just revert rL168970?
What exactly was the rdar://12779436 about, can anyone look it up?

It's an Apple-internal bug report of a crash that was the reason for the revert. As long as the test that has been added in rL168970 passes that should be fine. I can also verify against the original C++ source.

Note that most people don't have access to any such internal bugtrackers.
What was the crast?

I guess in this case, the reference is a historical artifact. I assume the test added to llvm/test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll in the commit should be sufficient to guard against the reported issue.

Can we just revert rL168970?
What exactly was the rdar://12779436 about, can anyone look it up?

It's an Apple-internal bug report of a crash that was the reason for the revert. As long as the test that has been added in rL168970 passes that should be fine. I can also verify against the original C++ source.

Note that most people don't have access to any such internal bugtrackers.
What was the crast?

I guess in this case, the reference is a historical artifact. I assume the test added to llvm/test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll in the commit should be sufficient to guard against the reported issue.

I'm not sure i follow. Is it a profitability check, or is it guarding against some crash somewhere in backend?
We can nicely lower i96 load, https://godbolt.org/z/scP8sj5jf, and i suspect it will still be more performant than the switch lowering.

fhahn added a comment.Aug 3 2021, 7:02 AM

Can we just revert rL168970?
What exactly was the rdar://12779436 about, can anyone look it up?

It's an Apple-internal bug report of a crash that was the reason for the revert. As long as the test that has been added in rL168970 passes that should be fine. I can also verify against the original C++ source.

Note that most people don't have access to any such internal bugtrackers.
What was the crast?

I guess in this case, the reference is a historical artifact. I assume the test added to llvm/test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll in the commit should be sufficient to guard against the reported issue.

The crash was in the AArch64 backend due to the emitted table using un-emittable constants. I don't really have any further insight and cannot say if it is still an issue. I can check a patch against the original source to check if it crashes.

Can we just revert rL168970?
What exactly was the rdar://12779436 about, can anyone look it up?

It's an Apple-internal bug report of a crash that was the reason for the revert. As long as the test that has been added in rL168970 passes that should be fine. I can also verify against the original C++ source.

Note that most people don't have access to any such internal bugtrackers.
What was the crast?

I guess in this case, the reference is a historical artifact. I assume the test added to llvm/test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll in the commit should be sufficient to guard against the reported issue.

The crash was in the AArch64 backend due to the emitted table using un-emittable constants. I don't really have any further insight and cannot say if it is still an issue. I can check a patch against the original source to check if it crashes.

Aha. But that was not a reasonable fix. It would still crash just the same should anyone produce such an IR,
the fix should have been in the backend, and indeed, it no longer crashes, for a long while now: https://godbolt.org/z/34nf7q5xz
So back to my original question: can we just essentially revert that commit?

I was trying to determine what else the current check is protecting like vectors or floating point. It looks like ValidLookupTableConstant may largely filter out vectors. Though the recursion in ValidLookupTableConstant for ConstantExpr seems like it might be incomplete. It only visits operand 0. Though there are probably no operations that takes a scalar as a first operand and returns a vector result.

If the type is very large and the constants are small we will generate a very large table which could be a lot worse than the original switch. Of course we could use a smaller type for the lookup table and the extend the constants in such a case, but that's additional work I can't sign up for. So I think it is still reasonable to have some kind of limit in place here.

Could you please add a FIXME somewhere around ShouldBuildLookupTable in the code summarizing that support for larger-than-largest-legal-integer types can likely be added?

Add another TODO.

lebedev.ri accepted this revision.Aug 3 2021, 12:53 PM

LGTM, this looks very limited-enough.

This revision is now accepted and ready to land.Aug 3 2021, 12:53 PM