This is an archive of the discontinued LLVM Phabricator instance.

[X86] Sort the static memory folding tables by reg opcode. Remove the reg->mem DenseMaps in favor of binary search.
ClosedPublic

Authored by craig.topper on Jun 23 2018, 11:02 PM.

Details

Summary

With the static tables sorted we can binary search them directly for reg->mem lookups. This removes 6 DenseMaps that had to be created when X86InstrInfo is constructed.

We still have one Mem->Reg DenseMap for the reverse direction. This is created just as before by walking the reg->mem arrays to populate it.

Diff Detail

Event Timeline

craig.topper created this revision.Jun 23 2018, 11:02 PM
RKSimon accepted this revision.Jun 25 2018, 4:39 AM

Makes sense to me

This revision is now accepted and ready to land.Jun 25 2018, 4:39 AM
This revision was automatically updated to reflect the committed changes.
greened added inline comments.
llvm/trunk/lib/Target/X86/X86InstrInfo.cpp
123 ↗(On Diff #152723)

Whoa. So developers are expected to keep these tables sorted, with no comment to that effect and no convenient numeric indication of the opcode values? This seems like a recipe for mistakes to me. Instead of asserting that the tables are sorted below, why not just sort them? Is it too expensive?

craig.topper added inline comments.Jun 25 2018, 12:37 PM
llvm/trunk/lib/Target/X86/X86InstrInfo.cpp
123 ↗(On Diff #152723)

Sorting them would require bringing them into a heap allocated vector to sort. Which is a little more costly than leaving them in constant memory.

Conveniently the instruction numeric values are in alphabetical order which is the only reason I really considered this approach. I sorted them by selecting all the lines and doing ":sort" in vim. We also have a tablegen backend that generates a buggy version of the same tables in almost the same order. There are some manual entries hardcoded into tablegen that get dumped at the end of each table that mess up the ordering. I expect new entries to be added by getting them from the auto generated table and bringing them over.

You're absolutely right that I should have left a comment.

greened added inline comments.Jun 25 2018, 12:52 PM
llvm/trunk/lib/Target/X86/X86InstrInfo.cpp
123 ↗(On Diff #152723)

Could you write that up in a prominent block comment? Basically, explain how the opcode numbers correspond to alphabetical order (and are expected to remain that way) and how new entries should be added.

If TableGen is buggy, can we just fix it and use those tables instead of rewriting them here?

lib/Target/X86/X86InstrInfo.h