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

[Ivan Llopard]

On 25/08/2012 13:42, Ivan Llopard wrote:
> Hi Anshu,
>
> Thanks again for your feedbacks.
>
> On 24/08/2012 17:01, Anshuman Dasgupta wrote:
>> Hi Ivan,
>>
>>> I missed last 2 commits made by Alexey. Following his advices, I
>>> updated the patch. It should be ok now.
>>> Thanks Anshu!
>>>
>>> I've recently added more functional units to our Schedule.td and the
>>> generation time became painfully long. In fact, the main problem was
>>> in writeTableAndAPI(). I propose another patch to fix it:
>>> - Fixed memory leaks.
>>> - Transitions are attached to states.
>>>
>>> I've regenerated the DFA table of Hexagon and everything is ok.
>>> Please review it.
>>
>> I had a few comments about the design change that you're introducing
>> with the patch:
>>
>> This patch adds multiple points of control for adding a transition:
>> there's now an addTransition() for DFA and another addTransition() for
>> State that populate different data structures. We shouldn't need both. I
>> am okay with transitions being folded into the State class if it results
>> in significant speedup in DFA generation.
>
> Yes, it gives a significant speedup to the emitter. My main concern is
> to address this:
>
> 357:    for (unsigned j = 0; j <= LargestInput; ++j) {
>
> LargestInput becomes too large. The more resources we introduce in the
> td file the larger it will be. Given an architecture with n resources,
> LargestInput will take the maximum value, i.e. 2^(n-1), but valid inputs
> are just a small subset of [0, LargestInput].

ERRATA: LargestInput will take some value in [2^(n-1), 2^n-1]. That's 
depend on the resource combinations. Then it may be even larger! :)

>
> But then please remove the
>> Transition mechanism for the DFA class (stateTransitions).
>
> Done!
>
>>
>> For transitions being folded into State:
>>  > std::map<unsigned, Transition *> inputToTrans;
>>
>> We don't need a map to Transition* here; we can directly map from input
>> to stateNum. You should be able to use a LLVM data structure.
>
> In that case,
> (1) Should I completely remove Transition and create a map structure in
> State (input, state) to replace them?
> (2) Or are you proposing to go though DFA in order look for valid
> transitions?
>
> After doing some cleanup to match the new design, these are the main
> changes:
> - Transition folded in states.
> Each state keeps a set of transitions.
> - Each transition contains the input to match in order to take it and
> the destination state 'To'.
> - Factoring up redundant information.
> Transitions doesn't contains 'From' state anymore because they are
> folded into it.
> - Using STLExtras functions.
> - Removed old and unused API's (e.g. addTransition in DFA)
>
> The new patch is attached but if you prefer (2) I can remake it.
>
> I failed to use SmallSet to store the transitions in State because I
> needed to iterate on it. What kind of llvm structure may I use?
>
> Ivan
>
>>
>> -Anshu
>>
>
>