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

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

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
>

-------------- next part --------------
A non-text attachment was scrubbed...
Name: DFAPacketizerEmitter.new.patch
Type: text/x-patch
Size: 8628 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120825/2ec5f657/attachment.bin>

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

Ivan,

Thanks for working on the patch. It looks good to me except for the 
removal of the Transition class:

 > (1) Should I completely remove Transition and create a map structure 
in State (input, state) to replace them?

Yes, please remove the Transition class and create a map structure in 
State instead of TransitionSet.

Thanks
-Anshu



On 8/25/2012 6:42 AM, 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].
>
> 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
>>
>
>

On 28/08/2012 00:21, Anshuman Dasgupta wrote:
> Ivan,
>
> Thanks for working on the patch. It looks good to me except for the
> removal of the Transition class:
>
>  > (1) Should I completely remove Transition and create a map structure
> in State (input, state) to replace them?
>
> Yes, please remove the Transition class and create a map structure in
> State instead of TransitionSet.
Sure. Please, take a look at the new patch.

Ivan
>
> Thanks
> -Anshu
>
>
>
> On 8/25/2012 6:42 AM, 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].
>>
>> 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
>>>
>>
>>
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: DFAPacketizerEmitter.new.patch
Type: text/x-patch
Size: 8117 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120829/4a66c373/attachment.bin>