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

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>

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

Great. Looks good to me.

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

I agree; let's keep it around for now.

-Anshu

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



On 6/18/2012 3:47 AM, Ivan Llopard wrote:
> 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/20120620/ba85a45c/attachment.html>

Hi Anshu,

Just in case you have forgotten this thread ;-). Is this patch ok to 
commit or does it not apply to trunk properly ?
I can fix it if that's the problem.

Ivan

On 20/06/2012 19:33, Anshuman Dasgupta wrote:
>
> > Thanks for reviewing this. I added a top comment for AddInsnClass 
> and I fixed the violation of column numbers.
>
> Great. Looks good to me.
>
> > 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.
>
> I agree; let's keep it around for now.
>
> -Anshu
>
> ---
> Qualcomm Innovation Center, Inc is a member of the Code Aurora Forum
>
>
>
> On 6/18/2012 3:47 AM, Ivan Llopard wrote:
>> 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/20120625/6bb23824/attachment.html>