Page MenuHomePhabricator

[TableGen] Introduce a generic automaton (DFA) backend
ClosedPublic

Authored by jmolloy on Sep 24 2019, 8:49 AM.

Details

Summary

This patch introduces -gen-automata, a backend for generating deterministic finite-state automata.

DFAs are already generated by the -gen-dfa-packetizer backend. This backend is more generic and will
hopefully be used to implement the DFA generation (and determinization) for the packetizer in the
future.

This backend allows not only generation of a DFA from an NFA (nondeterministic finite-state
automaton), it also emits sidetables that allow a path through the DFA under a sequence of inputs to
be analyzed, and the equivalent set of all possible NFA transitions extracted.

This allows a user to not just answer "can my problem be solved?" but also "what is the
solution?". Clearly this analysis is more expensive than just playing a DFA forwards so is
opt-in. The DFAPacketizer has this behaviour already but this is a more compact and generic
representation.

Examples are bundled in unittests/TableGen/Automata.td. Some are trivial, but the BinPacking example
is a stripped-down version of the original target problem I set out to solve, where we pack values
(actually immediates) into bins (an immediate pool in a VLIW bundle) subject to a set of esoteric
constraints.

Diff Detail

Repository
rL LLVM

Event Timeline

jmolloy created this revision.Sep 24 2019, 8:49 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 24 2019, 8:49 AM

Hi Daniel,

Perhaps you might have some thoughts on this patch? It's a step towards slightly easier bundle packing and similar problems for VLIWs.

Cheers,

James

majnemer added inline comments.
llvm/include/llvm/TableGen/Automaton.td
25 ↗(On Diff #221549)

Is it OK to have unicode in source files? It used to be frowned upon IIRC.

llvm/utils/TableGen/DFAEmitter.cpp
210–211 ↗(On Diff #221549)

Why do these take references?

334 ↗(On Diff #221549)

Should we assert(NewStateInit->getNumBits() <= sizeof(uint64_t) * 8 somewhere?

llvm/utils/TableGen/DFAEmitter.h
48 ↗(On Diff #221549)

= default();

49 ↗(On Diff #221549)

= default();

jmolloy updated this revision to Diff 222377.Sep 30 2019, 2:20 AM
jmolloy marked 6 inline comments as done.

Thanks David - I missed your comments, sorry this is a late response.

jmolloy added inline comments.Sep 30 2019, 2:56 AM
llvm/utils/TableGen/DFAEmitter.cpp
210–211 ↗(On Diff #221549)

Just a hangover from when I used a non-POD datatype as parameter here. Fixed, thanks!

Perhaps you might have some thoughts on this patch? It's a step towards slightly easier bundle packing and similar problems for VLIWs.

Hi James,

Sorry for the slow reply. Our target isn't a VLIW, our instructions words are just very long :-). We don't have the usual VLIW issues, it just takes a lot of bits to describe some operations.

I haven't dug into the implementation code but FWIW, the definition makes sense to me. It took me a little while to pick up on how State bits being 1 prevented transitions that has NewState be 1 in that same bit and it might be worth commenting on that in the tests.

llvm/unittests/TableGen/AutomataTest.cpp
101–117 ↗(On Diff #222377)

I notice that there isn't a test where one of the two-bin constraints is trying to pack into a state where only one of the two bins are available.
Shouldn't there be one that does something like pack BRK_0_to_6 five times and then checks that packing BRK_0_to_6_dbl fails?

jmolloy marked 2 inline comments as done.Oct 1 2019, 5:23 AM

Hi Daniel,

Sorry for the slow reply. Our target isn't a VLIW, our instructions words are just very long :-). We don't have the usual VLIW issues, it just takes a lot of bits to describe some operations.

Ah, apologies for the mischaracterization. Thanks so much for taking a look!

I've added descriptions to the Transition class which I hadn't realised was missing documentation. PTAL!

Cheers,

James

llvm/unittests/TableGen/AutomataTest.cpp
101–117 ↗(On Diff #222377)

Great point, thanks! Added a test.

jmolloy updated this revision to Diff 222597.Oct 1 2019, 5:24 AM
jmolloy marked an inline comment as done.

Address review comments.

I've added descriptions to the Transition class which I hadn't realised was missing documentation. PTAL!

Thanks. That's much clearer

majnemer accepted this revision.Oct 2 2019, 4:20 PM

LGTM

This revision is now accepted and ready to land.Oct 2 2019, 4:20 PM
This revision was automatically updated to reflect the committed changes.
stevewan added a subscriber: stevewan.EditedOct 4 2019, 12:22 PM

Hi @jmolloy,

This is breaking our internal build bots with gcc version 5.4.0. Sample error is as follows,

/home/docker/llvm-project/llvm/unittests/TableGen/AutomataTest.cpp: In member function ‘virtual void Automata_TupleAutomatonAccepts_Test::TestBody()’:
/home/docker/llvm-project/llvm/unittests/TableGen/AutomataTest.cpp:65:33: error: converting to ‘const std::tuple<SymKind, SymKind, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >’ from initializer list would use explicit constructor ‘constexpr std::tuple< <template-parameter-1-1> >::tuple(_UElements&& ...) [with _UElements = {SymKind, SymKind, const char (&)[5]}; <template-parameter-2-2> = void; _Elements = {SymKind, SymKind, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >}]’
       A.add({SK_a, SK_b, "yeet"}));
                                 ^

Please let us know regarding timeline for a fix. Thanks!

clang-cuda-build buildbot failed too:
http://lab.llvm.org:8011/builders/clang-cuda-build/builds/37865/steps/ninja%20check%201/logs/stdio

I think it can be fixed with

@@ -371,20 +371,20 @@ uint64_t Transition::transitionFrom(uint64_t State) {
 void CustomDfaEmitter::printActionType(raw_ostream &OS) { OS << TypeName; }
 
 void CustomDfaEmitter::printActionValue(action_type A, raw_ostream &OS) {
   const ActionTuple &AT = Actions[A];
   if (AT.size() > 1)
-    OS << "{";
+    OS << "std::make_tuple(";
   bool First = true;
   for (const auto &SingleAction : AT) {
     if (!First)
       OS << ", ";
     First = false;
     SingleAction.print(OS);
   }
   if (AT.size() > 1)
-    OS << "}";
+    OS << ")";
 }
 
 namespace llvm {
 
 void EmitAutomata(RecordKeeper &RK, raw_ostream &OS) {

similar to the fix in r372384 (169cb6347).