[LLVMdev] [llvm-commits] [PATCH] Refactoring the DFA generator

[Anshuman Dasgupta]

Committed in r159281.

-Anshu


On 6/26/2012 3:04 AM, Ivan Llopard wrote:
> 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
>>>>>>
>>>>
>>