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     // FIXME: Eventually don't pass ownership back to the scope node.
  87     Scope->resetChild(i, Child.take());
  88
  89     if (Matcher *N = Scope->getChild(i)) {
  90       OptionsToMatch.push_back(N);
  91       MatchersByHash[N->getHash()].push_back(N);
  92     }
  93   }
  94
  95
  96   SmallVector<Matcher*, 32> NewOptionsToMatch;
  97
  98   // Now that we have bucketed up things by hash code, iterate over sets of
  99   // matchers that all start with the same node.  We would like to iterate over
 100   // the hash table, but it isn't in deterministic order, emulate this by going
 101   // about this slightly backwards.  After each set of nodes is processed, we
 102   // remove them from MatchersByHash.
 103   for (unsigned i = 0, e = OptionsToMatch.size();
 104        i != e && !MatchersByHash.empty(); ++i) {
 105     // Find the set of matchers that start with this node.
 106     Matcher *Optn = OptionsToMatch[i];
 107
 108     // Find all nodes that hash to the same value.  If there is no entry in the
 109     // hash table, then we must have previously processed a node equal to this
 110     // one.
 111     HashTableTy::iterator DMI = MatchersByHash.find(Optn->getHash());
 112     if (DMI == MatchersByHash.end()) continue;
 113
 114     std::vector<Matcher*> &HashMembers = DMI->second;
 115     assert(!HashMembers.empty() && "Should be removed if empty");
 116
 117     // Check to see if this node is in HashMembers, if not it was equal to a
 118     // previous node and removed.
 119     std::vector<Matcher*>::iterator MemberSlot =
 120       std::find(HashMembers.begin(), HashMembers.end(), Optn);
 121     if (MemberSlot == HashMembers.end()) continue;
 122
 123     // If the node *does* exist in HashMembers, then we've confirmed that it
 124     // hasn't been processed as equal to a previous node.  Process it now, start
 125     // by removing it from the list of hash-equal nodes.
 126     HashMembers.erase(MemberSlot);
 127
 128     // Scan all of the hash members looking for ones that are equal, removing
 129     // them from HashMembers, adding them to EqualMatchers.
 130     SmallVector<Matcher*, 8> EqualMatchers;
 131
 132     // Scan the vector backwards so we're generally removing from the end to
 133     // avoid pointless data copying.
 134     for (unsigned i = HashMembers.size(); i != 0; --i) {
 135       if (!HashMembers[i-1]->isEqual(Optn)) continue;
 136
 137       EqualMatchers.push_back(HashMembers[i-1]);
 138       HashMembers.erase(HashMembers.begin()+i-1);
 139     }
 140     EqualMatchers.push_back(Optn);
 141
 142     // Reverse the vector so that we preserve the match ordering.
 143     std::reverse(EqualMatchers.begin(), EqualMatchers.end());
 144
 145     // If HashMembers is empty at this point, then we've gotten all nodes with
 146     // the same hash, nuke the entry in the hash table.
 147     if (HashMembers.empty())
 148       MatchersByHash.erase(Optn->getHash());
 149
 150     // Okay, we have the list of all matchers that start with the same node as
 151     // Optn.  If there is more than one in the set, we want to factor them.
 152     if (EqualMatchers.size() == 1) {
 153       NewOptionsToMatch.push_back(Optn);
 154       continue;
 155     }
 156
 157     // Factor these checks by pulling the first node off each entry and
 158     // discarding it, replacing it with...
 159     // something amazing??
 160
 161     // FIXME: Need to change the Scope model.
 162   }
 163
 164   // Reassemble a new Scope node.
 165
 166 }
 167
 168 Matcher *llvm::OptimizeMatcher(Matcher *TheMatcher) {
 169   OwningPtr<Matcher> MatcherPtr(TheMatcher);
 170   ContractNodes(MatcherPtr);
 171   FactorNodes(MatcherPtr);
 172   return MatcherPtr.take();
 173 }