path: root/utils/TableGen/DAGISelMatcherGen.cpp

//===- DAGISelMatcherGen.cpp - Matcher generator --------------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//

#include "DAGISelMatcher.h"
#include "CodeGenDAGPatterns.h"
#include "Record.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringMap.h"
using namespace llvm;

namespace {
  class MatcherGen {
    const PatternToMatch &Pattern;
    const CodeGenDAGPatterns &CGP;
    
    /// PatWithNoTypes - This is a clone of Pattern.getSrcPattern() that starts
    /// out with all of the types removed.  This allows us to insert type checks
    /// as we scan the tree.
    TreePatternNode *PatWithNoTypes;
    
    /// VariableMap - A map from variable names ('$dst') to the recorded operand
    /// number that they were captured as.  These are biased by 1 to make
    /// insertion easier.
    StringMap<unsigned> VariableMap;
    unsigned NextRecordedOperandNo;
    
    /// InputChains - This maintains the position in the recorded nodes array of
    /// all of the recorded input chains.
    SmallVector<unsigned, 2> InputChains;
    
    /// Matcher - This is the top level of the generated matcher, the result.
    MatcherNode *Matcher;
    
    /// CurPredicate - As we emit matcher nodes, this points to the latest check
    /// which should have future checks stuck into its Next position.
    MatcherNode *CurPredicate;
  public:
    MatcherGen(const PatternToMatch &pattern, const CodeGenDAGPatterns &cgp);
    
    ~MatcherGen() {
      delete PatWithNoTypes;
    }
    
    void EmitMatcherCode();
    void EmitResultCode();
    
    MatcherNode *GetMatcher() const { return Matcher; }
    MatcherNode *GetCurPredicate() const { return CurPredicate; }
  private:
    void AddMatcherNode(MatcherNode *NewNode);
    void InferPossibleTypes();
    
    // Matcher Generation.
    void EmitMatchCode(const TreePatternNode *N, TreePatternNode *NodeNoTypes);
    void EmitLeafMatchCode(const TreePatternNode *N);
    void EmitOperatorMatchCode(const TreePatternNode *N,
                               TreePatternNode *NodeNoTypes);
    
    // Result Code Generation.
    void EmitResultOperand(const TreePatternNode *N,
                           SmallVectorImpl<unsigned> &ResultOps);
    void EmitResultLeafAsOperand(const TreePatternNode *N,
                                 SmallVectorImpl<unsigned> &ResultOps);
    void EmitResultInstructionAsOperand(const TreePatternNode *N,
                                        SmallVectorImpl<unsigned> &ResultOps);
  };
  
} // end anon namespace.

MatcherGen::MatcherGen(const PatternToMatch &pattern,
                       const CodeGenDAGPatterns &cgp)
: Pattern(pattern), CGP(cgp), NextRecordedOperandNo(0),
  Matcher(0), CurPredicate(0) {
  // We need to produce the matcher tree for the patterns source pattern.  To do
  // this we need to match the structure as well as the types.  To do the type
  // matching, we want to figure out the fewest number of type checks we need to
  // emit.  For example, if there is only one integer type supported by a
  // target, there should be no type comparisons at all for integer patterns!
  //
  // To figure out the fewest number of type checks needed, clone the pattern,
  // remove the types, then perform type inference on the pattern as a whole.
  // If there are unresolved types, emit an explicit check for those types,
  // apply the type to the tree, then rerun type inference.  Iterate until all
  // types are resolved.
  //
  PatWithNoTypes = Pattern.getSrcPattern()->clone();
  PatWithNoTypes->RemoveAllTypes();
    
  // If there are types that are manifestly known, infer them.
  InferPossibleTypes();
}

/// InferPossibleTypes - As we emit the pattern, we end up generating type
/// checks and applying them to the 'PatWithNoTypes' tree.  As we do this, we
/// want to propagate implied types as far throughout the tree as possible so
/// that we avoid doing redundant type checks.  This does the type propagation.
void MatcherGen::InferPossibleTypes() {
  // TP - Get *SOME* tree pattern, we don't care which.  It is only used for
  // diagnostics, which we know are impossible at this point.
  TreePattern &TP = *CGP.pf_begin()->second;
  
  try {
    bool MadeChange = true;
    while (MadeChange)
      MadeChange = PatWithNoTypes->ApplyTypeConstraints(TP,
                                                true/*Ignore reg constraints*/);
  } catch (...) {
    errs() << "Type constraint application shouldn't fail!";
    abort();
  }
}


/// AddMatcherNode - Add a matcher node to the current graph we're building. 
void MatcherGen::AddMatcherNode(MatcherNode *NewNode) {
  if (CurPredicate != 0)
    CurPredicate->setNext(NewNode);
  else
    Matcher = NewNode;
  CurPredicate = NewNode;
}


//===----------------------------------------------------------------------===//
// Pattern Match Generation
//===----------------------------------------------------------------------===//

/// EmitLeafMatchCode - Generate matching code for leaf nodes.
void MatcherGen::EmitLeafMatchCode(const TreePatternNode *N) {
  assert(N->isLeaf() && "Not a leaf?");
  // Direct match against an integer constant.
  if (IntInit *II = dynamic_cast<IntInit*>(N->getLeafValue()))
    return AddMatcherNode(new CheckIntegerMatcherNode(II->getValue()));
  
  DefInit *DI = dynamic_cast<DefInit*>(N->getLeafValue());
  if (DI == 0) {
    errs() << "Unknown leaf kind: " << *DI << "\n";
    abort();
  }
  
  Record *LeafRec = DI->getDef();
  if (// Handle register references.  Nothing to do here, they always match.
      LeafRec->isSubClassOf("RegisterClass") || 
      LeafRec->isSubClassOf("PointerLikeRegClass") ||
      LeafRec->isSubClassOf("Register") ||
      // Place holder for SRCVALUE nodes. Nothing to do here.
      LeafRec->getName() == "srcvalue")
    return;
  
  if (LeafRec->isSubClassOf("ValueType"))
    return AddMatcherNode(new CheckValueTypeMatcherNode(LeafRec->getName()));
  
  if (LeafRec->isSubClassOf("CondCode"))
    return AddMatcherNode(new CheckCondCodeMatcherNode(LeafRec->getName()));
  
  if (LeafRec->isSubClassOf("ComplexPattern")) {
    // We can't model ComplexPattern uses that don't have their name taken yet.
    // The OPC_CheckComplexPattern operation implicitly records the results.
    if (N->getName().empty()) {
      errs() << "We expect complex pattern uses to have names: " << *N << "\n";
      exit(1);
    }
    
    // Handle complex pattern.
    const ComplexPattern &CP = CGP.getComplexPattern(LeafRec);
    AddMatcherNode(new CheckComplexPatMatcherNode(CP));
    
    // If the complex pattern has a chain, then we need to keep track of the
    // fact that we just recorded a chain input.  The chain input will be
    // matched as the last operand of the predicate if it was successful.
    if (CP.hasProperty(SDNPHasChain)) {
      // It is the last operand recorded.
      assert(NextRecordedOperandNo > 1 &&
             "Should have recorded input/result chains at least!");
      InputChains.push_back(NextRecordedOperandNo-1);

      // IF we need to check chains, do so, see comment for
      // "NodeHasProperty(SDNPHasChain" below.
      if (InputChains.size() > 1) {
        // FIXME: This is broken, we should eliminate this nonsense completely,
        // but we want to produce the same selections that the old matcher does
        // for now.
        unsigned PrevOp = InputChains[InputChains.size()-2];
        AddMatcherNode(new CheckChainCompatibleMatcherNode(PrevOp));
      }
    }
    return;
  }
  
  errs() << "Unknown leaf kind: " << *N << "\n";
  abort();
}

void MatcherGen::EmitOperatorMatchCode(const TreePatternNode *N,
                                       TreePatternNode *NodeNoTypes) {
  assert(!N->isLeaf() && "Not an operator?");
  const SDNodeInfo &CInfo = CGP.getSDNodeInfo(N->getOperator());
  
  // If this is an 'and R, 1234' where the operation is AND/OR and the RHS is
  // a constant without a predicate fn that has more that one bit set, handle
  // this as a special case.  This is usually for targets that have special
  // handling of certain large constants (e.g. alpha with it's 8/16/32-bit
  // handling stuff).  Using these instructions is often far more efficient
  // than materializing the constant.  Unfortunately, both the instcombiner
  // and the dag combiner can often infer that bits are dead, and thus drop
  // them from the mask in the dag.  For example, it might turn 'AND X, 255'
  // into 'AND X, 254' if it knows the low bit is set.  Emit code that checks
  // to handle this.
  if ((N->getOperator()->getName() == "and" || 
       N->getOperator()->getName() == "or") &&
      N->getChild(1)->isLeaf() && N->getChild(1)->getPredicateFns().empty()) {
    if (IntInit *II = dynamic_cast<IntInit*>(N->getChild(1)->getLeafValue())) {
      if (!isPowerOf2_32(II->getValue())) {  // Don't bother with single bits.
        if (N->getOperator()->getName