llvm dev - Jun 2012 - [LLVMdev] [PATCH] Refactoring the DFA generator

Hi,

I've refactored the DFA generator in TableGen because it takes too much 
time to build the table of our BE and I'd like to share it.
We have 15 functional units and 13 different itineraries which, in the 
worst case, can produce 13! states. Fortunately, many of those states 
are reused :-) but it still takes up to 11min to build the entire table. 
This patch reduces the build time to 5min, giving a speed-up factor 
greater than 2.

It contains small changes:
- Transitions are stored in a set for quicker searches
- canAddInsnClass() API is split in two API's:
   - canAddInsnClass() which perform a quick verification about the 
possibility of having new states for a given InsnClass
   - AddInsnClass() performs the actual computation of possible states.

I've regenerated the DFA table of Hexagon and all seems to be ok.

What do you think about these changes ?


Ivan
-------------- next part --------------
A non-text attachment was scrubbed...
Name: DFAPacketizerEmitter.speedup.patch
Type: text/x-patch
Size: 4957 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120614/93dca92e/attachment.bin>

Thank you for using a deterministic sort order for the std::set :)

One nit: please make as much as possible private to the translation unit.
Run

nm DFAPacketizerEmitter.cpp.o | awk '$2 == "T"' | c++filt

to ensure that only the "emit" function is being exported.

I can't comment on the validity of this optimization since I'm not
familiar
with the algorithm that this code uses.

--Sean Silva

On Thu, Jun 14, 2012 at 6:22 AM, Ivan Llopard <ivanllopard at gmail.com>
wrote:
> Hi,
>
> I've refactored the DFA generator in TableGen because it takes too much
> time to build the table of our BE and I'd like to share it.
> We have 15 functional units and 13 different itineraries which, in the
> worst case, can produce 13! states. Fortunately, many of those states are
> reused :-) but it still takes up to 11min to build the entire table. This
> patch reduces the build time to 5min, giving a speed-up factor greater than
> 2.
>
> It contains small changes:
> - Transitions are stored in a set for quicker searches
> - canAddInsnClass() API is split in two API's:
>  - canAddInsnClass() which perform a quick verification about the
> possibility of having new states for a given InsnClass
>  - AddInsnClass() performs the actual computation of possible states.
>
> I've regenerated the DFA table of Hexagon and all seems to be ok.
>
> What do you think about these changes ?
>
>
> Ivan
>
> _______________________________________________
> llvm-commits mailing list
> llvm-commits at cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120614/8b514795/attachment.html>

Ivan,

Thanks for working on the DFA generator. I'll take a look at the changes 
in detail but from your description, I like the general nature of the 
modifications.

-Anshu

---
Qualcomm Innovation Center, Inc is a member of the Code Aurora Forum


On 6/14/2012 8:22 AM, Ivan Llopard wrote:
> Hi,
>
> I've refactored the DFA generator in TableGen because it takes too 
> much time to build the table of our BE and I'd like to share it.
> We have 15 functional units and 13 different itineraries which, in the 
> worst case, can produce 13! states. Fortunately, many of those states 
> are reused :-) but it still takes up to 11min to build the entire 
> table. This patch reduces the build time to 5min, giving a speed-up 
> factor greater than 2.
>
> It contains small changes:
> - Transitions are stored in a set for quicker searches
> - canAddInsnClass() API is split in two API's:
>   - canAddInsnClass() which perform a quick verification about the 
> possibility of having new states for a given InsnClass
>   - AddInsnClass() performs the actual computation of possible states.
>
> I've regenerated the DFA table of Hexagon and all seems to be ok.
>
> What do you think about these changes ?
>
>
> Ivan
>
>
> _______________________________________________
> llvm-commits mailing list
> llvm-commits at cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120614/230d9b24/attachment.html>

Hi Anshu, Sean,

Thanks for your quick feedbacks!

Sean, I ran your command and I had the following output:

$nm DFAPacketizerEmitter.o | awk '$2 == "T"' | c++filt
0000000000000000 T llvm::EmitDFAPacketizer(llvm::RecordKeeper&, 
llvm::raw_ostream&)

which I think it's correct.

Ivan

On 14/06/2012 21:15, Anshuman Dasgupta wrote:
> Ivan,
>
> Thanks for working on the DFA generator. I'll take a look at the 
> changes in detail but from your description, I like the general nature 
> of the modifications.
>
> -Anshu
>
> ---
> Qualcomm Innovation Center, Inc is a member of the Code Aurora Forum
>
>
> On 6/14/2012 8:22 AM, Ivan Llopard wrote:
>> Hi,
>>
>> I've refactored the DFA generator in TableGen because it takes too 
>> much time to build the table of our BE and I'd like to share it.
>> We have 15 functional units and 13 different itineraries which, in 
>> the worst case, can produce 13! states. Fortunately, many of those 
>> states are reused :-) but it still takes up to 11min to build the 
>> entire table. This patch reduces the build time to 5min, giving a 
>> speed-up factor greater than 2.
>>
>> It contains small changes:
>> - Transitions are stored in a set for quicker searches
>> - canAddInsnClass() API is split in two API's:
>>   - canAddInsnClass() which perform a quick verification about the 
>> possibility of having new states for a given InsnClass
>>   - AddInsnClass() performs the actual computation of possible states.
>>
>> I've regenerated the DFA table of Hexagon and all seems to be ok.
>>
>> What do you think about these changes ?
>>
>>
>> Ivan
>>
>>
>> _______________________________________________
>> llvm-commits mailing list
>> llvm-commits at cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120615/3fca74a3/attachment.html>

Hi Ivan,

The patch looks good to me. I have a couple of minor comments:

+void State::AddInsnClass(unsigned InsnClass,
Add a top level comment describing the function

+  std::map<State*, std::set<Transition*, ltTransition>, ltState> 
stateTransitions;
You should be able to use SmallSet here. Also, this line exceeds 80 columns.


On a related note, is the CachedTable mechanism in DFAPacketizer.h 
useful for your architecture? Currently the DFA generator generates one 
table for a given architecture. I had originally added the CachedTable 
mechanism since for a given compilation and subtarget, the DFA only uses 
the subset of the states and transitions. Using a "cache" made sense.
At
one point, I'd like to change the code so that it can generate one DFA 
for every subtarget and remove the CachedTable mechanism. Given the size 
of the DFA for your architecture, however, it may make sense to keep it 
around even if it generates separate tables for each subtarget.

Thanks
-Anshu

---
Qualcomm Innovation Center, Inc is a member of the Code Aurora Forum





On 6/14/2012 8:22 AM, Ivan Llopard wrote:
> Hi,
>
> I've refactored the DFA generator in TableGen because it takes too 
> much time to build the table of our BE and I'd like to share it.
> We have 15 functional units and 13 different itineraries which, in the 
> worst case, can produce 13! states. Fortunately, many of those states 
> are reused :-) but it still takes up to 11min to build the entire 
> table. This patch reduces the build time to 5min, giving a speed-up 
> factor greater than 2.
>
> It contains small changes:
> - Transitions are stored in a set for quicker searches
> - canAddInsnClass() API is split in two API's:
>   - canAddInsnClass() which perform a quick verification about the 
> possibility of having new states for a given InsnClass
>   - AddInsnClass() performs the actual computation of possible states.
>
> I've regenerated the DFA table of Hexagon and all seems to be ok.
>
> What do you think about these changes ?
>
>
> Ivan
>
>
> _______________________________________________
> llvm-commits mailing list
> llvm-commits at cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120615/468d8be4/attachment.html>

Hi Anshu,

Thanks for reviewing this. I added a top comment for AddInsnClass and I 
fixed the violation of column numbers.

On 15/06/2012 21:31, Anshuman Dasgupta wrote:
> Hi Ivan,
>
> The patch looks good to me. I have a couple of minor comments:
>
> +void State::AddInsnClass(unsigned InsnClass,
> Add a top level comment describing the function
>
> +  std::map<State*, std::set<Transition*, ltTransition>,
ltState>
> stateTransitions;
> You should be able to use SmallSet here. Also, this line exceeds 80 
> columns.
I tried but SmallSet is not iterable. SmallSetPtr could be useful here 
but it doesn't allow custom sorting.
>
>
> On a related note, is the CachedTable mechanism in DFAPacketizer.h 
> useful for your architecture? Currently the DFA generator generates 
> one table for a given architecture. I had originally added the 
> CachedTable mechanism since for a given compilation and subtarget, the 
> DFA only uses the subset of the states and transitions. Using a 
> "cache" made sense. At one point, I'd like to change the code
so that
> it can generate one DFA for every subtarget and remove the CachedTable 
> mechanism. Given the size of the DFA for your architecture, however, 
> it may make sense to keep it around even if it generates separate 
> tables for each subtarget.
I liked the cachedtable idea but I can't tell you if it's really useful 
in our case, I didn't make any performance tests in that regard.
IMO, it wil be nice to keep it alive for performance comparisons. Given 
the overall performance is rather determined by transition searches on 
the current state, for small DFA tables may not be a win and it may 
still be the case for greater ones. We have a huge number of states but 
the number of distinct itineraries, or maximum possible transitions, 
remains quite small (11, it wasn't 13, my mistake).

Ivan
>
> Thanks
> -Anshu
>
> ---
> Qualcomm Innovation Center, Inc is a member of the Code Aurora Forum
>
>
>
>
>
> On 6/14/2012 8:22 AM, Ivan Llopard wrote:
>> Hi,
>>
>> I've refactored the DFA generator in TableGen because it takes too 
>> much time to build the table of our BE and I'd like to share it.
>> We have 15 functional units and 13 different itineraries which, in 
>> the worst case, can produce 13! states. Fortunately, many of those 
>> states are reused :-) but it still takes up to 11min to build the 
>> entire table. This patch reduces the build time to 5min, giving a 
>> speed-up factor greater than 2.
>>
>> It contains small changes:
>> - Transitions are stored in a set for quicker searches
>> - canAddInsnClass() API is split in two API's:
>>   - canAddInsnClass() which perform a quick verification about the 
>> possibility of having new states for a given InsnClass
>>   - AddInsnClass() performs the actual computation of possible states.
>>
>> I've regenerated the DFA table of Hexagon and all seems to be ok.
>>
>> What do you think about these changes ?
>>
>>
>> Ivan
>>
>>
>> _______________________________________________
>> llvm-commits mailing list
>> llvm-commits at cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120618/66e4fa42/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: DFAPacketizerEmitter.speedup.patch
Type: text/x-patch
Size: 5050 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120618/66e4fa42/attachment.bin>