Page MenuHomePhabricator

Reapply Avoid creating an immutable map in the Automaton class.
Needs ReviewPublic

Authored by kariddi on Jan 20 2020, 4:40 PM.

Details

Summary

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
itself.

This map creation can make the creation of a DFAPacketizer
quite expensive if the target contains a considerable
amount of transition states.
This patch avoids creating the new map by using the TableGen
generated array as the map based on the assumption that this
array is already sorted in the DFAPacketizer by State/Action
pairs (the key of the map) and we can perform cheap log(N)
searches using std::lower_bound() directly on this array.

The previous patch in 051d330314cb1f175025ca37da8e5e1d851e1790
used this approach for every possible user of the Automaton.
In this patch this approach is used only in the DFAPacketizer.
The problem was that, because the Action object can be customized,
there could be cases where the relative order of the actions
is different between the time TableGen generates the transitions
array and the time the Automaton is instantiated if a customized
action type is used.

An example is the "BinPackerAutomatonAccepts" that asserted on
an assert() added on the previous commit.
In this test the "BinRequirementKindEnum" is generated through
the "Searchable Tables" infrastructure.
When the transitions array is generated every element of the enum
is assigned a temporary value and the transitions array is ordered
based on that value. In the transition array the enum is left with
its textual name and not the underlying value (like BRK_0_to_4,
BRK_0_to_6, ... etc in this case).
The C++ code that is included by users of the enum is generated
subsequently by the "Searchable Tables" infrastructure and is at this
point that each element of the enum have their actual numerical value
assigned. With this new assignment the relative order between enum elements
could be different from the one temporarily determined during the transitions
array generation, causing the array to be effectively unordered now and
to fix that is necessary to actually create the map and we can't
perform the optimization.

Event Timeline

kariddi created this revision.Jan 20 2020, 4:40 PM
Herald added a project: Restricted Project. · View Herald TranscriptJan 20 2020, 4:40 PM
kariddi updated this revision to Diff 239751.Jan 22 2020, 5:53 PM

Fixing typo that made everything useless :P

jmolloy added inline comments.Jan 23 2020, 4:44 AM
llvm/include/llvm/Support/Automaton.h
238

Does this compile? I'm confused by the syntax here.

kariddi marked an inline comment as done.Jan 23 2020, 8:31 AM
kariddi added inline comments.
llvm/include/llvm/Support/Automaton.h
238

Yeah, it compiles, we are passing the the map type as a template parameter (so if they user knows is not doing anything fancy with custom actions can use the one that just uses the ordered array in the background), but the map type is a templated type on the action type.

I chose to pass a template here instead of a class because if we passed a class the instantiation would have looked something like:

Automaton<uint64_t, OrderedArrayMap<uint64_t> A;

Duplicating the information about the action type in the instantiation (passed both to the automaton and the map), with this syntax we can do:

Automaton<uint64_t, OrderedArrayMap> A;

Another way I was thinking I could have done is pass the action type through the map and then just do:

Automaton<OrderedArrayMap<uint64_t>> A;

but the action type seems something that pertains the Automaton more than the map, so I liked more the first version.

kariddi marked an inline comment as done.Jan 23 2020, 11:40 AM