This is an archive of the discontinued LLVM Phabricator instance.

Avoid creating an immutable map in the Automaton class.

Authored by kariddi on Jan 13 2020, 10:16 PM.



In the DFAPacketizer we copy the Transitions array
into a map in order to later access the transitions
based on a "Current State/Action" pair as a key.
This map lives in the Automaton object used by the DFAPacketizer.
It is never changed during the life of the object after
having been created during the creation of the Automaton

This map creation can make the creation of a DFAPacketizer
quite expensive if the target contains a considerable
amount of transition states.

Considering that TableGen already generates a
sorted list of transitions by State/Action pairs
we could just use that directly in our Automaton
and search entries with std::lower_bound instead of copying
it in a map and paying the execution time and memory cost.

Diff Detail

Event Timeline

kariddi created this revision.Jan 13 2020, 10:16 PM
Herald added a project: Restricted Project. · View Herald TranscriptJan 13 2020, 10:16 PM
kariddi updated this revision to Diff 237853.Jan 13 2020, 10:20 PM

Updating a stale comment where the old map used to live

Harbormaster completed remote builds in B43897: Diff 237853.
jmolloy accepted this revision.Jan 16 2020, 5:57 AM

Nice cleanup, thanks!

This revision is now accepted and ready to land.Jan 16 2020, 5:57 AM
This revision was automatically updated to reflect the committed changes.
tycho added a subscriber: tycho.Jan 16 2020, 11:10 PM

This change is causing test regressions, e.g::

Failing Tests (2):
    LLVM-Unit :: TableGen/./TableGenTests/Automata.BinPackerAutomatonAccepts
    LLVM-Unit :: TableGen/./TableGenTests/Automata.BinPackerAutomatonExplains

This change broke buildbots and I reverted it in 10b4aece528936bb7f75a9758ae95c61b6434d2f.

Please always run ninja check-all before pushing.