utils/TableGen/DAGISelEmitter.cpp

   1 //===- DAGISelEmitter.cpp - Generate an instruction selector --------------===//
   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 tablegen backend emits a DAG instruction selector.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "DAGISelEmitter.h"
  15 #include "DAGISelMatcher.h"
  16 #include "Record.h"
  17 #include "llvm/ADT/StringExtras.h"
  18 #include "llvm/Support/CommandLine.h"
  19 #include "llvm/Support/Debug.h"
  20 #include "llvm/Support/MathExtras.h"
  21 #include "llvm/Support/Debug.h"
  22 #include <algorithm>
  23 #include <deque>
  24 #include <iostream>
  25 using namespace llvm;
  26
  27 //#define ENABLE_NEW_ISEL
  28
  29
  30 static cl::opt<bool>
  31 GenDebug("gen-debug", cl::desc("Generate debug code"), cl::init(false));
  32
  33 //===----------------------------------------------------------------------===//
  34 // DAGISelEmitter Helper methods
  35 //
  36
  37 /// getNodeName - The top level Select_* functions have an "SDNode* N"
  38 /// argument. When expanding the pattern-matching code, the intermediate
  39 /// variables have type SDValue. This function provides a uniform way to
  40 /// reference the underlying "SDNode *" for both cases.
  41 static std::string getNodeName(const std::string &S) {
  42   if (S == "N") return S;
  43   return S + ".getNode()";
  44 }
  45
  46 /// getNodeValue - Similar to getNodeName, except it provides a uniform
  47 /// way to access the SDValue for both cases.
  48 static std::string getValueName(const std::string &S) {
  49   if (S == "N") return "SDValue(N, 0)";
  50   return S;
  51 }
  52
  53 /// getPatternSize - Return the 'size' of this pattern.  We want to match large
  54 /// patterns before small ones.  This is used to determine the size of a
  55 /// pattern.
  56 static unsigned getPatternSize(TreePatternNode *P, CodeGenDAGPatterns &CGP) {
  57   assert((EEVT::isExtIntegerInVTs(P->getExtTypes()) ||
  58           EEVT::isExtFloatingPointInVTs(P->getExtTypes()) ||
  59           P->getExtTypeNum(0) == MVT::isVoid ||
  60           P->getExtTypeNum(0) == MVT::Flag ||
  61           P->getExtTypeNum(0) == MVT::iPTR ||
  62           P->getExtTypeNum(0) == MVT::iPTRAny) &&
  63          "Not a valid pattern node to size!");
  64   unsigned Size = 3;  // The node itself.
  65   // If the root node is a ConstantSDNode, increases its size.
  66   // e.g. (set R32:$dst, 0).
  67   if (P->isLeaf() && dynamic_cast<IntInit*>(P->getLeafValue()))
  68     Size += 2;
  69
  70   // FIXME: This is a hack to statically increase the priority of patterns
  71   // which maps a sub-dag to a complex pattern. e.g. favors LEA over ADD.
  72   // Later we can allow complexity / cost for each pattern to be (optionally)
  73   // specified. To get best possible pattern match we'll need to dynamically
  74   // calculate the complexity of all patterns a dag can potentially map to.
  75   const ComplexPattern *AM = P->getComplexPatternInfo(CGP);
  76   if (AM)
  77     Size += AM->getNumOperands() * 3;
  78
  79   // If this node has some predicate function that must match, it adds to the
  80   // complexity of this node.
  81   if (!P->getPredicateFns().empty())
  82     ++Size;
  83
  84   // Count children in the count if they are also nodes.
  85   for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i) {
  86     TreePatternNode *Child = P->getChild(i);
  87     if (!Child->isLeaf() && Child->getExtTypeNum(0) != MVT::Other)
  88       Size += getPatternSize(Child, CGP);
  89     else if (Child->isLeaf()) {
  90       if (dynamic_cast<IntInit*>(Child->getLeafValue()))
  91         Size += 5;  // Matches a ConstantSDNode (+3) and a specific value (+2).
  92       else if (Child->getComplexPatternInfo(CGP))
  93         Size += getPatternSize(Child, CGP);
  94       else if (!Child->getPredicateFns().empty())
  95         ++Size;
  96     }
  97   }
  98
  99   return Size;
 100 }
 101
 102 /// getResultPatternCost - Compute the number of instructions for this pattern.
 103 /// This is a temporary hack.  We should really include the instruction
 104 /// latencies in this calculation.
 105 static unsigned getResultPatternCost(TreePatternNode *P,
 106                                      CodeGenDAGPatterns &CGP) {
 107   if (P->isLeaf()) return 0;
 108
 109   unsigned Cost = 0;
 110   Record *Op = P->getOperator();
 111   if (Op->isSubClassOf("Instruction")) {
 112     Cost++;
 113     CodeGenInstruction &II = CGP.getTargetInfo().getInstruction(Op->getName());
 114     if (II.usesCustomInserter)
 115       Cost += 10;
 116   }
 117   for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i)
 118     Cost += getResultPatternCost(P->getChild(i), CGP);
 119   return Cost;
 120 }
 121
 122 /// getResultPatternCodeSize - Compute the code size of instructions for this
 123 /// pattern.
 124 static unsigned getResultPatternSize(TreePatternNode *P,
 125                                      CodeGenDAGPatterns &CGP) {
 126   if (P->isLeaf()) return 0;
 127
 128   unsigned Cost = 0;
 129   Record *Op = P->getOperator();
 130   if (Op->isSubClassOf("Instruction")) {
 131     Cost += Op->getValueAsInt("CodeSize");
 132   }
 133   for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i)
 134     Cost += getResultPatternSize(P->getChild(i), CGP);
 135   return Cost;
 136 }
 137
 138 // PatternSortingPredicate - return true if we prefer to match LHS before RHS.
 139 // In particular, we want to match maximal patterns first and lowest cost within
 140 // a particular complexity first.
 141 struct PatternSortingPredicate {
 142   PatternSortingPredicate(CodeGenDAGPatterns &cgp) : CGP(cgp) {}
 143   CodeGenDAGPatterns &CGP;
 144
 145   typedef std::pair<unsigned, std::string> CodeLine;
 146   typedef std::vector<CodeLine> CodeList;
 147
 148   bool operator()(const std::pair<const PatternToMatch*, CodeList> &LHSPair,
 149                   const std::pair<const PatternToMatch*, CodeList> &RHSPair) {
 150     const PatternToMatch *LHS = LHSPair.first;
 151     const PatternToMatch *RHS = RHSPair.first;
 152
 153     unsigned LHSSize = getPatternSize(LHS->getSrcPattern(), CGP);
 154     unsigned RHSSize = getPatternSize(RHS->getSrcPattern(), CGP);
 155     LHSSize += LHS->getAddedComplexity();
 156     RHSSize += RHS->getAddedComplexity();
 157     if (LHSSize > RHSSize) return true;   // LHS -> bigger -> less cost
 158     if (LHSSize < RHSSize) return false;
 159
 160     // If the patterns have equal complexity, compare generated instruction cost
 161     unsigned LHSCost = getResultPatternCost(LHS->getDstPattern(), CGP);
 162     unsigned RHSCost = getResultPatternCost(RHS->getDstPattern(), CGP);
 163     if (LHSCost < RHSCost) return true;
 164     if (LHSCost > RHSCost) return false;
 165
 166     return getResultPatternSize(LHS->getDstPattern(), CGP) <
 167       getResultPatternSize(RHS->getDstPattern(), CGP);
 168   }
 169 };
 170
 171 /// getRegisterValueType - Look up and return the ValueType of the specified
 172 /// register. If the register is a member of multiple register classes which
 173 /// have different associated types, return MVT::Other.
 174 static MVT::SimpleValueType getRegisterValueType(Record *R,
 175                                                  const CodeGenTarget &T) {
 176   bool FoundRC = false;
 177   MVT::SimpleValueType VT = MVT::Other;
 178   const std::vector<CodeGenRegisterClass> &RCs = T.getRegisterClasses();
 179   std::vector<CodeGenRegisterClass>::const_iterator RC;
 180   std::vector<Record*>::const_iterator Element;
 181
 182   for (RC = RCs.begin() ; RC != RCs.end() ; RC++) {
 183     Element = find((*RC).Elements.begin(), (*RC).Elements.end(), R);
 184     if (Element != (*RC).Elements.end()) {
 185       if (!FoundRC) {
 186         FoundRC = true;
 187         VT = (*RC).getValueTypeNum(0);
 188       } else {
 189         // In multiple RC's
 190         if (VT != (*RC).getValueTypeNum(0)) {
 191           // Types of the RC's do not agree. Return MVT::Other. The
 192           // target is responsible for handling this.
 193           return MVT::Other;
 194         }
 195       }
 196     }
 197   }
 198   return VT;
 199 }
 200
 201 static std::string getOpcodeName(Record *Op, CodeGenDAGPatterns &CGP) {
 202   return CGP.getSDNodeInfo(Op).getEnumName();
 203 }
 204
 205 //===----------------------------------------------------------------------===//
 206 // Node Transformation emitter implementation.
 207 //
 208 void DAGISelEmitter::EmitNodeTransforms(raw_ostream &OS) {
 209   // Walk the pattern fragments, adding them to a map, which sorts them by
 210   // name.
 211   typedef std::map<std::string, CodeGenDAGPatterns::NodeXForm> NXsByNameTy;
 212   NXsByNameTy NXsByName;
 213
 214   for (CodeGenDAGPatterns::nx_iterator I = CGP.nx_begin(), E = CGP.nx_end();
 215        I != E; ++I)
 216     NXsByName.insert(std::make_pair(I->first->getName(), I->second));
 217
 218   OS << "\n// Node transformations.\n";
 219
 220   for (NXsByNameTy::iterator I = NXsByName.begin(), E = NXsByName.end();
 221        I != E; ++I) {
 222     Record *SDNode = I->second.first;
 223     std::string Code = I->second.second;
 224
 225     if (Code.empty()) continue;  // Empty code?  Skip it.
 226
 227     std::string ClassName = CGP.getSDNodeInfo(SDNode).getSDClassName();
 228     const char *C2 = ClassName == "SDNode" ? "N" : "inN";
 229
 230     OS << "inline SDValue Transform_" << I->first << "(SDNode *" << C2
 231        << ") {\n";
 232     if (ClassName != "SDNode")
 233       OS << "  " << ClassName << " *N = cast<" << ClassName << ">(inN);\n";
 234     OS << Code << "\n}\n";
 235   }
 236 }
 237
 238 //===----------------------------------------------------------------------===//
 239 // Predicate emitter implementation.
 240 //
 241
 242 void DAGISelEmitter::EmitPredicateFunctions(raw_ostream &OS) {
 243   OS << "\n// Predicate functions.\n";
 244
 245   // Walk the pattern fragments, adding them to a map, which sorts them by
 246   // name.
 247   typedef std::map<std::string, std::pair<Record*, TreePattern*> > PFsByNameTy;
 248   PFsByNameTy PFsByName;
 249
 250   for (CodeGenDAGPatterns::pf_iterator I = CGP.pf_begin(), E = CGP.pf_end();
 251        I != E; ++I)
 252     PFsByName.insert(std::make_pair(I->first->getName(), *I));
 253
 254
 255   for (PFsByNameTy::iterator I = PFsByName.begin(), E = PFsByName.end();
 256        I != E; ++I) {
 257     Record *PatFragRecord = I->second.first;// Record that derives from PatFrag.
 258     TreePattern *P = I->second.second;
 259
 260     // If there is a code init for this fragment, emit the predicate code.
 261     std::string Code = PatFragRecord->getValueAsCode("Predicate");
 262     if (Code.empty()) continue;
 263
 264     if (P->getOnlyTree()->isLeaf())
 265       OS << "inline bool Predicate_" << PatFragRecord->getName()
 266       << "(SDNode *N) const {\n";
 267     else {
 268       std::string ClassName =
 269         CGP.getSDNodeInfo(P->getOnlyTree()->getOperator()).getSDClassName();
 270       const char *C2 = ClassName == "SDNode" ? "N" : "inN";
 271
 272       OS << "inline bool Predicate_" << PatFragRecord->getName()
 273          << "(SDNode *" << C2 << ") const {\n";
 274       if (ClassName != "SDNode")
 275         OS << "  " << ClassName << " *N = cast<" << ClassName << ">(inN);\n";
 276     }
 277     OS << Code << "\n}\n";
 278   }
 279
 280   OS << "\n\n";
 281 }
 282
 283
 284 //===----------------------------------------------------------------------===//
 285 // PatternCodeEmitter implementation.
 286 //
 287 class PatternCodeEmitter {
 288 private:
 289   CodeGenDAGPatterns &CGP;
 290
 291   // Predicates.
 292   std::string PredicateCheck;
 293   // Pattern cost.
 294   unsigned Cost;
 295   // Instruction selector pattern.
 296   TreePatternNode *Pattern;
 297   // Matched instruction.
 298   TreePatternNode *Instruction;
 299
 300   // Node to name mapping
 301   std::map<std::string, std::string> VariableMap;
 302   // Name of the folded node which produces a flag.
 303   std::pair<std::string, unsigned> FoldedFlag;
 304   // Names of all the folded nodes which produce chains.
 305   std::vector<std::pair<std::string, unsigned> > FoldedChains;
 306   // Original input chain(s).
 307   std::vector<std::pair<std::string, std::string> > OrigChains;
 308   std::set<std::string> Duplicates;
 309
 310   /// LSI - Load/Store information.
 311   /// Save loads/stores matched by a pattern, and generate a MemOperandSDNode
 312   /// for each memory access. This facilitates the use of AliasAnalysis in
 313   /// the backend.
 314   std::vector<std::string> LSI;
 315
 316   /// GeneratedCode - This is the buffer that we emit code to.  The first int
 317   /// indicates whether this is an exit predicate (something that should be
 318   /// tested, and if true, the match fails) [when 1], or normal code to emit
 319   /// [when 0], or initialization code to emit [when 2].
 320   std::vector<std::pair<unsigned, std::string> > &GeneratedCode;
 321   /// GeneratedDecl - This is the set of all SDValue declarations needed for
 322   /// the set of patterns for each top-level opcode.
 323   std::set<std::string> &GeneratedDecl;
 324   /// TargetOpcodes - The target specific opcodes used by the resulting
 325   /// instructions.
 326   std::vector<std::string> &TargetOpcodes;
 327   std::vector<std::string> &TargetVTs;
 328   /// OutputIsVariadic - Records whether the instruction output pattern uses
 329   /// variable_ops.  This requires that the Emit function be passed an
 330   /// additional argument to indicate where the input varargs operands
 331   /// begin.
 332   bool &OutputIsVariadic;
 333   /// NumInputRootOps - Records the number of operands the root node of the
 334   /// input pattern has.  This information is used in the generated code to
 335   /// pass to Emit functions when variable_ops processing is needed.
 336   unsigned &NumInputRootOps;
 337
 338   std::string ChainName;
 339   unsigned TmpNo;
 340   unsigned OpcNo;
 341   unsigned VTNo;
 342
 343   void emitCheck(const std::string &S) {
 344     if (!S.empty())
 345       GeneratedCode.push_back(std::make_pair(1, S));
 346   }
 347   void emitCode(const std::string &S) {
 348     if (!S.empty())
 349       GeneratedCode.push_back(std::make_pair(0, S));
 350   }
 351   void emitInit(const std::string &S) {
 352     if (!S.empty())
 353       GeneratedCode.push_back(std::make_pair(2, S));
 354   }
 355   void emitDecl(const std::string &S) {
 356     assert(!S.empty() && "Invalid declaration");
 357     GeneratedDecl.insert(S);
 358   }
 359   void emitOpcode(const std::string &Opc) {
 360     TargetOpcodes.push_back(Opc);
 361     OpcNo++;
 362   }
 363   void emitVT(const std::string &VT) {
 364     TargetVTs.push_back(VT);
 365     VTNo++;
 366   }
 367 public:
 368   PatternCodeEmitter(CodeGenDAGPatterns &cgp, std::string predcheck,
 369                      TreePatternNode *pattern, TreePatternNode *instr,
 370                      std::vector<std::pair<unsigned, std::string> > &gc,
 371                      std::set<std::string> &gd,
 372                      std::vector<std::string> &to,
 373                      std::vector<std::string> &tv,
 374                      bool &oiv,
 375                      unsigned &niro)
 376   : CGP(cgp), PredicateCheck(predcheck), Pattern(pattern), Instruction(instr),
 377     GeneratedCode(gc), GeneratedDecl(gd),
 378     TargetOpcodes(to), TargetVTs(tv),
 379     OutputIsVariadic(oiv), NumInputRootOps(niro),
 380     TmpNo(0), OpcNo(0), VTNo(0) {}
 381
 382   /// EmitMatchCode - Emit a matcher for N, going to the label for PatternNo
 383   /// if the match fails. At this point, we already know that the opcode for N
 384   /// matches, and the SDNode for the result has the RootName specified name.
 385   void EmitMatchCode(TreePatternNode *N, TreePatternNode *P,
 386                      const std::string &RootName, const std::string &ChainSuffix,
 387                      bool &FoundChain);
 388
 389   void EmitChildMatchCode(TreePatternNode *Child, TreePatternNode *Parent,
 390                           const std::string &RootName,
 391                           const std::string &ChainSuffix, bool &FoundChain);
 392
 393   /// EmitResultCode - Emit the action for a pattern.  Now that it has matched
 394   /// we actually have to build a DAG!
 395   std::vector<std::string>
 396   EmitResultCode(TreePatternNode *N, std::vector<Record*> DstRegs,
 397                  bool InFlagDecled, bool ResNodeDecled,
 398                  bool LikeLeaf = false, bool isRoot = false);
 399
 400   /// InsertOneTypeCheck - Insert a type-check for an unresolved type in 'Pat'
 401   /// and add it to the tree. 'Pat' and 'Other' are isomorphic trees except that
 402   /// 'Pat' may be missing types.  If we find an unresolved type to add a check
 403   /// for, this returns true otherwise false if Pat has all types.
 404   bool InsertOneTypeCheck(TreePatternNode *Pat, TreePatternNode *Other,
 405                           const std::string &Prefix, bool isRoot = false) {
 406     // Did we find one?
 407     if (Pat->getExtTypes() != Other->getExtTypes()) {
 408       // Move a type over from 'other' to 'pat'.
 409       Pat->setTypes(Other->getExtTypes());
 410       // The top level node type is checked outside of the select function.
 411       if (!isRoot)
 412         emitCheck(Prefix + ".getValueType() == " +
 413                   getName(Pat->getTypeNum(0)));
 414       return true;
 415     }
 416
 417     unsigned OpNo = (unsigned)Pat->NodeHasProperty(SDNPHasChain, CGP);
 418     for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i, ++OpNo)
 419       if (InsertOneTypeCheck(Pat->getChild(i), Other->getChild(i),
 420                              Prefix + utostr(OpNo)))
 421         return true;
 422     return false;
 423   }
 424
 425 private:
 426   /// EmitInFlagSelectCode - Emit the flag operands for the DAG that is
 427   /// being built.
 428   void EmitInFlagSelectCode(TreePatternNode *N, const std::string &RootName,
 429                             bool &ChainEmitted, bool &InFlagDecled,
 430                             bool &ResNodeDecled, bool isRoot = false) {
 431     const CodeGenTarget &T = CGP.getTargetInfo();
 432     unsigned OpNo = (unsigned)N->NodeHasProperty(SDNPHasChain, CGP);
 433     for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i, ++OpNo) {
 434       TreePatternNode *Child = N->getChild(i);
 435       if (!Child->isLeaf()) {
 436         EmitInFlagSelectCode(Child, RootName + utostr(OpNo), ChainEmitted,
 437                              InFlagDecled, ResNodeDecled);
 438       } else {
 439         if (DefInit *DI = dynamic_cast<DefInit*>(Child->getLeafValue())) {
 440           if (!Child->getName().empty()) {
 441             std::string Name = RootName + utostr(OpNo);
 442             if (Duplicates.find(Name) != Duplicates.end())
 443               // A duplicate! Do not emit a copy for this node.
 444               continue;
 445           }
 446
 447           Record *RR = DI->getDef();
 448           if (RR->isSubClassOf("Register")) {
 449             MVT::SimpleValueType RVT = getRegisterValueType(RR, T);
 450             if (RVT == MVT::Flag) {
 451               if (!InFlagDecled) {
 452                 emitCode("SDValue InFlag = " +
 453                          getValueName(RootName + utostr(OpNo)) + ";");
 454                 InFlagDecled = true;
 455               } else
 456                 emitCode("InFlag = " +
 457                          getValueName(RootName + utostr(OpNo)) + ";");
 458             } else {
 459               if (!ChainEmitted) {
 460                 emitCode("SDValue Chain = CurDAG->getEntryNode();");
 461                 ChainName = "Chain";
 462                 ChainEmitted = true;
 463               }
 464               if (!InFlagDecled) {
 465                 emitCode("SDValue InFlag(0, 0);");
 466                 InFlagDecled = true;
 467               }
 468               std::string Decl = (!ResNodeDecled) ? "SDNode *" : "";
 469               emitCode(Decl + "ResNode = CurDAG->getCopyToReg(" + ChainName +
 470                        ", " + getNodeName(RootName) + "->getDebugLoc()" +
 471                        ", " + getQualifiedName(RR) +
 472                        ", " +  getValueName(RootName + utostr(OpNo)) +
 473                        ", InFlag).getNode();");
 474               ResNodeDecled = true;
 475               emitCode(ChainName + " = SDValue(ResNode, 0);");
 476               emitCode("InFlag = SDValue(ResNode, 1);");
 477             }
 478           }
 479         }
 480       }
 481     }
 482
 483     if (N->NodeHasProperty(SDNPInFlag, CGP)) {
 484       if (!InFlagDecled) {
 485         emitCode("SDValue InFlag = " + getNodeName(RootName) +
 486                "->getOperand(" + utostr(OpNo) + ");");
 487         InFlagDecled = true;
 488       } else
 489         abort();
 490         emitCode("InFlag = " + getNodeName(RootName) +
 491                "->getOperand(" + utostr(OpNo) + ");");
 492     }
 493   }
 494 };
 495
 496
 497 /// EmitMatchCode - Emit a matcher for N, going to the label for PatternNo
 498 /// if the match fails. At this point, we already know that the opcode for N
 499 /// matches, and the SDNode for the result has the RootName specified name.
 500 void PatternCodeEmitter::EmitMatchCode(TreePatternNode *N, TreePatternNode *P,
 501                                        const std::string &RootName,
 502                                        const std::string &ChainSuffix,
 503                                        bool &FoundChain) {
 504   // Save loads/stores matched by a pattern.
 505   if (!N->isLeaf() && N->getName().empty()) {
 506     if (N->NodeHasProperty(SDNPMemOperand, CGP))
 507       LSI.push_back(getNodeName(RootName));
 508   }
 509
 510   bool isRoot = (P == NULL);
 511   // Emit instruction predicates. Each predicate is just a string for now.
 512   if (isRoot) {
 513     // Record input varargs info.
 514     NumInputRootOps = N->getNumChildren();
 515     emitCheck(PredicateCheck);
 516   }
 517
 518   if (N->isLeaf()) {
 519     if (IntInit *II = dynamic_cast<IntInit*>(N->getLeafValue())) {
 520       emitCheck("cast<ConstantSDNode>(" + getNodeName(RootName) +
 521                 ")->getSExtValue() == INT64_C(" +
 522                 itostr(II->getValue()) + ")");
 523       return;
 524     }
 525     assert(N->getComplexPatternInfo(CGP) != 0 &&
 526            "Cannot match this as a leaf value!");
 527   }
 528
 529   // If this node has a name associated with it, capture it in VariableMap. If
 530   // we already saw this in the pattern, emit code to verify dagness.
 531   if (!N->getName().empty()) {
 532     std::string &VarMapEntry = VariableMap[N->getName()];
 533     if (VarMapEntry.empty()) {
 534       VarMapEntry = RootName;
 535     } else {
 536       // If we get here, this is a second reference to a specific name.  Since
 537       // we already have checked that the first reference is valid, we don't
 538       // have to recursively match it, just check that it's the same as the
 539       // previously named thing.
 540       emitCheck(VarMapEntry + " == " + RootName);
 541       return;
 542     }
 543   }
 544
 545
 546   // Emit code to load the child nodes and match their contents recursively.
 547   unsigned OpNo = 0;
 548   bool NodeHasChain = N->NodeHasProperty(SDNPHasChain, CGP);
 549   bool HasChain     = N->TreeHasProperty(SDNPHasChain, CGP);
 550   if (HasChain) {
 551     if (NodeHasChain)
 552       OpNo = 1;
 553     if (!isRoot) {
 554       // Check if it's profitable to fold the node. e.g. Check for multiple uses
 555       // of actual result?
 556       std::string ParentName(RootName.begin(), RootName.end()-1);
 557       if (!NodeHasChain) {
 558         // If this is just an interior node, check to see if it has a single
 559         // use.  If the node has multiple uses and the pattern has a load as
 560         // an operand, then we can't fold the load.
 561         emitCheck(getValueName(RootName) + ".hasOneUse()");
 562       } else if (!N->isLeaf()) { // ComplexPatterns do their own legality check.
 563         // If the immediate use can somehow reach this node through another
 564         // path, then can't fold it either or it will create a cycle.
 565         // e.g. In the following diagram, XX can reach ld through YY. If
 566         // ld is folded into XX, then YY is both a predecessor and a successor
 567         // of XX.
 568         //
 569         //         [ld]
 570         //         ^  ^
 571         //         |  |
 572         //        /   \---
 573         //      /        [YY]
 574         //      |         ^
 575         //     [XX]-------|
 576
 577         // We know we need the check if N's parent is not the root.
 578         bool NeedCheck = P != Pattern;
 579         if (!NeedCheck) {
 580           // If the parent is the root and the node has more than one operand,
 581           // we need to check.
 582           const SDNodeInfo &PInfo = CGP.getSDNodeInfo(P->getOperator());
 583           NeedCheck =
 584           P->getOperator() == CGP.get_intrinsic_void_sdnode() ||
 585           P->getOperator() == CGP.get_intrinsic_w_chain_sdnode() ||
 586           P->getOperator() == CGP.get_intrinsic_wo_chain_sdnode() ||
 587           PInfo.getNumOperands() > 1 ||
 588           PInfo.hasProperty(SDNPHasChain) ||
 589           PInfo.hasProperty(SDNPInFlag) ||
 590           PInfo.hasProperty(SDNPOptInFlag);
 591         }
 592
 593         if (NeedCheck) {
 594           emitCheck("IsProfitableToFold(" + getValueName(RootName) +
 595                     ", " + getNodeName(ParentName) + ", N)");
 596           emitCheck("IsLegalToFold(" + getValueName(RootName) +
 597                     ", " + getNodeName(ParentName) + ", N)");
 598         } else {
 599           // Otherwise, just verify that the node only has a single use.
 600           emitCheck(getValueName(RootName) + ".hasOneUse()");
 601         }
 602       }
 603     }
 604
 605     if (NodeHasChain) {
 606       if (FoundChain) {
 607         emitCheck("IsChainCompatible(" + ChainName + ".getNode(), " +
 608                   getNodeName(RootName) + ")");
 609         OrigChains.push_back(std::make_pair(ChainName,
 610                                             getValueName(RootName)));
 611       } else
 612         FoundChain = true;
 613       ChainName = "Chain" + ChainSuffix;
 614
 615       if (!N->getComplexPatternInfo(CGP) ||
 616           isRoot)
 617         emitInit("SDValue " + ChainName + " = " + getNodeName(RootName) +
 618                  "->getOperand(0);");
 619     }
 620   }
 621
 622   // If there are node predicates for this, emit the calls.
 623   for (unsigned i = 0, e = N->getPredicateFns().size(); i != e; ++i)
 624     emitCheck(N->getPredicateFns()[i] + "(" + getNodeName(RootName) + ")");
 625
 626   // If this is an 'and R, 1234' where the operation is AND/OR and the RHS is
 627   // a constant without a predicate fn that has more that one bit set, handle
 628   // this as a special case.  This is usually for targets that have special
 629   // handling of certain large constants (e.g. alpha with it's 8/16/32-bit
 630   // handling stuff).  Using these instructions is often far more efficient
 631   // than materializing the constant.  Unfortunately, both the instcombiner
 632   // and the dag combiner can often infer that bits are dead, and thus drop
 633   // them from the mask in the dag.  For example, it might turn 'AND X, 255'
 634   // into 'AND X, 254' if it knows the low bit is set.  Emit code that checks
 635   // to handle this.
 636   if (!N->isLeaf() &&
 637       (N->getOperator()->getName() == "and" ||
 638        N->getOperator()->getName() == "or") &&
 639       N->getChild(1)->isLeaf() &&
 640       N->getChild(1)->getPredicateFns().empty()) {
 641     if (IntInit *II = dynamic_cast<IntInit*>(N->getChild(1)->getLeafValue())) {
 642       if (!isPowerOf2_32(II->getValue())) {  // Don't bother with single bits.
 643         emitInit("SDValue " + RootName + "0" + " = " +
 644                  getNodeName(RootName) + "->getOperand(" + utostr(0) + ");");
 645         emitInit("SDValue " + RootName + "1" + " = " +
 646                  getNodeName(RootName) + "->getOperand(" + utostr(1) + ");");
 647
 648         unsigned NTmp = TmpNo++;
 649         emitCode("ConstantSDNode *Tmp" + utostr(NTmp) +
 650                  " = dyn_cast<ConstantSDNode>(" +
 651                  getNodeName(RootName + "1") + ");");
 652         emitCheck("Tmp" + utostr(NTmp));
 653         const char *MaskPredicate = N->getOperator()->getName() == "or"
 654         ? "CheckOrMask(" : "CheckAndMask(";
 655         emitCheck(MaskPredicate + getValueName(RootName + "0") +
 656                   ", Tmp" + utostr(NTmp) +
 657                   ", INT64_C(" + itostr(II->getValue()) + "))");
 658
 659         EmitChildMatchCode(N->getChild(0), N, RootName + utostr(0),
 660                            ChainSuffix + utostr(0), FoundChain);
 661         return;
 662       }
 663     }
 664   }
 665
 666   for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i, ++OpNo) {
 667     emitInit("SDValue " + getValueName(RootName + utostr(OpNo)) + " = " +
 668              getNodeName(RootName) + "->getOperand(" + utostr(OpNo) + ");");
 669
 670     EmitChildMatchCode(N->getChild(i), N, RootName + utostr(OpNo),
 671                        ChainSuffix + utostr(OpNo), FoundChain);
 672   }
 673
 674   // Handle complex patterns.
 675   if (const ComplexPattern *CP = N->getComplexPatternInfo(CGP)) {
 676     std::string Fn = CP->getSelectFunc();
 677     unsigned NumOps = CP->getNumOperands();
 678     for (unsigned i = 0; i < NumOps; ++i) {
 679       emitDecl("CPTmp" + RootName + "_" + utostr(i));
 680       emitCode("SDValue CPTmp" + RootName + "_" + utostr(i) + ";");
 681     }
 682     if (CP->hasProperty(SDNPHasChain)) {
 683       emitDecl("CPInChain");
 684       emitDecl("Chain" + ChainSuffix);
 685       emitCode("SDValue CPInChain;");
 686       emitCode("SDValue Chain" + ChainSuffix + ";");
 687     }
 688
 689     std::string Code = Fn + "(N, ";  // always pass in the root.
 690     Code += getValueName(RootName);
 691     for (unsigned i = 0; i < NumOps; i++)
 692       Code += ", CPTmp" + RootName + "_" + utostr(i);
 693     if (CP->hasProperty(SDNPHasChain)) {
 694       ChainName = "Chain" + ChainSuffix;
 695       Code += ", CPInChain, " + ChainName;
 696     }
 697     emitCheck(Code + ")");
 698   }
 699 }
 700
 701 void PatternCodeEmitter::EmitChildMatchCode(TreePatternNode *Child,
 702                                             TreePatternNode *Parent,
 703                                             const std::string &RootName,
 704                                             const std::string &ChainSuffix,
 705                                             bool &FoundChain) {
 706   if (!Child->isLeaf()) {
 707     // If it's not a leaf, recursively match.
 708     const SDNodeInfo &CInfo = CGP.getSDNodeInfo(Child->getOperator());
 709     emitCheck(getNodeName(RootName) + "->getOpcode() == " +
 710               CInfo.getEnumName());
 711     EmitMatchCode(Child, Parent, RootName, ChainSuffix, FoundChain);
 712     bool HasChain = false;
 713     if (Child->NodeHasProperty(SDNPHasChain, CGP)) {
 714       HasChain = true;
 715       FoldedChains.push_back(std::make_pair(getValueName(RootName),
 716                                             CInfo.getNumResults()));
 717     }
 718     if (Child->NodeHasProperty(SDNPOutFlag, CGP)) {
 719       assert(FoldedFlag.first == "" && FoldedFlag.second == 0 &&
 720              "Pattern folded multiple nodes which produce flags?");
 721       FoldedFlag = std::make_pair(getValueName(RootName),
 722                                   CInfo.getNumResults() + (unsigned)HasChain);
 723     }
 724     return;
 725   }
 726
 727   if (const ComplexPattern *CP = Child->getComplexPatternInfo(CGP)) {
 728     EmitMatchCode(Child, Parent, RootName, ChainSuffix, FoundChain);
 729     bool HasChain = false;
 730
 731     if (Child->NodeHasProperty(SDNPHasChain, CGP)) {
 732       HasChain = true;
 733       const SDNodeInfo &PInfo = CGP.getSDNodeInfo(Parent->getOperator());
 734       FoldedChains.push_back(std::make_pair("CPInChain",
 735                                             PInfo.getNumResults()));
 736     }
 737     if (Child->NodeHasProperty(SDNPOutFlag, CGP)) {
 738       assert(FoldedFlag.first == "" && FoldedFlag.second == 0 &&
 739              "Pattern folded multiple nodes which produce flags?");
 740       FoldedFlag = std::make_pair(getValueName(RootName),
 741                                   CP->getNumOperands() + (unsigned)HasChain);
 742     }
 743     return;
 744   }
 745
 746   // If this child has a name associated with it, capture it in VarMap. If
 747   // we already saw this in the pattern, emit code to verify dagness.
 748   if (!Child->getName().empty()) {
 749     std::string &VarMapEntry = VariableMap[Child->getName()];
 750     if (VarMapEntry.empty()) {
 751       VarMapEntry = getValueName(RootName);
 752     } else {
 753       // If we get here, this is a second reference to a specific name.
 754       // Since we already have checked that the first reference is valid,
 755       // we don't have to recursively match it, just check that it's the
 756       // same as the previously named thing.
 757       emitCheck(VarMapEntry + " == " + getValueName(RootName));
 758       Duplicates.insert(getValueName(RootName));
 759       return;
 760     }
 761   }
 762
 763   // Handle leaves of various types.
 764   if (DefInit *DI = dynamic_cast<DefInit*>(Child->getLeafValue())) {
 765     Record *LeafRec = DI->getDef();
 766     if (LeafRec->isSubClassOf("RegisterClass") ||
 767         LeafRec->isSubClassOf("PointerLikeRegClass")) {
 768       // Handle register references.  Nothing to do here.
 769     } else if (LeafRec->isSubClassOf("Register")) {
 770       // Handle register references.
 771     } else if (LeafRec->getName() == "srcvalue") {
 772       // Place holder for SRCVALUE nodes. Nothing to do here.
 773     } else if (LeafRec->isSubClassOf("ValueType")) {
 774       // Make sure this is the specified value type.
 775       emitCheck("cast<VTSDNode>(" + getNodeName(RootName) +
 776                 ")->getVT() == MVT::" + LeafRec->getName());
 777     } else if (LeafRec->isSubClassOf("CondCode")) {
 778       // Make sure this is the specified cond code.
 779       emitCheck("cast<CondCodeSDNode>(" + getNodeName(RootName) +
 780                 ")->get() == ISD::" + LeafRec->getName());
 781     } else {
 782 #ifndef NDEBUG
 783       Child->dump();
 784       errs() << " ";
 785 #endif
 786       assert(0 && "Unknown leaf type!");
 787     }
 788
 789     // If there are node predicates for this, emit the calls.
 790     for (unsigned i = 0, e = Child->getPredicateFns().size(); i != e; ++i)
 791       emitCheck(Child->getPredicateFns()[i] + "(" + getNodeName(RootName) +
 792                 ")");
 793     return;
 794   }
 795
 796   if (IntInit *II = dynamic_cast<IntInit*>(Child->getLeafValue())) {
 797     unsigned NTmp = TmpNo++;
 798     emitCode("ConstantSDNode *Tmp"+ utostr(NTmp) +
 799              " = dyn_cast<ConstantSDNode>("+
 800              getNodeName(RootName) + ");");
 801     emitCheck("Tmp" + utostr(NTmp));
 802     unsigned CTmp = TmpNo++;
 803     emitCode("int64_t CN"+ utostr(CTmp) +
 804              " = Tmp" + utostr(NTmp) + "->getSExtValue();");
 805     emitCheck("CN" + utostr(CTmp) + " == "
 806               "INT64_C(" +itostr(II->getValue()) + ")");
 807     return;
 808   }
 809 #ifndef NDEBUG
 810   Child->dump();
 811 #endif
 812   assert(0 && "Unknown leaf type!");
 813 }
 814
 815 /// EmitResultCode - Emit the action for a pattern.  Now that it has matched
 816 /// we actually have to build a DAG!
 817 std::vector<std::string>
 818 PatternCodeEmitter::EmitResultCode(TreePatternNode *N,
 819                                    std::vector<Record*> DstRegs,
 820                                    bool InFlagDecled, bool ResNodeDecled,
 821                                    bool LikeLeaf, bool isRoot) {
 822   // List of arguments of getMachineNode() or SelectNodeTo().
 823   std::vector<std::string> NodeOps;
 824   // This is something selected from the pattern we matched.
 825   if (!N->getName().empty()) {
 826     const std::string &VarName = N->getName();
 827     std::string Val = VariableMap[VarName];
 828     if (Val.empty()) {
 829       errs() << "Variable '" << VarName << " referenced but not defined "
 830       << "and not caught earlier!\n";
 831       abort();
 832     }
 833
 834     unsigned ResNo = TmpNo++;
 835     if (!N->isLeaf() && N->getOperator()->getName() == "imm") {
 836       assert(N->getExtTypes().size() == 1 && "Multiple types not handled!");
 837       std::string CastType;
 838       std::string TmpVar =  "Tmp" + utostr(ResNo);
 839       switch (N->getTypeNum(0)) {
 840         default:
 841           errs() << "Cannot handle " << getEnumName(N->getTypeNum(0))
 842           << " type as an immediate constant. Aborting\n";
 843           abort();
 844         case MVT::i1:  CastType = "bool"; break;
 845         case MVT::i8:  CastType = "unsigned char"; break;
 846         case MVT::i16: CastType = "unsigned short"; break;
 847         case MVT::i32: CastType = "unsigned"; break;
 848         case MVT::i64: CastType = "uint64_t"; break;
 849       }
 850       emitCode("SDValue " + TmpVar +
 851                " = CurDAG->getTargetConstant(((" + CastType +
 852                ") cast<ConstantSDNode>(" + Val + ")->getZExtValue()), " +
 853                getEnumName(N->getTypeNum(0)) + ");");
 854       NodeOps.push_back(getValueName(TmpVar));
 855     } else if (!N->isLeaf() && N->getOperator()->getName() == "fpimm") {
 856       assert(N->getExtTypes().size() == 1 && "Multiple types not handled!");
 857       std::string TmpVar =  "Tmp" + utostr(ResNo);
 858       emitCode("SDValue " + TmpVar +
 859                " = CurDAG->getTargetConstantFP(*cast<ConstantFPSDNode>(" +
 860                Val + ")->getConstantFPValue(), cast<ConstantFPSDNode>(" +
 861                Val + ")->getValueType(0));");
 862       NodeOps.push_back(getValueName(TmpVar));
 863     } else if (const ComplexPattern *CP = N->getComplexPatternInfo(CGP)) {
 864       for (unsigned i = 0; i < CP->getNumOperands(); ++i)
 865         NodeOps.push_back(getValueName("CPTmp" + Val + "_" + utostr(i)));
 866     } else {
 867       // This node, probably wrapped in a SDNodeXForm, behaves like a leaf
 868       // node even if it isn't one. Don't select it.
 869       if (!LikeLeaf) {
 870         if (isRoot && N->isLeaf()) {
 871           emitCode("ReplaceUses(SDValue(N, 0), " + Val + ");");
 872           emitCode("return NULL;");
 873         }
 874       }
 875       NodeOps.push_back(getValueName(Val));
 876     }
 877     return NodeOps;
 878   }
 879   if (N->isLeaf()) {
 880     // If this is an explicit register reference, handle it.
 881     if (DefInit *DI = dynamic_cast<DefInit*>(N->getLeafValue())) {
 882       unsigned ResNo = TmpNo++;
 883       if (DI->getDef()->isSubClassOf("Register")) {
 884         emitCode("SDValue Tmp" + utostr(ResNo) + " = CurDAG->getRegister(" +
 885                  getQualifiedName(DI->getDef()) + ", " +
 886                  getEnumName(N->getTypeNum(0)) + ");");
 887         NodeOps.push_back(getValueName("Tmp" + utostr(ResNo)));
 888         return NodeOps;
 889       } else if (DI->getDef()->getName() == "zero_reg") {
 890         emitCode("SDValue Tmp" + utostr(ResNo) +
 891                  " = CurDAG->getRegister(0, " +
 892                  getEnumName(N->getTypeNum(0)) + ");");
 893         NodeOps.push_back(getValueName("Tmp" + utostr(ResNo)));
 894         return NodeOps;
 895       } else if (DI->getDef()->isSubClassOf("RegisterClass")) {
 896         // Handle a reference to a register class. This is used
 897         // in COPY_TO_SUBREG instructions.
 898         emitCode("SDValue Tmp" + utostr(ResNo) +
 899                  " = CurDAG->getTargetConstant(" +
 900                  getQualifiedName(DI->getDef()) + "RegClassID, " +
 901                  "MVT::i32);");
 902         NodeOps.push_back(getValueName("Tmp" + utostr(ResNo)));
 903         return NodeOps;
 904       }
 905     } else if (IntInit *II = dynamic_cast<IntInit*>(N->getLeafValue())) {
 906       unsigned ResNo = TmpNo++;
 907       assert(N->getExtTypes().size() == 1 && "Multiple types not handled!");
 908       emitCode("SDValue Tmp" + utostr(ResNo) +
 909                " = CurDAG->getTargetConstant(0x" +
 910                utohexstr((uint64_t) II->getValue()) +
 911                "ULL, " + getEnumName(N->getTypeNum(0)) + ");");
 912       NodeOps.push_back(getValueName("Tmp" + utostr(ResNo)));
 913       return NodeOps;
 914     }
 915
 916 #ifndef NDEBUG
 917     N->dump();
 918 #endif
 919     assert(0 && "Unknown leaf type!");
 920     return NodeOps;
 921   }
 922
 923   Record *Op = N->getOperator();
 924   if (Op->isSubClassOf("Instruction")) {
 925     const CodeGenTarget &CGT = CGP.getTargetInfo();
 926     CodeGenInstruction &II = CGT.getInstruction(Op->getName());
 927     const DAGInstruction &Inst = CGP.getInstruction(Op);
 928     const TreePattern *InstPat = Inst.getPattern();
 929     // FIXME: Assume actual pattern comes before "implicit".
 930     TreePatternNode *InstPatNode =
 931     isRoot ? (InstPat ? InstPat->getTree(0) : Pattern)
 932     : (InstPat ? InstPat->getTree(0) : NULL);
 933     if (InstPatNode && !InstPatNode->isLeaf() &&
 934         InstPatNode->getOperator()->getName() == "set") {
 935       InstPatNode = InstPatNode->getChild(InstPatNode->getNumChildren()-1);
 936     }
 937     bool IsVariadic = isRoot && II.isVariadic;
 938     // FIXME: fix how we deal with physical register operands.
 939     bool HasImpInputs  = isRoot && Inst.getNumImpOperands() > 0;
 940     bool HasImpResults = isRoot && DstRegs.size() > 0;
 941     bool NodeHasOptInFlag = isRoot &&
 942       Pattern->TreeHasProperty(SDNPOptInFlag, CGP);
 943     bool NodeHasInFlag  = isRoot &&
 944       Pattern->TreeHasProperty(SDNPInFlag, CGP);
 945     bool NodeHasOutFlag = isRoot &&
 946       Pattern->TreeHasProperty(SDNPOutFlag, CGP);
 947     bool NodeHasChain = InstPatNode &&
 948       InstPatNode->TreeHasProperty(SDNPHasChain, CGP);
 949     bool InputHasChain = isRoot && Pattern->NodeHasProperty(SDNPHasChain, CGP);
 950     unsigned NumResults = Inst.getNumResults();
 951     unsigned NumDstRegs = HasImpResults ? DstRegs.size() : 0;
 952
 953     // Record output varargs info.
 954     OutputIsVariadic = IsVariadic;
 955
 956     if (NodeHasOptInFlag) {
 957       emitCode("bool HasInFlag = "
 958                "(N->getOperand(N->getNumOperands()-1).getValueType() == "
 959                "MVT::Flag);");
 960     }
 961     if (IsVariadic)
 962       emitCode("SmallVector<SDValue, 8> Ops" + utostr(OpcNo) + ";");
 963
 964     // How many results is this pattern expected to produce?
 965     unsigned NumPatResults = 0;
 966     for (unsigned i = 0, e = Pattern->getExtTypes().size(); i != e; i++) {
 967       MVT::SimpleValueType VT = Pattern->getTypeNum(i);
 968       if (VT != MVT::isVoid && VT != MVT::Flag)
 969         NumPatResults++;
 970     }
 971
 972     if (OrigChains.size() > 0) {
 973       // The original input chain is being ignored. If it is not just
 974       // pointing to the op that's being folded, we should create a
 975       // TokenFactor with it and the chain of the folded op as the new chain.
 976       // We could potentially be doing multiple levels of folding, in that
 977       // case, the TokenFactor can have more operands.
 978       emitCode("SmallVector<SDValue, 8> InChains;");
 979       for (unsigned i = 0, e = OrigChains.size(); i < e; ++i) {
 980         emitCode("if (" + OrigChains[i].first + ".getNode() != " +
 981                  OrigChains[i].second + ".getNode()) {");
 982         emitCode("  InChains.push_back(" + OrigChains[i].first + ");");
 983         emitCode("}");
 984       }
 985       emitCode("InChains.push_back(" + ChainName + ");");
 986       emitCode(ChainName + " = CurDAG->getNode(ISD::TokenFactor, "
 987                "N->getDebugLoc(), MVT::Other, "
 988                "&InChains[0], InChains.size());");
 989       if (GenDebug) {
 990         emitCode("CurDAG->setSubgraphColor(" + ChainName +
 991                  ".getNode(), \"yellow\");");
 992         emitCode("CurDAG->setSubgraphColor(" + ChainName +
 993                  ".getNode(), \"black\");");
 994       }
 995     }
 996
 997     // Loop over all of the operands of the instruction pattern, emitting code
 998     // to fill them all in.  The node 'N' usually has number children equal to
 999     // the number of input operands of the instruction.  However, in cases
1000     // where there are predicate operands for an instruction, we need to fill
1001     // in the 'execute always' values.  Match up the node operands to the
1002     // instruction operands to do this.
1003     std::vector<std::string> AllOps;
1004     for (unsigned ChildNo = 0, InstOpNo = NumResults;
1005          InstOpNo != II.OperandList.size(); ++InstOpNo) {
1006       std::vector<std::string> Ops;
1007
1008       // Determine what to emit for this operand.
1009       Record *OperandNode = II.OperandList[InstOpNo].Rec;
1010       if ((OperandNode->isSubClassOf("PredicateOperand") ||
1011            OperandNode->isSubClassOf("OptionalDefOperand")) &&
1012           !CGP.getDefaultOperand(OperandNode).DefaultOps.empty()) {
1013         // This is a predicate or optional def operand; emit the
1014         // 'default ops' operands.
1015         const DAGDefaultOperand &DefaultOp =
1016         CGP.getDefaultOperand(II.OperandList[InstOpNo].Rec);
1017         for (unsigned i = 0, e = DefaultOp.DefaultOps.size(); i != e; ++i) {
1018           Ops = EmitResultCode(DefaultOp.DefaultOps[i], DstRegs,
1019                                InFlagDecled, ResNodeDecled);
1020           AllOps.insert(AllOps.end(), Ops.begin(), Ops.end());
1021         }
1022       } else {
1023         // Otherwise this is a normal operand or a predicate operand without
1024         // 'execute always'; emit it.
1025         Ops = EmitResultCode(N->getChild(ChildNo), DstRegs,
1026                              InFlagDecled, ResNodeDecled);
1027         AllOps.insert(AllOps.end(), Ops.begin(), Ops.end());
1028         ++ChildNo;
1029       }
1030     }
1031
1032     // Emit all the chain and CopyToReg stuff.
1033     bool ChainEmitted = NodeHasChain;
1034     if (NodeHasInFlag || HasImpInputs)
1035       EmitInFlagSelectCode(Pattern, "N", ChainEmitted,
1036                            InFlagDecled, ResNodeDecled, true);
1037     if (NodeHasOptInFlag || NodeHasInFlag || HasImpInputs) {
1038       if (!InFlagDecled) {
1039         emitCode("SDValue InFlag(0, 0);");
1040         InFlagDecled = true;
1041       }
1042       if (NodeHasOptInFlag) {
1043         emitCode("if (HasInFlag) {");
1044         emitCode("  InFlag = N->getOperand(N->getNumOperands()-1);");
1045         emitCode("}");
1046       }
1047     }
1048
1049     unsigned ResNo = TmpNo++;
1050
1051     unsigned OpsNo = OpcNo;
1052     std::string CodePrefix;
1053     bool ChainAssignmentNeeded = NodeHasChain && !isRoot;
1054     std::deque<std::string> After;
1055     std::string NodeName;
1056     if (!isRoot) {
1057       NodeName = "Tmp" + utostr(ResNo);
1058       CodePrefix = "SDValue " + NodeName + "(";
1059     } else {
1060       NodeName = "ResNode";
1061       if (!ResNodeDecled) {
1062         CodePrefix = "SDNode *" + NodeName + " = ";
1063         ResNodeDecled = true;
1064       } else
1065         CodePrefix = NodeName + " = ";
1066     }
1067
1068     std::string Code = "Opc" + utostr(OpcNo);
1069
1070     if (!isRoot || (InputHasChain && !NodeHasChain))
1071       // For call to "getMachineNode()".
1072       Code += ", N->getDebugLoc()";
1073
1074     emitOpcode(II.Namespace + "::" + II.TheDef->getName());
1075
1076     // Output order: results, chain, flags
1077     // Result types.
1078     if (NumResults > 0 && N->getTypeNum(0) != MVT::isVoid) {
1079       Code += ", VT" + utostr(VTNo);
1080       emitVT(getEnumName(N->getTypeNum(0)));
1081     }
1082     // Add types for implicit results in physical registers, scheduler will
1083     // care of adding copyfromreg nodes.
1084     for (unsigned i = 0; i < NumDstRegs; i++) {
1085       Record *RR = DstRegs[i];
1086       if (RR->isSubClassOf("Register")) {
1087         MVT::SimpleValueType RVT = getRegisterValueType(RR, CGT);
1088         Code += ", " + getEnumName(RVT);
1089       }
1090     }
1091     if (NodeHasChain)
1092       Code += ", MVT::Other";
1093     if (NodeHasOutFlag)
1094       Code += ", MVT::Flag";
1095
1096     // Inputs.
1097     if (IsVariadic) {
1098       for (unsigned i = 0, e = AllOps.size(); i != e; ++i)
1099         emitCode("Ops" + utostr(OpsNo) + ".push_back(" + AllOps[i] + ");");
1100       AllOps.clear();
1101
1102       // Figure out whether any operands at the end of the op list are not
1103       // part of the variable section.
1104       std::string EndAdjust;
1105       if (NodeHasInFlag || HasImpInputs)
1106         EndAdjust = "-1";  // Always has one flag.
1107       else if (NodeHasOptInFlag)
1108         EndAdjust = "-(HasInFlag?1:0)"; // May have a flag.
1109
1110       emitCode("for (unsigned i = NumInputRootOps + " + utostr(NodeHasChain) +
1111                ", e = N->getNumOperands()" + EndAdjust + "; i != e; ++i) {");
1112
1113       emitCode("  Ops" + utostr(OpsNo) + ".push_back(N->getOperand(i));");
1114       emitCode("}");
1115     }
1116
1117     // Populate MemRefs with entries for each memory accesses covered by
1118     // this pattern.
1119     if (isRoot && !LSI.empty()) {
1120       std::string MemRefs = "MemRefs" + utostr(OpsNo);
1121       emitCode("MachineSDNode::mmo_iterator " + MemRefs + " = "
1122                "MF->allocateMemRefsArray(" + utostr(LSI.size()) + ");");
1123       for (unsigned i = 0, e = LSI.size(); i != e; ++i)
1124         emitCode(MemRefs + "[" + utostr(i) + "] = "
1125                  "cast<MemSDNode>(" + LSI[i] + ")->getMemOperand();");
1126       After.push_back("cast<MachineSDNode>(ResNode)->setMemRefs(" +
1127                       MemRefs + ", " + MemRefs + " + " + utostr(LSI.size()) +
1128                       ");");
1129     }
1130
1131     if (NodeHasChain) {
1132       if (IsVariadic)
1133         emitCode("Ops" + utostr(OpsNo) + ".push_back(" + ChainName + ");");
1134       else
1135         AllOps.push_back(ChainName);
1136     }
1137
1138     if (IsVariadic) {
1139       if (NodeHasInFlag || HasImpInputs)
1140         emitCode("Ops" + utostr(OpsNo) + ".push_back(InFlag);");
1141       else if (NodeHasOptInFlag) {
1142         emitCode("if (HasInFlag)");
1143         emitCode("  Ops" + utostr(OpsNo) + ".push_back(InFlag);");
1144       }
1145       Code += ", &Ops" + utostr(OpsNo) + "[0], Ops" + utostr(OpsNo) +
1146       ".size()";
1147     } else if (NodeHasInFlag || NodeHasOptInFlag || HasImpInputs)
1148       AllOps.push_back("InFlag");
1149
1150     unsigned NumOps = AllOps.size();
1151     if (NumOps) {
1152       if (!NodeHasOptInFlag && NumOps < 4) {
1153         for (unsigned i = 0; i != NumOps; ++i)
1154           Code += ", " + AllOps[i];
1155       } else {
1156         std::string OpsCode = "SDValue Ops" + utostr(OpsNo) + "[] = { ";
1157         for (unsigned i = 0; i != NumOps; ++i) {
1158           OpsCode += AllOps[i];
1159           if (i != NumOps-1)
1160             OpsCode += ", ";
1161         }
1162         emitCode(OpsCode + " };");
1163         Code += ", Ops" + utostr(OpsNo) + ", ";
1164         if (NodeHasOptInFlag) {
1165           Code += "HasInFlag ? ";
1166           Code += utostr(NumOps) + " : " + utostr(NumOps-1);
1167         } else
1168           Code += utostr(NumOps);
1169       }
1170     }
1171
1172     if (!isRoot)
1173       Code += "), 0";
1174
1175     std::vector<std::string> ReplaceFroms;
1176     std::vector<std::string> ReplaceTos;
1177     if (!isRoot) {
1178       NodeOps.push_back("Tmp" + utostr(ResNo));
1179     } else {
1180
1181       if (NodeHasOutFlag) {
1182         if (!InFlagDecled) {
1183           After.push_back("SDValue InFlag(ResNode, " +
1184                           utostr(NumResults+NumDstRegs+(unsigned)NodeHasChain) +
1185                           ");");
1186           InFlagDecled = true;
1187         } else
1188           After.push_back("InFlag = SDValue(ResNode, " +
1189                           utostr(NumResults+NumDstRegs+(unsigned)NodeHasChain) +
1190                           ");");
1191       }
1192
1193       for (unsigned j = 0, e = FoldedChains.size(); j < e; j++) {
1194         ReplaceFroms.push_back("SDValue(" +
1195                                FoldedChains[j].first + ".getNode(), " +
1196                                utostr(FoldedChains[j].second) +
1197                                ")");
1198         ReplaceTos.push_back("SDValue(ResNode, " +
1199                              utostr(NumResults+NumDstRegs) + ")");
1200       }
1201
1202       if (NodeHasOutFlag) {
1203         if (FoldedFlag.first != "") {
1204           ReplaceFroms.push_back("SDValue(" + FoldedFlag.first + ".getNode(), " +
1205                                  utostr(FoldedFlag.second) + ")");
1206           ReplaceTos.push_back("InFlag");
1207         } else {
1208           assert(Pattern->NodeHasProperty(SDNPOutFlag, CGP));
1209           ReplaceFroms.push_back("SDValue(N, " +
1210                                  utostr(NumPatResults + (unsigned)InputHasChain)
1211                                  + ")");
1212           ReplaceTos.push_back("InFlag");
1213         }
1214       }
1215
1216       if (!ReplaceFroms.empty() && InputHasChain) {
1217         ReplaceFroms.push_back("SDValue(N, " +
1218                                utostr(NumPatResults) + ")");
1219         ReplaceTos.push_back("SDValue(" + ChainName + ".getNode(), " +
1220                              ChainName + ".getResNo()" + ")");
1221         ChainAssignmentNeeded |= NodeHasChain;
1222       }
1223
1224       // User does not expect the instruction would produce a chain!
1225       if ((!InputHasChain && NodeHasChain) && NodeHasOutFlag) {
1226         ;
1227       } else if (InputHasChain && !NodeHasChain) {
1228         // One of the inner node produces a chain.
1229         assert(!NodeHasOutFlag && "Node has flag but not chain!");
1230         ReplaceFroms.push_back("SDValue(N, " +
1231                                utostr(NumPatResults) + ")");
1232         ReplaceTos.push_back(ChainName);
1233       }
1234     }
1235
1236     if (ChainAssignmentNeeded) {
1237       // Remember which op produces the chain.
1238       std::string ChainAssign;
1239       if (!isRoot)
1240         ChainAssign = ChainName + " = SDValue(" + NodeName +
1241         ".getNode(), " + utostr(NumResults+NumDstRegs) + ");";
1242       else
1243         ChainAssign = ChainName + " = SDValue(" + NodeName +
1244         ", " + utostr(NumResults+NumDstRegs) + ");";
1245
1246       After.push_front(ChainAssign);
1247     }
1248
1249     if (ReplaceFroms.size() == 1) {
1250       After.push_back("ReplaceUses(" + ReplaceFroms[0] + ", " +
1251                       ReplaceTos[0] + ");");
1252     } else if (!ReplaceFroms.empty()) {
1253       After.push_back("const SDValue Froms[] = {");
1254       for (unsigned i = 0, e = ReplaceFroms.size(); i != e; ++i)
1255         After.push_back("  " + ReplaceFroms[i] + (i + 1 != e ? "," : ""));
1256       After.push_back("};");
1257       After.push_back("const SDValue Tos[] = {");
1258       for (unsigned i = 0, e = ReplaceFroms.size(); i != e; ++i)
1259         After.push_back("  " + ReplaceTos[i] + (i + 1 != e ? "," : ""));
1260       After.push_back("};");
1261       After.push_back("ReplaceUses(Froms, Tos, " +
1262                       itostr(ReplaceFroms.size()) + ");");
1263     }
1264
1265     // We prefer to use SelectNodeTo since it avoids allocation when
1266     // possible and it avoids CSE map recalculation for the node's
1267     // users, however it's tricky to use in a non-root context.
1268     //
1269     // We also don't use SelectNodeTo if the pattern replacement is being
1270     // used to jettison a chain result, since morphing the node in place
1271     // would leave users of the chain dangling.
1272     //
1273     if (!isRoot || (InputHasChain && !NodeHasChain)) {
1274       Code = "CurDAG->getMachineNode(" + Code;
1275     } else {
1276       Code = "CurDAG->SelectNodeTo(N, " + Code;
1277     }
1278     if (isRoot) {
1279       if (After.empty())
1280         CodePrefix = "return ";
1281       else
1282         After.push_back("return ResNode;");
1283     }
1284
1285     emitCode(CodePrefix + Code + ");");
1286
1287     if (GenDebug) {
1288       if (!isRoot) {
1289         emitCode("CurDAG->setSubgraphColor(" +
1290                  NodeName +".getNode(), \"yellow\");");
1291         emitCode("CurDAG->setSubgraphColor(" +
1292                  NodeName +".getNode(), \"black\");");
1293       } else {
1294         emitCode("CurDAG->setSubgraphColor(" + NodeName +", \"yellow\");");
1295         emitCode("CurDAG->setSubgraphColor(" + NodeName +", \"black\");");
1296       }
1297     }
1298
1299     for (unsigned i = 0, e = After.size(); i != e; ++i)
1300       emitCode(After[i]);
1301
1302     return NodeOps;
1303   }
1304   if (Op->isSubClassOf("SDNodeXForm")) {
1305     assert(N->getNumChildren() == 1 && "node xform should have one child!");
1306     // PatLeaf node - the operand may or may not be a leaf node. But it should
1307     // behave like one.
1308     std::vector<std::string> Ops =
1309     EmitResultCode(N->getChild(0), DstRegs, InFlagDecled,
1310                    ResNodeDecled, true);
1311     unsigned ResNo = TmpNo++;
1312     emitCode("SDValue Tmp" + utostr(ResNo) + " = Transform_" + Op->getName()
1313              + "(" + Ops.back() + ".getNode());");
1314     NodeOps.push_back("Tmp" + utostr(ResNo));
1315     if (isRoot)
1316       emitCode("return Tmp" + utostr(ResNo) + ".getNode();");
1317     return NodeOps;
1318   }
1319
1320   N->dump();
1321   errs() << "\n";
1322   throw std::string("Unknown node in result pattern!");
1323 }
1324
1325
1326 /// EmitCodeForPattern - Given a pattern to match, emit code to the specified
1327 /// stream to match the pattern, and generate the code for the match if it
1328 /// succeeds.  Returns true if the pattern is not guaranteed to match.
1329 void DAGISelEmitter::GenerateCodeForPattern(const PatternToMatch &Pattern,
1330                   std::vector<std::pair<unsigned, std::string> > &GeneratedCode,
1331                                            std::set<std::string> &GeneratedDecl,
1332                                         std::vector<std::string> &TargetOpcodes,
1333                                             std::vector<std::string> &TargetVTs,
1334                                             bool &OutputIsVariadic,
1335                                             unsigned &NumInputRootOps) {
1336   OutputIsVariadic = false;
1337   NumInputRootOps = 0;
1338
1339   PatternCodeEmitter Emitter(CGP, Pattern.getPredicateCheck(),
1340                              Pattern.getSrcPattern(), Pattern.getDstPattern(),
1341                              GeneratedCode, GeneratedDecl,
1342                              TargetOpcodes, TargetVTs,
1343                              OutputIsVariadic, NumInputRootOps);
1344
1345   // Emit the matcher, capturing named arguments in VariableMap.
1346   bool FoundChain = false;
1347   Emitter.EmitMatchCode(Pattern.getSrcPattern(), NULL, "N", "", FoundChain);
1348
1349   // TP - Get *SOME* tree pattern, we don't care which.  It is only used for
1350   // diagnostics, which we know are impossible at this point.
1351   TreePattern &TP = *CGP.pf_begin()->second;
1352
1353   // At this point, we know that we structurally match the pattern, but the
1354   // types of the nodes may not match.  Figure out the fewest number of type
1355   // comparisons we need to emit.  For example, if there is only one integer
1356   // type supported by a target, there should be no type comparisons at all for
1357   // integer patterns!
1358   //
1359   // To figure out the fewest number of type checks needed, clone the pattern,
1360   // remove the types, then perform type inference on the pattern as a whole.
1361   // If there are unresolved types, emit an explicit check for those types,
1362   // apply the type to the tree, then rerun type inference.  Iterate until all
1363   // types are resolved.
1364   //
1365   TreePatternNode *Pat = Pattern.getSrcPattern()->clone();
1366   Pat->RemoveAllTypes();
1367
1368   do {
1369     // Resolve/propagate as many types as possible.
1370     try {
1371       bool MadeChange = true;
1372       while (MadeChange)
1373         MadeChange = Pat->ApplyTypeConstraints(TP,
1374                                                true/*Ignore reg constraints*/);
1375     } catch (...) {
1376       assert(0 && "Error: could not find consistent types for something we"
1377              " already decided was ok!");
1378       abort();
1379     }
1380
1381     // Insert a check for an unresolved type and add it to the tree.  If we find
1382     // an unresolved type to add a check for, this returns true and we iterate,
1383     // otherwise we are done.
1384   } while (Emitter.InsertOneTypeCheck(Pat, Pattern.getSrcPattern(), "N", true));
1385
1386   Emitter.EmitResultCode(Pattern.getDstPattern(), Pattern.getDstRegs(),
1387                          false, false, false, true);
1388   delete Pat;
1389 }
1390
1391 /// EraseCodeLine - Erase one code line from all of the patterns.  If removing
1392 /// a line causes any of them to be empty, remove them and return true when
1393 /// done.
1394 static bool EraseCodeLine(std::vector<std::pair<const PatternToMatch*,
1395                           std::vector<std::pair<unsigned, std::string> > > >
1396                           &Patterns) {
1397   bool ErasedPatterns = false;
1398   for (unsigned i = 0, e = Patterns.size(); i != e; ++i) {
1399     Patterns[i].second.pop_back();
1400     if (Patterns[i].second.empty()) {
1401       Patterns.erase(Patterns.begin()+i);
1402       --i; --e;
1403       ErasedPatterns = true;
1404     }
1405   }
1406   return ErasedPatterns;
1407 }
1408
1409 /// EmitPatterns - Emit code for at least one pattern, but try to group common
1410 /// code together between the patterns.
1411 void DAGISelEmitter::EmitPatterns(std::vector<std::pair<const PatternToMatch*,
1412                               std::vector<std::pair<unsigned, std::string> > > >
1413                                   &Patterns, unsigned Indent,
1414                                   raw_ostream &OS) {
1415   typedef std::pair<unsigned, std::string> CodeLine;
1416   typedef std::vector<CodeLine> CodeList;
1417   typedef std::vector<std::pair<const PatternToMatch*, CodeList> > PatternList;
1418
1419   if (Patterns.empty()) return;
1420
1421   // Figure out how many patterns share the next code line.  Explicitly copy
1422   // FirstCodeLine so that we don't invalidate a reference when changing
1423   // Patterns.
1424   const CodeLine FirstCodeLine = Patterns.back().second.back();
1425   unsigned LastMatch = Patterns.size()-1;
1426   while (LastMatch != 0 && Patterns[LastMatch-1].second.back() == FirstCodeLine)
1427     --LastMatch;
1428
1429   // If not all patterns share this line, split the list into two pieces.  The
1430   // first chunk will use this line, the second chunk won't.
1431   if (LastMatch != 0) {
1432     PatternList Shared(Patterns.begin()+LastMatch, Patterns.end());
1433     PatternList Other(Patterns.begin(), Patterns.begin()+LastMatch);
1434
1435     // FIXME: Emit braces?
1436     if (Shared.size() == 1) {
1437       const PatternToMatch &Pattern = *Shared.back().first;
1438       OS << "\n" << std::string(Indent, ' ') << "// Pattern: ";
1439       Pattern.getSrcPattern()->print(OS);
1440       OS << "\n" << std::string(Indent, ' ') << "// Emits: ";
1441       Pattern.getDstPattern()->print(OS);
1442       OS << "\n";
1443       unsigned AddedComplexity = Pattern.getAddedComplexity();
1444       OS << std::string(Indent, ' ') << "// Pattern complexity = "
1445          << getPatternSize(Pattern.getSrcPattern(), CGP) + AddedComplexity
1446          << "  cost = "
1447          << getResultPatternCost(Pattern.getDstPattern(), CGP)
1448          << "  size = "
1449          << getResultPatternSize(Pattern.getDstPattern(), CGP) << "\n";
1450     }
1451     if (FirstCodeLine.first != 1) {
1452       OS << std::string(Indent, ' ') << "{\n";
1453       Indent += 2;
1454     }
1455     EmitPatterns(Shared, Indent, OS);
1456     if (FirstCodeLine.first != 1) {
1457       Indent -= 2;
1458       OS << std::string(Indent, ' ') << "}\n";
1459     }
1460
1461     if (Other.size() == 1) {
1462       const PatternToMatch &Pattern = *Other.back().first;
1463       OS << "\n" << std::string(Indent, ' ') << "// Pattern: ";
1464       Pattern.getSrcPattern()->print(OS);
1465       OS << "\n" << std::string(Indent, ' ') << "// Emits: ";
1466       Pattern.getDstPattern()->print(OS);
1467       OS << "\n";
1468       unsigned AddedComplexity = Pattern.getAddedComplexity();
1469       OS << std::string(Indent, ' ') << "// Pattern complexity = "
1470          << getPatternSize(Pattern.getSrcPattern(), CGP) + AddedComplexity
1471          << "  cost = "
1472          << getResultPatternCost(Pattern.getDstPattern(), CGP)
1473          << "  size = "
1474          << getResultPatternSize(Pattern.getDstPattern(), CGP) << "\n";
1475     }
1476     EmitPatterns(Other, Indent, OS);
1477     return;
1478   }
1479
1480   // Remove this code from all of the patterns that share it.
1481   bool ErasedPatterns = EraseCodeLine(Patterns);
1482
1483   bool isPredicate = FirstCodeLine.first == 1;
1484
1485   // Otherwise, every pattern in the list has this line.  Emit it.
1486   if (!isPredicate) {
1487     // Normal code.
1488     OS << std::string(Indent, ' ') << FirstCodeLine.second << "\n";
1489   } else {
1490     OS << std::string(Indent, ' ') << "if (" << FirstCodeLine.second;
1491
1492     // If the next code line is another predicate, and if all of the pattern
1493     // in this group share the same next line, emit it inline now.  Do this
1494     // until we run out of common predicates.
1495     while (!ErasedPatterns && Patterns.back().second.back().first == 1) {
1496       // Check that all of the patterns in Patterns end with the same predicate.
1497       bool AllEndWithSamePredicate = true;
1498       for (unsigned i = 0, e = Patterns.size(); i != e; ++i)
1499         if (Patterns[i].second.back() != Patterns.back().second.back()) {
1500           AllEndWithSamePredicate = false;
1501           break;
1502         }
1503       // If all of the predicates aren't the same, we can't share them.
1504       if (!AllEndWithSamePredicate) break;
1505
1506       // Otherwise we can.  Emit it shared now.
1507       OS << " &&\n" << std::string(Indent+4, ' ')
1508          << Patterns.back().second.back().second;
1509       ErasedPatterns = EraseCodeLine(Patterns);
1510     }
1511
1512     OS << ") {\n";
1513     Indent += 2;
1514   }
1515
1516   EmitPatterns(Patterns, Indent, OS);
1517
1518   if (isPredicate)
1519     OS << std::string(Indent-2, ' ') << "}\n";
1520 }
1521
1522 static std::string getLegalCName(std::string OpName) {
1523   std::string::size_type pos = OpName.find("::");
1524   if (pos != std::string::npos)
1525     OpName.replace(pos, 2, "_");
1526   return OpName;
1527 }
1528
1529 void DAGISelEmitter::EmitInstructionSelector(raw_ostream &OS) {
1530   const CodeGenTarget &Target = CGP.getTargetInfo();
1531
1532   // Get the namespace to insert instructions into.
1533   std::string InstNS = Target.getInstNamespace();
1534   if (!InstNS.empty()) InstNS += "::";
1535
1536   // Group the patterns by their top-level opcodes.
1537   std::map<std::string, std::vector<const PatternToMatch*> > PatternsByOpcode;
1538   // All unique target node emission functions.
1539   std::map<std::string, unsigned> EmitFunctions;
1540   for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(),
1541        E = CGP.ptm_end(); I != E; ++I) {
1542     const PatternToMatch &Pattern = *I;
1543     TreePatternNode *Node = Pattern.getSrcPattern();
1544     if (!Node->isLeaf()) {
1545       PatternsByOpcode[getOpcodeName(Node->getOperator(), CGP)].
1546         push_back(&Pattern);
1547     } else {
1548       const ComplexPattern *CP;
1549       if (dynamic_cast<IntInit*>(Node->getLeafValue())) {
1550         PatternsByOpcode[getOpcodeName(CGP.getSDNodeNamed("imm"), CGP)].
1551           push_back(&Pattern);
1552       } else if ((CP = Node->getComplexPatternInfo(CGP))) {
1553         std::vector<Record*> OpNodes = CP->getRootNodes();
1554         for (unsigned j = 0, e = OpNodes.size(); j != e; j++) {
1555           PatternsByOpcode[getOpcodeName(OpNodes[j], CGP)]
1556             .insert(PatternsByOpcode[getOpcodeName(OpNodes[j], CGP)].begin(),
1557                     &Pattern);
1558         }
1559       } else {
1560         errs() << "Unrecognized opcode '";
1561         Node->dump();
1562         errs() << "' on tree pattern '";
1563         errs() << Pattern.getDstPattern()->getOperator()->getName() << "'!\n";
1564         exit(1);
1565       }
1566     }
1567   }
1568
1569   // For each opcode, there might be multiple select functions, one per
1570   // ValueType of the node (or its first operand if it doesn't produce a
1571   // non-chain result.
1572   std::map<std::string, std::vector<std::string> > OpcodeVTMap;
1573
1574   // Emit one Select_* method for each top-level opcode.  We do this instead of
1575   // emitting one giant switch statement to support compilers where this will
1576   // result in the recursive functions taking less stack space.
1577   for (std::map<std::string, std::vector<const PatternToMatch*> >::iterator
1578          PBOI = PatternsByOpcode.begin(), E = PatternsByOpcode.end();
1579        PBOI != E; ++PBOI) {
1580     const std::string &OpName = PBOI->first;
1581     std::vector<const PatternToMatch*> &PatternsOfOp = PBOI->second;
1582     assert(!PatternsOfOp.empty() && "No patterns but map has entry?");
1583
1584     // Split them into groups by type.
1585     std::map<MVT::SimpleValueType,
1586              std::vector<const PatternToMatch*> > PatternsByType;
1587     for (unsigned i = 0, e = PatternsOfOp.size(); i != e; ++i) {
1588       const PatternToMatch *Pat = PatternsOfOp[i];
1589       TreePatternNode *SrcPat = Pat->getSrcPattern();
1590       PatternsByType[SrcPat->getTypeNum(0)].push_back(Pat);
1591     }
1592
1593     for (std::map<MVT::SimpleValueType,
1594                   std::vector<const PatternToMatch*> >::iterator
1595            II = PatternsByType.begin(), EE = PatternsByType.end(); II != EE;
1596          ++II) {
1597       MVT::SimpleValueType OpVT = II->first;
1598       std::vector<const PatternToMatch*> &Patterns = II->second;
1599       typedef std::pair<unsigned, std::string> CodeLine;
1600       typedef std::vector<CodeLine> CodeList;
1601       typedef CodeList::iterator CodeListI;
1602
1603       std::vector<std::pair<const PatternToMatch*, CodeList> > CodeForPatterns;
1604       std::vector<std::vector<std::string> > PatternOpcodes;
1605       std::vector<std::vector<std::string> > PatternVTs;
1606       std::vector<std::set<std::string> > PatternDecls;
1607       std::vector<bool> OutputIsVariadicFlags;
1608       std::vector<unsigned> NumInputRootOpsCounts;
1609       for (unsigned i = 0, e = Patterns.size(); i != e; ++i) {
1610         CodeList GeneratedCode;
1611         std::set<std::string> GeneratedDecl;
1612         std::vector<std::string> TargetOpcodes;
1613         std::vector<std::string> TargetVTs;
1614         bool OutputIsVariadic;
1615         unsigned NumInputRootOps;
1616         GenerateCodeForPattern(*Patterns[i], GeneratedCode, GeneratedDecl,
1617                                TargetOpcodes, TargetVTs,
1618                                OutputIsVariadic, NumInputRootOps);
1619         CodeForPatterns.push_back(std::make_pair(Patterns[i], GeneratedCode));
1620         PatternDecls.push_back(GeneratedDecl);
1621         PatternOpcodes.push_back(TargetOpcodes);
1622         PatternVTs.push_back(TargetVTs);
1623         OutputIsVariadicFlags.push_back(OutputIsVariadic);
1624         NumInputRootOpsCounts.push_back(NumInputRootOps);
1625       }
1626
1627       // Factor target node emission code (emitted by EmitResultCode) into
1628       // separate functions. Uniquing and share them among all instruction
1629       // selection routines.
1630       for (unsigned i = 0, e = CodeForPatterns.size(); i != e; ++i) {
1631         CodeList &GeneratedCode = CodeForPatterns[i].second;
1632         std::vector<std::string> &TargetOpcodes = PatternOpcodes[i];
1633         std::vector<std::string> &TargetVTs = PatternVTs[i];
1634         std::set<std::string> Decls = PatternDecls[i];
1635         bool OutputIsVariadic = OutputIsVariadicFlags[i];
1636         unsigned NumInputRootOps = NumInputRootOpsCounts[i];
1637         std::vector<std::string> AddedInits;
1638         int CodeSize = (int)GeneratedCode.size();
1639         int LastPred = -1;
1640         for (int j = CodeSize-1; j >= 0; --j) {
1641           if (LastPred == -1 && GeneratedCode[j].first == 1)
1642             LastPred = j;
1643           else if (LastPred != -1 && GeneratedCode[j].first == 2)
1644             AddedInits.push_back(GeneratedCode[j].second);
1645         }
1646
1647         std::string CalleeCode = "(SDNode *N";
1648         std::string CallerCode = "(N";
1649         for (unsigned j = 0, e = TargetOpcodes.size(); j != e; ++j) {
1650           CalleeCode += ", unsigned Opc" + utostr(j);
1651           CallerCode += ", " + TargetOpcodes[j];
1652         }
1653         for (unsigned j = 0, e = TargetVTs.size(); j != e; ++j) {
1654           CalleeCode += ", MVT::SimpleValueType VT" + utostr(j);
1655           CallerCode += ", " + TargetVTs[j];
1656         }
1657         for (std::set<std::string>::iterator
1658                I = Decls.begin(), E = Decls.end(); I != E; ++I) {
1659           std::string Name = *I;
1660           CalleeCode += ", SDValue &" + Name;
1661           CallerCode += ", " + Name;
1662         }
1663
1664         if (OutputIsVariadic) {
1665           CalleeCode += ", unsigned NumInputRootOps";
1666           CallerCode += ", " + utostr(NumInputRootOps);
1667         }
1668
1669         CallerCode += ");";
1670         CalleeCode += ") {\n";
1671
1672         for (std::vector<std::string>::const_reverse_iterator
1673                I = AddedInits.rbegin(), E = AddedInits.rend(); I != E; ++I)
1674           CalleeCode += "  " + *I + "\n";
1675
1676         for (int j = LastPred+1; j < CodeSize; ++j)
1677           CalleeCode += "  " + GeneratedCode[j].second + "\n";
1678         for (int j = LastPred+1; j < CodeSize; ++j)
1679           GeneratedCode.pop_back();
1680         CalleeCode += "}\n";
1681
1682         // Uniquing the emission routines.
1683         unsigned EmitFuncNum;
1684         std::map<std::string, unsigned>::iterator EFI =
1685           EmitFunctions.find(CalleeCode);
1686         if (EFI != EmitFunctions.end()) {
1687           EmitFuncNum = EFI->second;
1688         } else {
1689           EmitFuncNum = EmitFunctions.size();
1690           EmitFunctions.insert(std::make_pair(CalleeCode, EmitFuncNum));
1691           // Prevent emission routines from being inlined to reduce selection
1692           // routines stack frame sizes.
1693           OS << "DISABLE_INLINE ";
1694           OS << "SDNode *Emit_" << utostr(EmitFuncNum) << CalleeCode;
1695         }
1696
1697         // Replace the emission code within selection routines with calls to the
1698         // emission functions.
1699         if (GenDebug)
1700           GeneratedCode.push_back(std::make_pair(0,
1701                                       "CurDAG->setSubgraphColor(N, \"red\");"));
1702         CallerCode = "SDNode *Result = Emit_" + utostr(EmitFuncNum) +CallerCode;
1703         GeneratedCode.push_back(std::make_pair(3, CallerCode));
1704         if (GenDebug) {
1705           GeneratedCode.push_back(std::make_pair(0, "if(Result) {"));
1706           GeneratedCode.push_back(std::make_pair(0,
1707                             "  CurDAG->setSubgraphColor(Result, \"yellow\");"));
1708           GeneratedCode.push_back(std::make_pair(0,
1709                              "  CurDAG->setSubgraphColor(Result, \"black\");"));
1710           GeneratedCode.push_back(std::make_pair(0, "}"));
1711         }
1712         GeneratedCode.push_back(std::make_pair(0, "return Result;"));
1713       }
1714
1715       // Print function.
1716       std::string OpVTStr;
1717       if (OpVT == MVT::iPTR) {
1718         OpVTStr = "_iPTR";
1719       } else if (OpVT == MVT::iPTRAny) {
1720         OpVTStr = "_iPTRAny";
1721       } else if (OpVT == MVT::isVoid) {
1722         // Nodes with a void result actually have a first result type of either
1723         // Other (a chain) or Flag.  Since there is no one-to-one mapping from
1724         // void to this case, we handle it specially here.
1725       } else {
1726         OpVTStr = "_" + getEnumName(OpVT).substr(5);  // Skip 'MVT::'
1727       }
1728       std::map<std::string, std::vector<std::string> >::iterator OpVTI =
1729         OpcodeVTMap.find(OpName);
1730       if (OpVTI == OpcodeVTMap.end()) {
1731         std::vector<std::string> VTSet;
1732         VTSet.push_back(OpVTStr);
1733         OpcodeVTMap.insert(std::make_pair(OpName, VTSet));
1734       } else
1735         OpVTI->second.push_back(OpVTStr);
1736
1737       // We want to emit all of the matching code now.  However, we want to emit
1738       // the matches in order of minimal cost.  Sort the patterns so the least
1739       // cost one is at the start.
1740       std::stable_sort(CodeForPatterns.begin(), CodeForPatterns.end(),
1741                        PatternSortingPredicate(CGP));
1742
1743       // Scan the code to see if all of the patterns are reachable and if it is
1744       // possible that the last one might not match.
1745       bool mightNotMatch = true;
1746       for (unsigned i = 0, e = CodeForPatterns.size(); i != e; ++i) {
1747         CodeList &GeneratedCode = CodeForPatterns[i].second;
1748         mightNotMatch = false;
1749
1750         for (unsigned j = 0, e = GeneratedCode.size(); j != e; ++j) {
1751           if (GeneratedCode[j].first == 1) { // predicate.
1752             mightNotMatch = true;
1753             break;
1754           }
1755         }
1756
1757         // If this pattern definitely matches, and if it isn't the last one, the
1758         // patterns after it CANNOT ever match.  Error out.
1759         if (mightNotMatch == false && i != CodeForPatterns.size()-1) {
1760           errs() << "Pattern '";
1761           CodeForPatterns[i].first->getSrcPattern()->print(errs());
1762           errs() << "' is impossible to select!\n";
1763           exit(1);
1764         }
1765       }
1766
1767       // Loop through and reverse all of the CodeList vectors, as we will be
1768       // accessing them from their logical front, but accessing the end of a
1769       // vector is more efficient.
1770       for (unsigned i = 0, e = CodeForPatterns.size(); i != e; ++i) {
1771         CodeList &GeneratedCode = CodeForPatterns[i].second;
1772         std::reverse(GeneratedCode.begin(), GeneratedCode.end());
1773       }
1774
1775       // Next, reverse the list of patterns itself for the same reason.
1776       std::reverse(CodeForPatterns.begin(), CodeForPatterns.end());
1777
1778       OS << "SDNode *Select_" << getLegalCName(OpName)
1779          << OpVTStr << "(SDNode *N) {\n";
1780
1781       // Emit all of the patterns now, grouped together to share code.
1782       EmitPatterns(CodeForPatterns, 2, OS);
1783
1784       // If the last pattern has predicates (which could fail) emit code to
1785       // catch the case where nothing handles a pattern.
1786       if (mightNotMatch) {
1787         OS << "\n";
1788         OS << "  CannotYetSelect(N);\n";
1789         OS << "  return NULL;\n";
1790       }
1791       OS << "}\n\n";
1792     }
1793   }
1794
1795   OS << "// The main instruction selector code.\n"
1796      << "SDNode *SelectCode(SDNode *N) {\n"
1797      << "  MVT::SimpleValueType NVT = N->getValueType(0).getSimpleVT().SimpleTy;\n"
1798      << "  switch (N->getOpcode()) {\n"
1799      << "  default:\n"
1800      << "    assert(!N->isMachineOpcode() && \"Node already selected!\");\n"
1801      << "    break;\n"
1802      << "  case ISD::EntryToken:       // These nodes remain the same.\n"
1803      << "  case ISD::BasicBlock:\n"
1804      << "  case ISD::Register:\n"
1805      << "  case ISD::HANDLENODE:\n"
1806      << "  case ISD::TargetConstant:\n"
1807      << "  case ISD::TargetConstantFP:\n"
1808      << "  case ISD::TargetConstantPool:\n"
1809      << "  case ISD::TargetFrameIndex:\n"
1810      << "  case ISD::TargetExternalSymbol:\n"
1811      << "  case ISD::TargetBlockAddress:\n"
1812      << "  case ISD::TargetJumpTable:\n"
1813      << "  case ISD::TargetGlobalTLSAddress:\n"
1814      << "  case ISD::TargetGlobalAddress:\n"
1815      << "  case ISD::TokenFactor:\n"
1816      << "  case ISD::CopyFromReg:\n"
1817      << "  case ISD::CopyToReg: {\n"
1818      << "    return NULL;\n"
1819      << "  }\n"
1820      << "  case ISD::AssertSext:\n"
1821      << "  case ISD::AssertZext: {\n"
1822      << "    ReplaceUses(SDValue(N, 0), N->getOperand(0));\n"
1823      << "    return NULL;\n"
1824      << "  }\n"
1825      << "  case ISD::INLINEASM: return Select_INLINEASM(N);\n"
1826      << "  case ISD::EH_LABEL: return Select_EH_LABEL(N);\n"
1827      << "  case ISD::UNDEF: return Select_UNDEF(N);\n";
1828
1829   // Loop over all of the case statements, emiting a call to each method we
1830   // emitted above.
1831   for (std::map<std::string, std::vector<const PatternToMatch*> >::iterator
1832          PBOI = PatternsByOpcode.begin(), E = PatternsByOpcode.end();
1833        PBOI != E; ++PBOI) {
1834     const std::string &OpName = PBOI->first;
1835     // Potentially multiple versions of select for this opcode. One for each
1836     // ValueType of the node (or its first true operand if it doesn't produce a
1837     // result.
1838     std::map<std::string, std::vector<std::string> >::iterator OpVTI =
1839       OpcodeVTMap.find(OpName);
1840     std::vector<std::string> &OpVTs = OpVTI->second;
1841     OS << "  case " << OpName << ": {\n";
1842     // If we have only one variant and it's the default, elide the
1843     // switch.  Marginally faster, and makes MSVC happier.
1844     if (OpVTs.size()==1 && OpVTs[0].empty()) {
1845       OS << "    return Select_" << getLegalCName(OpName) << "(N);\n";
1846       OS << "    break;\n";
1847       OS << "  }\n";
1848       continue;
1849     }
1850     // Keep track of whether we see a pattern that has an iPtr result.
1851     bool HasPtrPattern = false;
1852     bool HasDefaultPattern = false;
1853
1854     OS << "    switch (NVT) {\n";
1855     for (unsigned i = 0, e = OpVTs.size(); i < e; ++i) {
1856       std::string &VTStr = OpVTs[i];
1857       if (VTStr.empty()) {
1858         HasDefaultPattern = true;
1859         continue;
1860       }
1861
1862       // If this is a match on iPTR: don't emit it directly, we need special
1863       // code.
1864       if (VTStr == "_iPTR") {
1865         HasPtrPattern = true;
1866         continue;
1867       }
1868       OS << "    case MVT::" << VTStr.substr(1) << ":\n"
1869          << "      return Select_" << getLegalCName(OpName)
1870          << VTStr << "(N);\n";
1871     }
1872     OS << "    default:\n";
1873
1874     // If there is an iPTR result version of this pattern, emit it here.
1875     if (HasPtrPattern) {
1876       OS << "      if (TLI.getPointerTy() == NVT)\n";
1877       OS << "        return Select_" << getLegalCName(OpName) <<"_iPTR(N);\n";
1878     }
1879     if (HasDefaultPattern) {
1880       OS << "      return Select_" << getLegalCName(OpName) << "(N);\n";
1881     }
1882     OS << "      break;\n";
1883     OS << "    }\n";
1884     OS << "    break;\n";
1885     OS << "  }\n";
1886   }
1887
1888   OS << "  } // end of big switch.\n\n"
1889      << "  CannotYetSelect(N);\n"
1890      << "  return NULL;\n"
1891      << "}\n\n";
1892 }
1893
1894 namespace {
1895 // PatternSortingPredicate - return true if we prefer to match LHS before RHS.
1896 // In particular, we want to match maximal patterns first and lowest cost within
1897 // a particular complexity first.
1898 struct PatternSortingPredicate2 {
1899   PatternSortingPredicate2(CodeGenDAGPatterns &cgp) : CGP(cgp) {}
1900   CodeGenDAGPatterns &CGP;
1901
1902   bool operator()(const PatternToMatch *LHS,
1903                   const PatternToMatch *RHS) {
1904     unsigned LHSSize = getPatternSize(LHS->getSrcPattern(), CGP);
1905     unsigned RHSSize = getPatternSize(RHS->getSrcPattern(), CGP);
1906     LHSSize += LHS->getAddedComplexity();
1907     RHSSize += RHS->getAddedComplexity();
1908     if (LHSSize > RHSSize) return true;   // LHS -> bigger -> less cost
1909     if (LHSSize < RHSSize) return false;
1910
1911     // If the patterns have equal complexity, compare generated instruction cost
1912     unsigned LHSCost = getResultPatternCost(LHS->getDstPattern(), CGP);
1913     unsigned RHSCost = getResultPatternCost(RHS->getDstPattern(), CGP);
1914     if (LHSCost < RHSCost) return true;
1915     if (LHSCost > RHSCost) return false;
1916
1917     return getResultPatternSize(LHS->getDstPattern(), CGP) <
1918            getResultPatternSize(RHS->getDstPattern(), CGP);
1919   }
1920 };
1921 }
1922
1923
1924 void DAGISelEmitter::run(raw_ostream &OS) {
1925   EmitSourceFileHeader("DAG Instruction Selector for the " +
1926                        CGP.getTargetInfo().getName() + " target", OS);
1927
1928   OS << "// *** NOTE: This file is #included into the middle of the target\n"
1929      << "// *** instruction selector class.  These functions are really "
1930      << "methods.\n\n";
1931
1932   OS << "// Include standard, target-independent definitions and methods used\n"
1933      << "// by the instruction selector.\n";
1934   OS << "#include \"llvm/CodeGen/DAGISelHeader.h\"\n\n";
1935
1936   EmitNodeTransforms(OS);
1937   EmitPredicateFunctions(OS);
1938
1939   DEBUG(errs() << "\n\nALL PATTERNS TO MATCH:\n\n");
1940   for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(), E = CGP.ptm_end();
1941        I != E; ++I) {
1942     DEBUG(errs() << "PATTERN: ";   I->getSrcPattern()->dump());
1943     DEBUG(errs() << "\nRESULT:  "; I->getDstPattern()->dump());
1944     DEBUG(errs() << "\n");
1945   }
1946
1947 #ifdef ENABLE_NEW_ISEL
1948   MatcherNode *Matcher = 0;
1949
1950   // Add all the patterns to a temporary list so we can sort them.
1951   std::vector<const PatternToMatch*> Patterns;
1952   for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(), E = CGP.ptm_end();
1953        I != E; ++I)
1954     Patterns.push_back(&*I);
1955
1956   // We want to process the matches in order of minimal cost.  Sort the patterns
1957   // so the least cost one is at the start.
1958   // FIXME: Eliminate "PatternSortingPredicate" and rename.
1959   std::stable_sort(Patterns.begin(), Patterns.end(),
1960                    PatternSortingPredicate2(CGP));
1961
1962
1963   // Walk the patterns backwards (since we append to the front of the generated
1964   // code), building a matcher for each and adding it to the matcher for the
1965   // whole target.
1966   while (!Patterns.empty()) {
1967     const PatternToMatch &Pattern = *Patterns.back();
1968     Patterns.pop_back();
1969
1970     MatcherNode *N = ConvertPatternToMatcher(Pattern, CGP);
1971
1972     if (Matcher == 0)
1973       Matcher = N;
1974     else
1975       Matcher = new PushMatcherNode(N, Matcher);
1976   }
1977
1978   Matcher = OptimizeMatcher(Matcher);
1979   //Matcher->dump();
1980   EmitMatcherTable(Matcher, OS);
1981   delete Matcher;
1982
1983 #else
1984   // At this point, we have full information about the 'Patterns' we need to
1985   // parse, both implicitly from instructions as well as from explicit pattern
1986   // definitions.  Emit the resultant instruction selector.
1987   EmitInstructionSelector(OS);
1988 #endif
1989 }