Page MenuHomePhabricator

[SimplifyCFG] Run ReduceSwitchRange unconditionally, generalize
ClosedPublic

Authored by shawnl on Apr 25 2019, 4:16 PM.

Details

Reviewers
jmolloy
Summary

This is patch 4 is a series beginning with D61150

Rather than gating on "isSwitchDense" (resulting in necessesarily
sparse lookup tables even when they were generated), always run
this quite cheap transform.

This transform is useful not just for generating tables.
LowerSwitch also wants this: read LowerSwitch.cpp:257.

Be careful to not generate worse code, by introducing a
SubThreshold heuristic.

Instead of just sorting by signed, generalize the finding of the
best base.

And now that it is run unconditionally, do not replicate its
functionality in SwitchToLookupTable (which could use a Sub
when having a hole is smaller, hence the SubThreshold
heuristic located in a single place).
This simplifies SwitchToLookupTable, and fixes
some ugly corner cases due to the use of signed numbers,
such as a table containing i16 32768 and 32769, of which
32769 would be interpreted as -32768, and now the code thinks
the table is size 65536.

(We still use unconditional subtraction when building a single-register mask,
but I think this whole block should go when the more general sparse
map is added, which doesn't leave empty holes in the table.)

And the reason test4 and test5 did not trigger was documented wrong:
it was because they were not considered sufficiently "dense".

Diff Detail

Event Timeline

shawnl created this revision.Apr 25 2019, 4:16 PM
Herald added a project: Restricted Project. · View Herald TranscriptApr 25 2019, 4:16 PM
shawnl edited the summary of this revision. (Show Details)Apr 25 2019, 4:18 PM
jmolloy requested changes to this revision.Apr 26 2019, 1:08 AM

Thanks! Much easier to review this time.

lib/Transforms/Utils/SimplifyCFG.cpp
5514

no -> so

5525

Can you mention why we're doing this? A naive reader may wonder why this might possibly return any value other than Values.back() - Values.front() + 1 (of course, a counterexample is the signed zero-crossing case mentioned in the diffbase).

5529

Please use capitals for induction variables, calculate the end value once, and use preincrement as per style guide:

for (unsigned I = 1, E = Values.size(); I != E; ++I) {
5537

Is this heuristic correct? From my understanding, SubThreshold is the number of table entries elided. BestDistance is the wrap distance.

But the number of table entries elided isn't the wrap distance, it's the Base that you calculate below (because by default we start counting from zero).

Am I wrong? I think this should be if (Base > SubThreshold ...)

5538

And if I'm right above, this whole clause goes away and the entire if becomes:

if (Values[BestIndex] >= SubThreshold)
test/Transforms/SimplifyCFG/X86/disable-lookup-table.ll
55–57

Can you please name the CreateSub() you added so it's not just a temporary? like "switch.reducerange" or something?

test/Transforms/SimplifyCFG/X86/switch-table-bug.ll
12–13

I particularly like this simplification :)

This revision now requires changes to proceed.Apr 26 2019, 1:08 AM
shawnl updated this revision to Diff 197007.Apr 28 2019, 1:24 AM

Thanks for the changes, just two comments!

lib/Transforms/Utils/SimplifyCFG.cpp
5445

This line is too complex. Please don't nest conditionals into function calls; use an extra line to set up the constant.

5530

Space after both ;'s.

The best way to do this is use git-clang-format, which I've recommended before.

jmolloy requested changes to this revision.Apr 30 2019, 5:32 AM
This revision now requires changes to proceed.Apr 30 2019, 5:32 AM
shawnl updated this revision to Diff 197332.Apr 30 2019, 8:02 AM

the old shifting code could create a invalid shl 32/64

jmolloy accepted this revision.Apr 30 2019, 8:48 AM

LGTM, thanks for making the changes!

This revision is now accepted and ready to land.Apr 30 2019, 8:48 AM
lebedev.ri added inline comments.
lib/Transforms/Utils/SimplifyCFG.cpp
5529

This wasn't done

shawnl marked an inline comment as done.Apr 30 2019, 1:53 PM
shawnl added inline comments.
lib/Transforms/Utils/SimplifyCFG.cpp
5529

Oh I switched to using E in most places and I will use it here. I also ran git-clang-format.

shawnl closed this revision.May 26 2019, 7:46 AM

applied 361727