Ivan Llopard
2012-Jun-26 08:04 UTC
[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 >>>>> >>> >
Anshuman Dasgupta
2012-Jun-27 15:21 UTC
[LLVMdev] [llvm-commits] [PATCH] Refactoring the DFA generator
> 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
Anshuman Dasgupta
2012-Jun-27 19:42 UTC
[LLVMdev] [llvm-commits] [PATCH] Refactoring the DFA generator
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 >>>>>> >>>> >>
Ivan Llopard
2012-Jun-28 08:10 UTC
[LLVMdev] [llvm-commits] [PATCH] Refactoring the DFA generator
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);
Ivan Llopard
2012-Jun-28 09:28 UTC
[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);
Possibly Parallel Threads
- [LLVMdev] [llvm-commits] [PATCH] Refactoring the DFA generator
- [LLVMdev] [llvm-commits] [PATCH] Refactoring the DFA generator
- [LLVMdev] [llvm-commits] [PATCH] Refactoring the DFA generator
- [LLVMdev] [llvm-commits] [PATCH] Refactoring the DFA generator
- [LLVMdev] [llvm-commits] [PATCH] Refactoring the DFA generator