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 both edges.
  25   if (ScopeMatcher *Push = dyn_cast<ScopeMatcher>(N))
  26     ContractNodes(Push->getCheckPtr());
  27
  28   // If we found a movechild node with a node that comes in a 'foochild' form,
  29   // transform it.
  30   if (MoveChildMatcher *MC = dyn_cast<MoveChildMatcher>(N)) {
  31     Matcher *New = 0;
  32     if (RecordMatcher *RM = dyn_cast<RecordMatcher>(MC->getNext()))
  33       New = new RecordChildMatcher(MC->getChildNo(), RM->getWhatFor());
  34
  35     if (CheckTypeMatcher *CT= dyn_cast<CheckTypeMatcher>(MC->getNext()))
  36       New = new CheckChildTypeMatcher(MC->getChildNo(), CT->getType());
  37
  38     if (New) {
  39       // Insert the new node.
  40       New->setNext(MatcherPtr.take());
  41       MatcherPtr.reset(New);
  42       // Remove the old one.
  43       MC->setNext(MC->getNext()->takeNext());
  44       return ContractNodes(MatcherPtr);
  45     }
  46   }
  47
  48   if (MoveChildMatcher *MC = dyn_cast<MoveChildMatcher>(N))
  49     if (MoveParentMatcher *MP =
  50           dyn_cast<MoveParentMatcher>(MC->getNext())) {
  51       MatcherPtr.reset(MP->takeNext());
  52       return ContractNodes(MatcherPtr);
  53     }
  54
  55   ContractNodes(N->getNextPtr());
  56 }
  57
  58 static void FactorNodes(OwningPtr<Matcher> &MatcherPtr) {
  59   // If we reached the end of the chain, we're done.
  60   Matcher *N = MatcherPtr.get();
  61   if (N == 0) return;
  62
  63   // If this is not a push node, just scan for one.
  64   if (!isa<ScopeMatcher>(N))
  65     return FactorNodes(N->getNextPtr());
  66
  67   // Okay, pull together the series of linear push nodes into a vector so we can
  68   // inspect it more easily.  While we're at it, bucket them up by the hash
  69   // code of their first predicate.
  70   SmallVector<Matcher*, 32> OptionsToMatch;
  71   typedef DenseMap<unsigned, std::vector<Matcher*> > HashTableTy;
  72   HashTableTy MatchersByHash;
  73
  74   Matcher *CurNode = N;
  75   for (; ScopeMatcher *PMN = dyn_cast<ScopeMatcher>(CurNode);
  76        CurNode = PMN->getNext()) {
  77     // Factor the subexpression.
  78     FactorNodes(PMN->getCheckPtr());
  79     if (Matcher *Check = PMN->getCheck()) {
  80       OptionsToMatch.push_back(Check);
  81       MatchersByHash[Check->getHash()].push_back(Check);
  82     }
  83   }
  84
  85   if (CurNode) {
  86     OptionsToMatch.push_back(CurNode);
  87     MatchersByHash[CurNode->getHash()].push_back(CurNode);
  88   }
  89
  90
  91   SmallVector<Matcher*, 32> NewOptionsToMatch;
  92
  93   // Now that we have bucketed up things by hash code, iterate over sets of
  94   // matchers that all start with the same node.  We would like to iterate over
  95   // the hash table, but it isn't in deterministic order, emulate this by going
  96   // about this slightly backwards.  After each set of nodes is processed, we
  97   // remove them from MatchersByHash.
  98   for (unsigned i = 0, e = OptionsToMatch.size();
  99        i != e && !MatchersByHash.empty(); ++i) {
 100     // Find the set of matchers that start with this node.
 101     Matcher *Optn = OptionsToMatch[i];
 102
 103     // Find all nodes that hash to the same value.  If there is no entry in the
 104     // hash table, then we must have previously processed a node equal to this
 105     // one.
 106     HashTableTy::iterator DMI = MatchersByHash.find(Optn->getHash());
 107     if (DMI == MatchersByHash.end()) continue;
 108
 109     std::vector<Matcher*> &HashMembers = DMI->second;
 110     assert(!HashMembers.empty() && "Should be removed if empty");
 111
 112     // Check to see if this node is in HashMembers, if not it was equal to a
 113     // previous node and removed.
 114     std::vector<Matcher*>::iterator MemberSlot =
 115       std::find(HashMembers.begin(), HashMembers.end(), Optn);
 116     if (MemberSlot == HashMembers.end()) continue;
 117
 118     // If the node *does* exist in HashMembers, then we've confirmed that it
 119     // hasn't been processed as equal to a previous node.  Process it now, start
 120     // by removing it from the list of hash-equal nodes.
 121     HashMembers.erase(MemberSlot);
 122
 123     // Scan all of the hash members looking for ones that are equal, removing
 124     // them from HashMembers, adding them to EqualMatchers.
 125     SmallVector<Matcher*, 8> EqualMatchers;
 126
 127     // Scan the vector backwards so we're generally removing from the end to
 128     // avoid pointless data copying.
 129     for (unsigned i = HashMembers.size(); i != 0; --i) {
 130       if (!HashMembers[i-1]->isEqual(Optn)) continue;
 131
 132       EqualMatchers.push_back(HashMembers[i-1]);
 133       HashMembers.erase(HashMembers.begin()+i-1);
 134     }
 135     EqualMatchers.push_back(Optn);
 136
 137     // Reverse the vector so that we preserve the match ordering.
 138     std::reverse(EqualMatchers.begin(), EqualMatchers.end());
 139
 140     // If HashMembers is empty at this point, then we've gotten all nodes with
 141     // the same hash, nuke the entry in the hash table.
 142     if (HashMembers.empty())
 143       MatchersByHash.erase(Optn->getHash());
 144
 145     // Okay, we have the list of all matchers that start with the same node as
 146     // Optn.  If there is more than one in the set, we want to factor them.
 147     if (EqualMatchers.size() == 1) {
 148       NewOptionsToMatch.push_back(Optn);
 149       continue;
 150     }
 151
 152     // Factor these checks by pulling the first node off each entry and
 153     // discarding it, replacing it with...
 154     // something amazing??
 155
 156     // FIXME: Need to change the Scope model.
 157   }
 158
 159   // Reassemble a new Scope node.
 160
 161 }
 162
 163 Matcher *llvm::OptimizeMatcher(Matcher *TheMatcher) {
 164   OwningPtr<Matcher> MatcherPtr(TheMatcher);
 165   ContractNodes(MatcherPtr);
 166   FactorNodes(MatcherPtr);
 167   return MatcherPtr.take();
 168 }