This is an archive of the discontinued LLVM Phabricator instance.

[MC] Rewrite tablegen for printInstrAlias to comiple faster, NFC
ClosedPublic

Authored by rnk on Nov 24 2019, 7:29 PM.

Details

Summary

Before this change, the *InstPrinter.cpp files of each target where some
of the slowest objects to compile in all of LLVM. See this snippet produced by
ClangBuildAnalyzer:
https://reviews.llvm.org/P8171$96
Search for "InstPrinter", and see that it shows up in a few places.

Tablegen was emitting a large switch containing a sequence of operand checks,
each of which created many conditions and many BBs. Register allocation and
jump threading both did not scale well with such a large repetitive sequence of
basic blocks.

So, this change essentially turns those control flow structures into
data. The previous structure looked like:

switch (Opc) {
case TGT::ADD:
  // check alias 1
  if (MI->getOperandCount() == N && // check num opnds
      MI->getOperand(0).isReg() && // check opnd 0
      ...
      MI->getOperand(1).isImm() && // check opnd 1
   AsmString = "foo";
   break;
 }
 // check alias 2
 if (...)
   ...
 return false;

The new structure looks like:

OpToPatterns: Sorted table of opcodes mapping to pattern indices.
 \->
   Patterns: List of patterns. Previous table points to subrange of
             patterns to match.
    \->
      Conds: The if conditions above encoded as a kind and 32-bit value.

See MCInstPrinter.cpp for the details of how the new data structures are
interpreted.

Here are some before and after metrics.
Time to compile AArch64InstPrinter.cpp:

0m29.062s vs. 0m2.203s

size of the obj:

3.9M vs. 676K

size of clang.exe:

97M vs. 96M

I have not benchmarked disassembly performance, but typically
disassemblers are bottlenecked on IO and string processing, not alias
matching, so I'm not sure it's interesting enough to be worth doing.

Diff Detail

Event Timeline

rnk created this revision.Nov 24 2019, 7:29 PM
Herald added a project: Restricted Project. · View Herald TranscriptNov 24 2019, 7:29 PM

Adding extra reviewers as I'm about to go on holiday...

spatel edited reviewers, added: craig.topper; removed: spatel.Nov 25 2019, 6:28 AM

Looks very promising, but I don't know anything about this layer. Replacing me on the reviewer list with Craig.

spatel added a subscriber: spatel.Nov 25 2019, 6:28 AM
craig.topper added inline comments.Nov 25 2019, 11:36 AM
llvm/utils/TableGen/AsmWriterEmitter.cpp
677

Should we rename this since it doesn't print to a stream anymore?

818

Can we move the IAP object down and pass this to the constructor?

921–923

Bad identation here

954

Why StringRef(Op)? Isn't Op already a StringRef?

rnk updated this revision to Diff 230965.Nov 25 2019, 1:49 PM
rnk marked 6 inline comments as done.
  • fix issues
rnk added a comment.Nov 25 2019, 1:49 PM

Here's an example of the generated output for easier code review:
https://reviews.llvm.org/P8172

llvm/utils/TableGen/AsmWriterEmitter.cpp
677

Yeah. I named it formatAliasString.

818

Sure.

954

True, it is. This code uses std::string a lot, so I think I assumed I needed to convert first.

craig.topper added inline comments.Dec 5 2019, 4:43 PM
llvm/lib/MC/MCInstPrinter.cpp
106

Nit: I think the first "To" was supposed to be "Too"

llvm/utils/TableGen/AsmWriterEmitter.cpp
682–683

Was this changed from SmallString to std::string so we could just return it? Do we lose out on NRVO by going through OS.str() instead of OS.flush; return OutString;?

685–686

How efficient is putting 1 character at a time into a std::string with respect to heap allocations vs the large SmallString we had before. Though I'm not sure how long these strings are in practice. Do we stay under the small string size for std::string?

rnk marked 3 inline comments as done.Dec 5 2019, 4:50 PM
rnk added inline comments.
llvm/lib/MC/MCInstPrinter.cpp
106

Actually, this wasn't suppose to go up for review. I don't want to do O(n) things that should be O(log n) even in an asserts build. I'll try moving this assert into a static local constructor that runs once.

llvm/utils/TableGen/AsmWriterEmitter.cpp
682–683

Yes, I think you're right.

685–686

Well, this is tablegen anyway, so efficiency is less of a concern. If we wanted to save tablegen time, there are a number of things we could do to speed it up. These strings do end up being under 128 characters in practice, since they are derived from assembler snippets.

rnk updated this revision to Diff 232477.Dec 5 2019, 5:01 PM
  • NRVO std::string
  • Move is_sorted check
This revision is now accepted and ready to land.Dec 6 2019, 9:35 AM
This revision was automatically updated to reflect the committed changes.