[LLVMdev] [llvm-commits] [PATCH] Refactoring the DFA generator
Ivan Llopard
ivanllopard at gmail.com
Thu Jun 28 02:28:51 PDT 2012
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);
More information about the llvm-dev
mailing list