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 using namespace llvm;
  16
  17 static void ContractNodes(OwningPtr<MatcherNode> &MatcherPtr) {
  18   // If we reached the end of the chain, we're done.
  19   MatcherNode *N = MatcherPtr.get();
  20   if (N == 0) return;
  21
  22   // If we have a scope node, walk down both edges.
  23   if (ScopeMatcherNode *Push = dyn_cast<ScopeMatcherNode>(N))
  24     ContractNodes(Push->getCheckPtr());
  25
  26   // If we found a movechild node with a node that comes in a 'foochild' form,
  27   // transform it.
  28   if (MoveChildMatcherNode *MC = dyn_cast<MoveChildMatcherNode>(N)) {
  29     MatcherNode *New = 0;
  30     if (RecordMatcherNode *RM = dyn_cast<RecordMatcherNode>(MC->getNext()))
  31       New = new RecordChildMatcherNode(MC->getChildNo(), RM->getWhatFor());
  32
  33     if (CheckTypeMatcherNode *CT= dyn_cast<CheckTypeMatcherNode>(MC->getNext()))
  34       New = new CheckChildTypeMatcherNode(MC->getChildNo(), CT->getType());
  35
  36     if (New) {
  37       // Insert the new node.
  38       New->setNext(MatcherPtr.take());
  39       MatcherPtr.reset(New);
  40       // Remove the old one.
  41       MC->setNext(MC->getNext()->takeNext());
  42       return ContractNodes(MatcherPtr);
  43     }
  44   }
  45
  46   if (MoveChildMatcherNode *MC = dyn_cast<MoveChildMatcherNode>(N))
  47     if (MoveParentMatcherNode *MP =
  48           dyn_cast<MoveParentMatcherNode>(MC->getNext())) {
  49       MatcherPtr.reset(MP->takeNext());
  50       return ContractNodes(MatcherPtr);
  51     }
  52
  53   ContractNodes(N->getNextPtr());
  54 }
  55
  56 static void FactorNodes(OwningPtr<MatcherNode> &MatcherPtr) {
  57   // If we reached the end of the chain, we're done.
  58   MatcherNode *N = MatcherPtr.get();
  59   if (N == 0) return;
  60
  61   // If this is not a push node, just scan for one.
  62   if (!isa<ScopeMatcherNode>(N))
  63     return FactorNodes(N->getNextPtr());
  64
  65   // Okay, pull together the series of linear push nodes into a vector so we can
  66   // inspect it more easily.
  67   SmallVector<MatcherNode*, 32> OptionsToMatch;
  68
  69   MatcherNode *CurNode = N;
  70   for (; ScopeMatcherNode *PMN = dyn_cast<ScopeMatcherNode>(CurNode);
  71        CurNode = PMN->getNext())
  72     OptionsToMatch.push_back(PMN->getCheck());
  73   OptionsToMatch.push_back(CurNode);
  74
  75
  76 }
  77
  78 MatcherNode *llvm::OptimizeMatcher(MatcherNode *Matcher) {
  79   OwningPtr<MatcherNode> MatcherPtr(Matcher);
  80   ContractNodes(MatcherPtr);
  81   FactorNodes(MatcherPtr);
  82   return MatcherPtr.take();
  83 }