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

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>

Hi Ivan,

Sorry, I should have been more explicit in my last email. The patch looks
good to me. Please check that it applies on trunk and go ahead and commit.

Thanks
-Anshu


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

Hi Anshu,

I don't have commit access. It applies correctly on trunk, I've just 
checked it. Could you please commit it?

Ivan

On 26/06/2012 04:44, adasgupt at codeaurora.org wrote:
> Hi Ivan,
>
> Sorry, I should have been more explicit in my last email. The patch looks
> good to me. Please check that it applies on trunk and go ahead and commit.
>
> Thanks
> -Anshu
>
>
>
>> 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
>>>>>
>>>
>