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

[Anshuman Dasgupta]

Ivan,

Unfortunately I won't be able to review the new patch in the next few 
days but I plan on taking a look at it next week.

-Anshu

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


On 6/28/2012 4:28 AM, Ivan Llopard wrote:
> I missed last 2 commits made by Alexey. Following his advices, I 
> updated the patch. It should be ok now.
>
> Ivan
>
> On 27/06/2012 21:42, Anshuman Dasgupta wrote:
>> 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
>>>>>>>>
>>>>>>
>>>>
>>
>>