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

Anshuman Dasgupta adasgupt at codeaurora.org
Wed Jun 20 10:33:45 PDT 2012


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


More information about the llvm-dev mailing list