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

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
>>>>>>>
>>>>>
>>>
>
>
-------------- next part --------------
Index: DFAPacketizerEmitter.cpp
==================================================================---
DFAPacketizerEmitter.cpp	(révision 159340)
+++ DFAPacketizerEmitter.cpp	(copie de travail)
@@ -76,15 +76,19 @@
 //
 //
 namespace {
+struct Transition;
+
 class State {
  public:
   static int currentStateNum;
   int stateNum;
   bool isInitial;
   std::set<unsigned> stateInfo;
+  std::map<unsigned, Transition *> inputToTrans;
 
   State();
   State(const State &S);
+  ~State();
 
   //
   // canAddInsnClass - Returns true if an instruction of type InsnClass is a
@@ -100,6 +104,15 @@
   // which are possible from this state (PossibleStates).
   //
   void AddInsnClass(unsigned InsnClass, std::set<unsigned>
&PossibleStates);
+  // 
+  // addTransition - Add a transition from this state given the input InsnClass
+  //
+  void addTransition(unsigned InsnClass, Transition *T);
+  //
+  // hasTransition - Returns true if there is a transition from this state
+  // given the input InsnClass
+  //
+  bool hasTransition(unsigned InsnClass);
 };
 } // End anonymous namespace.
 
@@ -139,6 +152,7 @@
 class DFA {
 public:
   DFA();
+  ~DFA();
 
   // Set of states. Need to keep this sorted to emit the transition table.
   std::set<State*, ltState> states;
@@ -148,9 +162,6 @@
     stateTransitions;
   State *currentState;
 
-  // Highest valued Input seen.
-  unsigned LargestInput;
-
   //
   // Modify the DFA.
   //
@@ -179,7 +190,7 @@
 
 
 //
-// Constructors for State, Transition, and DFA
+// Constructors and destructors for State, Transition, and DFA
 //
 State::State() :
   stateNum(currentStateNum++), isInitial(false) {}
@@ -189,15 +200,26 @@
   stateNum(currentStateNum++), isInitial(S.isInitial),
   stateInfo(S.stateInfo) {}
 
+State::~State() {
+  for (std::map<unsigned, Transition *>::const_iterator
+      TI = inputToTrans.begin(), TE = inputToTrans.end(); TI != TE; ++TI)
+    delete TI->second;
+}
 
 Transition::Transition(State *from_, unsigned input_, State *to_) :
   transitionNum(currentTransitionNum++), from(from_), input(input_),
-  to(to_) {}
+  to(to_) {
+  from->addTransition(input_, this);
+}
 
 
-DFA::DFA() :
-  LargestInput(0) {}
+DFA::DFA(): currentState(NULL) {}
 
+DFA::~DFA() {
+  for (std::set<State*, ltState>::const_iterator SI = states.begin(),
+      SE = states.end(); SI != SE; ++SI)
+    delete *SI;
+}
 
 bool ltState::operator()(const State *s1, const State *s2) const {
     return (s1->stateNum < s2->stateNum);
@@ -207,7 +229,26 @@
     return (s1->input < s2->input);
 }
 
+// 
+// addTransition - Add a transition from this state given the input InsnClass
 //
+void State::addTransition(unsigned InsnClass, Transition *T) {
+  assert(T->from == this && "Not a transition from this
state");
+  bool Added = inputToTrans.insert(std::make_pair(InsnClass, T)).second;
+  assert(Added && "Cannot have multiple transitions for the same
input");
+  // Silence unused variable warning
+  (void)Added;
+}
+
+//
+// hasTransition - Returns true if there is a transition from this state
+// given the input InsnClass
+//
+bool State::hasTransition(unsigned InsnClass) {
+  return inputToTrans.find(InsnClass) != inputToTrans.end();
+}
+
+//
 // AddInsnClass - Return all combinations of resource reservation
 // which are possible from this state (PossibleStates).
 //
@@ -272,6 +313,7 @@
 
 
 void DFA::initialize() {
+  assert(currentState && "Missing current state");
   currentState->isInitial = true;
 }
 
@@ -283,10 +325,6 @@
 
 
 void DFA::addTransition(Transition *T) {
-  // Update LargestInput.
-  if (T->input > LargestInput)
-    LargestInput = T->input;
-
   // Add the new transition.
   bool Added = stateTransitions[T->from].insert(T).second;
   assert(Added && "Cannot have multiple states for the same
input");
@@ -353,18 +391,18 @@
   // to construct the StateEntry table.
   int ValidTransitions = 0;
   for (unsigned i = 0; i < states.size(); ++i, ++SI) {
+    assert (((*SI)->stateNum == (int) i) && "Mismatch in state
numbers");
     StateEntry[i] = ValidTransitions;
-    for (unsigned j = 0; j <= LargestInput; ++j) {
-      assert (((*SI)->stateNum == (int) i) && "Mismatch in
state numbers");
-      State *To = getTransition(*SI, j);
-      if (To == NULL)
-        continue;
+    for (std::map<unsigned, Transition *>::const_iterator
+        II = (*SI)->inputToTrans.begin(), IE = (*SI)->inputToTrans.end();
+        II != IE; ++II) {
+      State *To = (*II).second->to;
 
-      OS << "{" << j << ", "
+      OS << "{" << (*II).first << ", "
          << To->stateNum
          << "},    ";
-      ++ValidTransitions;
     }
+    ValidTransitions += (*SI)->inputToTrans.size();
 
     // If there are no valid transitions from this stage, we need a sentinel
     // transition.
@@ -539,7 +577,7 @@
       // If we haven't already created a transition for this input
       // and the state can accommodate this InsnClass, create a transition.
       //
-      if (!D.getTransition(current, InsnClass) &&
+      if (!current->hasTransition(InsnClass) &&
           current->canAddInsnClass(InsnClass)) {
         State *NewState = NULL;
         current->AddInsnClass(InsnClass, NewStateResources);

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

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. But then please remove the 
Transition mechanism for the DFA class (stateTransitions).

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.

-Anshu

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>