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

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

> I don't have commit access. It applies correctly on trunk,
 > I've just checked it. Could you please commit it?

Ivan: Sure, I'll commit the patch today.

-Anshu

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

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

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.

Thanks,
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 159332)
+++ 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>::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,24 @@
     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");
+}
+
+//
+// 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 +311,7 @@
 
 
 void DFA::initialize() {
+  assert(currentState && "Missing current state");
   currentState->isInitial = true;
 }
 
@@ -283,10 +323,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 +389,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 +575,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);

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