From d6f06025646f86bed78831ae2ec46bd1d4126d09 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Fri, 26 Feb 2010 08:08:41 +0000 Subject: switch from my nice hashtable based merging solution to a gross little neighbor merging implementation. This one has the benefit of not violating the ordering of patterns, so it generates code that passes tests again. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@97218 91177308-0d34-0410-b5e6-96231b3b80d8 --- utils/TableGen/DAGISelMatcherOpt.cpp | 88 +++++++++--------------------------- 1 file changed, 22 insertions(+), 66 deletions(-) (limited to 'utils/TableGen/DAGISelMatcherOpt.cpp') diff --git a/utils/TableGen/DAGISelMatcherOpt.cpp b/utils/TableGen/DAGISelMatcherOpt.cpp index d4796e9..5aaa51f 100644 --- a/utils/TableGen/DAGISelMatcherOpt.cpp +++ b/utils/TableGen/DAGISelMatcherOpt.cpp @@ -75,86 +75,40 @@ static void FactorNodes(OwningPtr &MatcherPtr) { // inspect it more easily. While we're at it, bucket them up by the hash // code of their first predicate. SmallVector OptionsToMatch; - typedef DenseMap > HashTableTy; - HashTableTy MatchersByHash; for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) { // Factor the subexpression. OwningPtr Child(Scope->takeChild(i)); FactorNodes(Child); - if (Matcher *N = Child.take()) { + if (Matcher *N = Child.take()) OptionsToMatch.push_back(N); - MatchersByHash[N->getHash()].push_back(N); - } } SmallVector NewOptionsToMatch; - // Now that we have bucketed up things by hash code, iterate over sets of - // matchers that all start with the same node. We would like to iterate over - // the hash table, but it isn't in deterministic order, emulate this by going - // about this slightly backwards. After each set of nodes is processed, we - // remove them from MatchersByHash. - for (unsigned i = 0, e = OptionsToMatch.size(); - i != e && !MatchersByHash.empty(); ++i) { + // Loop over options to match, merging neighboring patterns with identical + // starting nodes into a shared matcher. + for (unsigned i = 0, e = OptionsToMatch.size(); i != e;) { // Find the set of matchers that start with this node. - Matcher *Optn = OptionsToMatch[i]; - - // Find all nodes that hash to the same value. If there is no entry in the - // hash table, then we must have previously processed a node equal to this - // one. - HashTableTy::iterator DMI = MatchersByHash.find(Optn->getHash()); - if (DMI == MatchersByHash.end()) { - delete Optn; - continue; - } - - std::vector &HashMembers = DMI->second; - assert(!HashMembers.empty() && "Should be removed if empty"); - - // Check to see if this node is in HashMembers, if not it was equal to a - // previous node and removed. - std::vector::iterator MemberSlot = - std::find(HashMembers.begin(), HashMembers.end(), Optn); - if (MemberSlot == HashMembers.end()) { - delete Optn; + Matcher *Optn = OptionsToMatch[i++]; + + // See if the next option starts with the same matcher, if not, no sharing. + if (i == e || !OptionsToMatch[i]->isEqual(Optn)) { + // TODO: Skip over mutually exclusive patterns. + NewOptionsToMatch.push_back(Optn); continue; } - // If the node *does* exist in HashMembers, then we've confirmed that it - // hasn't been processed as equal to a previous node. Process it now, start - // by removing it from the list of hash-equal nodes. - HashMembers.erase(MemberSlot); - - // Scan all of the hash members looking for ones that are equal, removing - // them from HashMembers, adding them to EqualMatchers. + // If the two neighbors *do* start with the same matcher, we can factor the + // matcher out of at least these two patterns. See what the maximal set we + // can merge together is. SmallVector EqualMatchers; - - // Scan the vector backwards so we're generally removing from the end to - // avoid pointless data copying. - for (unsigned i = HashMembers.size(); i != 0; --i) { - if (!HashMembers[i-1]->isEqual(Optn)) continue; - - EqualMatchers.push_back(HashMembers[i-1]); - HashMembers.erase(HashMembers.begin()+i-1); - } EqualMatchers.push_back(Optn); + EqualMatchers.push_back(OptionsToMatch[i++]); - // Reverse the vector so that we preserve the match ordering. - std::reverse(EqualMatchers.begin(), EqualMatchers.end()); - - // If HashMembers is empty at this point, then we've gotten all nodes with - // the same hash, nuke the entry in the hash table. - if (HashMembers.empty()) - MatchersByHash.erase(Optn->getHash()); - - // Okay, we have the list of all matchers that start with the same node as - // Optn. If there is more than one in the set, we want to factor them. - if (EqualMatchers.size() == 1) { - NewOptionsToMatch.push_back(Optn); - continue; - } + while (i != e && OptionsToMatch[i]->isEqual(Optn)) + EqualMatchers.push_back(OptionsToMatch[i++]); // Factor these checks by pulling the first node off each entry and // discarding it. Take the first one off the first entry to reuse. @@ -162,10 +116,12 @@ static void FactorNodes(OwningPtr &MatcherPtr) { Optn = Optn->takeNext(); EqualMatchers[0] = Optn; - // Skip the first node. Leave the first node around though, we'll delete it - // on subsequent iterations over OptionsToMatch. - for (unsigned i = 1, e = EqualMatchers.size(); i != e; ++i) - EqualMatchers[i] = EqualMatchers[i]->takeNext(); + // Remove and delete the first node from the other matchers we're factoring. + for (unsigned i = 1, e = EqualMatchers.size(); i != e; ++i) { + Matcher *Tmp = EqualMatchers[i]->takeNext(); + delete EqualMatchers[i]; + EqualMatchers[i] = Tmp; + } Shared->setNext(new ScopeMatcher(&EqualMatchers[0], EqualMatchers.size())); -- cgit v1.1