utils/TableGen/DAGISelMatcherOpt.cpp

   1 //===- DAGISelMatcherOpt.cpp - Optimize a DAG Matcher ---------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the DAG Matcher optimizer.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "DAGISelMatcher.h"
  15 #include "llvm/ADT/DenseMap.h"
  16 #include <vector>
  17 using namespace llvm;
  18
  19 static void ContractNodes(OwningPtr<Matcher> &MatcherPtr) {
  20   // If we reached the end of the chain, we're done.
  21   Matcher *N = MatcherPtr.get();
  22   if (N == 0) return;
  23
  24   // If we have a scope node, walk down all of the children.
  25   if (ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N)) {
  26     for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) {
  27       OwningPtr<Matcher> Child(Scope->takeChild(i));
  28       ContractNodes(Child);
  29       Scope->resetChild(i, Child.take());
  30     }
  31     return;
  32   }
  33
  34   // If we found a movechild node with a node that comes in a 'foochild' form,
  35   // transform it.
  36   if (MoveChildMatcher *MC = dyn_cast<MoveChildMatcher>(N)) {
  37     Matcher *New = 0;
  38     if (RecordMatcher *RM = dyn_cast<RecordMatcher>(MC->getNext()))
  39       New = new RecordChildMatcher(MC->getChildNo(), RM->getWhatFor());
  40
  41     if (CheckTypeMatcher *CT= dyn_cast<CheckTypeMatcher>(MC->getNext()))
  42       New = new CheckChildTypeMatcher(MC->getChildNo(), CT->getType());
  43
  44     if (New) {
  45       // Insert the new node.
  46       New->setNext(MatcherPtr.take());
  47       MatcherPtr.reset(New);
  48       // Remove the old one.
  49       MC->setNext(MC->getNext()->takeNext());
  50       return ContractNodes(MatcherPtr);
  51     }
  52   }
  53
  54   if (MoveChildMatcher *MC = dyn_cast<MoveChildMatcher>(N))
  55     if (MoveParentMatcher *MP =
  56           dyn_cast<MoveParentMatcher>(MC->getNext())) {
  57       MatcherPtr.reset(MP->takeNext());
  58       return ContractNodes(MatcherPtr);
  59     }
  60
  61   ContractNodes(N->getNextPtr());
  62 }
  63
  64 static void FactorNodes(OwningPtr<Matcher> &MatcherPtr) {
  65   // If we reached the end of the chain, we're done.
  66   Matcher *N = MatcherPtr.get();
  67   if (N == 0) return;
  68
  69   // If this is not a push node, just scan for one.
  70   ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N);
  71   if (Scope == 0)
  72     return FactorNodes(N->getNextPtr());
  73
  74   // Okay, pull together the children of the scope node into a vector so we can
  75   // inspect it more easily.  While we're at it, bucket them up by the hash
  76   // code of their first predicate.
  77   SmallVector<Matcher*, 32> OptionsToMatch;
  78   typedef DenseMap<unsigned, std::vector<Matcher*> > HashTableTy;
  79   HashTableTy MatchersByHash;
  80
  81   for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) {
  82     // Factor the subexpression.
  83     OwningPtr<Matcher> Child(Scope->takeChild(i));
  84     FactorNodes(Child);
  85
  86     if (Matcher *N = Child.take()) {
  87       OptionsToMatch.push_back(N);
  88       MatchersByHash[N->getHash()].push_back(N);
  89     }
  90   }
  91
  92   SmallVector<Matcher*, 32> NewOptionsToMatch;
  93
  94   // Now that we have bucketed up things by hash code, iterate over sets of
  95   // matchers that all start with the same node.  We would like to iterate over
  96   // the hash table, but it isn't in deterministic order, emulate this by going
  97   // about this slightly backwards.  After each set of nodes is processed, we
  98   // remove them from MatchersByHash.
  99   for (unsigned i = 0, e = OptionsToMatch.size();
 100        i != e && !MatchersByHash.empty(); ++i) {
 101     // Find the set of matchers that start with this node.
 102     Matcher *Optn = OptionsToMatch[i];
 103
 104     // Find all nodes that hash to the same value.  If there is no entry in the
 105     // hash table, then we must have previously processed a node equal to this
 106     // one.
 107     HashTableTy::iterator DMI = MatchersByHash.find(Optn->getHash());
 108     if (DMI == MatchersByHash.end()) {
 109       delete Optn;
 110       continue;
 111     }
 112
 113     std::vector<Matcher*> &HashMembers = DMI->second;
 114     assert(!HashMembers.empty() && "Should be removed if empty");
 115
 116     // Check to see if this node is in HashMembers, if not it was equal to a
 117     // previous node and removed.
 118     std::vector<Matcher*>::iterator MemberSlot =
 119       std::find(HashMembers.begin(), HashMembers.end(), Optn);
 120     if (MemberSlot == HashMembers.end()) {
 121       delete Optn;
 122       continue;
 123     }
 124
 125     // If the node *does* exist in HashMembers, then we've confirmed that it
 126     // hasn't been processed as equal to a previous node.  Process it now, start
 127     // by removing it from the list of hash-equal nodes.
 128     HashMembers.erase(MemberSlot);
 129
 130     // Scan all of the hash members looking for ones that are equal, removing
 131     // them from HashMembers, adding them to EqualMatchers.
 132     SmallVector<Matcher*, 8> EqualMatchers;
 133
 134     // Scan the vector backwards so we're generally removing from the end to
 135     // avoid pointless data copying.
 136     for (unsigned i = HashMembers.size(); i != 0; --i) {
 137       if (!HashMembers[i-1]->isEqual(Optn)) continue;
 138
 139       EqualMatchers.push_back(HashMembers[i-1]);
 140       HashMembers.erase(HashMembers.begin()+i-1);
 141     }
 142     EqualMatchers.push_back(Optn);
 143
 144     // Reverse the vector so that we preserve the match ordering.
 145     std::reverse(EqualMatchers.begin(), EqualMatchers.end());
 146
 147     // If HashMembers is empty at this point, then we've gotten all nodes with
 148     // the same hash, nuke the entry in the hash table.
 149     if (HashMembers.empty())
 150       MatchersByHash.erase(Optn->getHash());
 151
 152     // Okay, we have the list of all matchers that start with the same node as
 153     // Optn.  If there is more than one in the set, we want to factor them.
 154     if (EqualMatchers.size() == 1) {
 155       NewOptionsToMatch.push_back(Optn);
 156       continue;
 157     }
 158
 159     // Factor these checks by pulling the first node off each entry and
 160     // discarding it.  Take the first one off the first entry to reuse.
 161     Matcher *Shared = Optn;
 162     Optn = Optn->takeNext();
 163     EqualMatchers[0] = Optn;
 164
 165     // Skip the first node.  Leave the first node around though, we'll delete it
 166     // on subsequent iterations over OptionsToMatch.
 167     for (unsigned i = 1, e = EqualMatchers.size(); i != e; ++i)
 168       EqualMatchers[i] = EqualMatchers[i]->takeNext();
 169
 170     Shared->setNext(new ScopeMatcher(&EqualMatchers[0], EqualMatchers.size()));
 171
 172     // Recursively factor the newly created node.
 173     FactorNodes(Shared->getNextPtr());
 174
 175     NewOptionsToMatch.push_back(Shared);
 176   }
 177
 178   // Reassemble a new Scope node.
 179   assert(!NewOptionsToMatch.empty() && "where'd all our children go?");
 180   if (NewOptionsToMatch.size() == 1)
 181     MatcherPtr.reset(NewOptionsToMatch[0]);
 182   else {
 183     Scope->setNumChildren(NewOptionsToMatch.size());
 184     for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i)
 185       Scope->resetChild(i, NewOptionsToMatch[i]);
 186   }
 187 }
 188
 189 Matcher *llvm::OptimizeMatcher(Matcher *TheMatcher) {
 190   OwningPtr<Matcher> MatcherPtr(TheMatcher);
 191   ContractNodes(MatcherPtr);
 192   FactorNodes(MatcherPtr);
 193   return MatcherPtr.take();
 194 }