contrib/llvm/utils/TableGen/GlobalISelEmitter.cpp

   1 //===- GlobalISelEmitter.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 /// \file
  11 /// This tablegen backend emits code for use by the GlobalISel instruction
  12 /// selector. See include/llvm/CodeGen/TargetGlobalISel.td.
  13 ///
  14 /// This file analyzes the patterns recognized by the SelectionDAGISel tablegen
  15 /// backend, filters out the ones that are unsupported, maps
  16 /// SelectionDAG-specific constructs to their GlobalISel counterpart
  17 /// (when applicable: MVT to LLT;  SDNode to generic Instruction).
  18 ///
  19 /// Not all patterns are supported: pass the tablegen invocation
  20 /// "-warn-on-skipped-patterns" to emit a warning when a pattern is skipped,
  21 /// as well as why.
  22 ///
  23 /// The generated file defines a single method:
  24 ///     bool <Target>InstructionSelector::selectImpl(MachineInstr &I) const;
  25 /// intended to be used in InstructionSelector::select as the first-step
  26 /// selector for the patterns that don't require complex C++.
  27 ///
  28 /// FIXME: We'll probably want to eventually define a base
  29 /// "TargetGenInstructionSelector" class.
  30 ///
  31 //===----------------------------------------------------------------------===//
  32
  33 #include "CodeGenDAGPatterns.h"
  34 #include "llvm/ADT/Optional.h"
  35 #include "llvm/ADT/Statistic.h"
  36 #include "llvm/CodeGen/MachineValueType.h"
  37 #include "llvm/Support/CommandLine.h"
  38 #include "llvm/TableGen/Error.h"
  39 #include "llvm/TableGen/Record.h"
  40 #include "llvm/TableGen/TableGenBackend.h"
  41 #include <string>
  42 using namespace llvm;
  43
  44 #define DEBUG_TYPE "gisel-emitter"
  45
  46 STATISTIC(NumPatternTotal, "Total number of patterns");
  47 STATISTIC(NumPatternSkipped, "Number of patterns skipped");
  48 STATISTIC(NumPatternEmitted, "Number of patterns emitted");
  49
  50 static cl::opt<bool> WarnOnSkippedPatterns(
  51     "warn-on-skipped-patterns",
  52     cl::desc("Explain why a pattern was skipped for inclusion "
  53              "in the GlobalISel selector"),
  54     cl::init(false));
  55
  56 namespace {
  57
  58 class GlobalISelEmitter {
  59 public:
  60   explicit GlobalISelEmitter(RecordKeeper &RK);
  61   void run(raw_ostream &OS);
  62
  63 private:
  64   const RecordKeeper &RK;
  65   const CodeGenDAGPatterns CGP;
  66   const CodeGenTarget &Target;
  67
  68   /// Keep track of the equivalence between SDNodes and Instruction.
  69   /// This is defined using 'GINodeEquiv' in the target description.
  70   DenseMap<Record *, const CodeGenInstruction *> NodeEquivs;
  71
  72   void gatherNodeEquivs();
  73   const CodeGenInstruction *findNodeEquiv(Record *N);
  74
  75   struct SkipReason {
  76     std::string Reason;
  77   };
  78
  79   /// Analyze pattern \p P, possibly emitting matching code for it to \p OS.
  80   /// Otherwise, return a reason why this pattern was skipped for emission.
  81   Optional<SkipReason> runOnPattern(const PatternToMatch &P,
  82                                     raw_ostream &OS);
  83 };
  84
  85 } // end anonymous namespace
  86
  87 //===- Helper functions ---------------------------------------------------===//
  88
  89 /// Convert an MVT to an equivalent LLT if possible, or the invalid LLT() for
  90 /// MVTs that don't map cleanly to an LLT (e.g., iPTR, *any, ...).
  91 static Optional<std::string> MVTToLLT(MVT::SimpleValueType SVT) {
  92   std::string TyStr;
  93   raw_string_ostream OS(TyStr);
  94   MVT VT(SVT);
  95   if (VT.isVector() && VT.getVectorNumElements() != 1) {
  96     OS << "LLT::vector(" << VT.getVectorNumElements() << ", "
  97        << VT.getScalarSizeInBits() << ")";
  98   } else if (VT.isInteger() || VT.isFloatingPoint()) {
  99     OS << "LLT::scalar(" << VT.getSizeInBits() << ")";
 100   } else {
 101     return None;
 102   }
 103   OS.flush();
 104   return TyStr;
 105 }
 106
 107 static bool isTrivialOperatorNode(const TreePatternNode *N) {
 108   return !N->isLeaf() && !N->hasAnyPredicate() && !N->getTransformFn();
 109 }
 110
 111 //===- Matchers -----------------------------------------------------------===//
 112
 113 struct Matcher {
 114   virtual ~Matcher() {}
 115   virtual void emit(raw_ostream &OS) const = 0;
 116 };
 117
 118 raw_ostream &operator<<(raw_ostream &S, const Matcher &M) {
 119   M.emit(S);
 120   return S;
 121 }
 122
 123 struct MatchAction {
 124   virtual ~MatchAction() {}
 125   virtual void emit(raw_ostream &OS) const = 0;
 126 };
 127
 128 raw_ostream &operator<<(raw_ostream &S, const MatchAction &A) {
 129   A.emit(S);
 130   return S;
 131 }
 132
 133 struct MatchOpcode : public Matcher {
 134   MatchOpcode(const CodeGenInstruction *I) : I(I) {}
 135   const CodeGenInstruction *I;
 136
 137   virtual void emit(raw_ostream &OS) const {
 138     OS << "I.getOpcode() == " << I->Namespace << "::" << I->TheDef->getName();
 139   }
 140 };
 141
 142 struct MatchRegOpType : public Matcher {
 143   MatchRegOpType(unsigned OpIdx, std::string Ty)
 144       : OpIdx(OpIdx), Ty(Ty) {}
 145   unsigned OpIdx;
 146   std::string Ty;
 147
 148   virtual void emit(raw_ostream &OS) const {
 149     OS << "MRI.getType(I.getOperand(" << OpIdx << ").getReg()) == (" << Ty
 150        << ")";
 151   }
 152 };
 153
 154 struct MatchRegOpBank : public Matcher {
 155   MatchRegOpBank(unsigned OpIdx, const CodeGenRegisterClass &RC)
 156       : OpIdx(OpIdx), RC(RC) {}
 157   unsigned OpIdx;
 158   const CodeGenRegisterClass &RC;
 159
 160   virtual void emit(raw_ostream &OS) const {
 161     OS << "(&RBI.getRegBankFromRegClass(" << RC.getQualifiedName()
 162        << "RegClass) == RBI.getRegBank(I.getOperand(" << OpIdx
 163        << ").getReg(), MRI, TRI))";
 164   }
 165 };
 166
 167 struct MatchMBBOp : public Matcher {
 168   MatchMBBOp(unsigned OpIdx) : OpIdx(OpIdx) {}
 169   unsigned OpIdx;
 170
 171   virtual void emit(raw_ostream &OS) const {
 172     OS << "I.getOperand(" << OpIdx << ").isMBB()";
 173   }
 174 };
 175
 176 struct MutateOpcode : public MatchAction {
 177   MutateOpcode(const CodeGenInstruction *I) : I(I) {}
 178   const CodeGenInstruction *I;
 179
 180   virtual void emit(raw_ostream &OS) const {
 181     OS << "I.setDesc(TII.get(" << I->Namespace << "::" << I->TheDef->getName()
 182        << "));";
 183   }
 184 };
 185
 186 class MatcherEmitter {
 187   const PatternToMatch &P;
 188
 189 public:
 190   std::vector<std::unique_ptr<Matcher>> Matchers;
 191   std::vector<std::unique_ptr<MatchAction>> Actions;
 192
 193   MatcherEmitter(const PatternToMatch &P) : P(P) {}
 194
 195   void emit(raw_ostream &OS) {
 196     if (Matchers.empty())
 197       llvm_unreachable("Unexpected empty matcher!");
 198
 199     OS << "  // Src: " << *P.getSrcPattern() << "\n"
 200        << "  // Dst: " << *P.getDstPattern() << "\n";
 201
 202     OS << "  if ((" << *Matchers.front() << ")";
 203     for (auto &MA : makeArrayRef(Matchers).drop_front())
 204       OS << " &&\n      (" << *MA << ")";
 205     OS << ") {\n";
 206
 207     for (auto &MA : Actions)
 208       OS << "    " << *MA << "\n";
 209
 210     OS << "    constrainSelectedInstRegOperands(I, TII, TRI, RBI);\n";
 211     OS << "    return true;\n";
 212     OS << "  }\n";
 213   }
 214 };
 215
 216 //===- GlobalISelEmitter class --------------------------------------------===//
 217
 218 void GlobalISelEmitter::gatherNodeEquivs() {
 219   assert(NodeEquivs.empty());
 220   for (Record *Equiv : RK.getAllDerivedDefinitions("GINodeEquiv"))
 221     NodeEquivs[Equiv->getValueAsDef("Node")] =
 222         &Target.getInstruction(Equiv->getValueAsDef("I"));
 223 }
 224
 225 const CodeGenInstruction *GlobalISelEmitter::findNodeEquiv(Record *N) {
 226   return NodeEquivs.lookup(N);
 227 }
 228
 229 GlobalISelEmitter::GlobalISelEmitter(RecordKeeper &RK)
 230     : RK(RK), CGP(RK), Target(CGP.getTargetInfo()) {}
 231
 232 //===- Emitter ------------------------------------------------------------===//
 233
 234 Optional<GlobalISelEmitter::SkipReason>
 235 GlobalISelEmitter::runOnPattern(const PatternToMatch &P, raw_ostream &OS) {
 236
 237   // Keep track of the matchers and actions to emit.
 238   MatcherEmitter M(P);
 239
 240   // First, analyze the whole pattern.
 241   // If the entire pattern has a predicate (e.g., target features), ignore it.
 242   if (!P.getPredicates()->getValues().empty())
 243     return SkipReason{"Pattern has a predicate"};
 244
 245   // Physreg imp-defs require additional logic.  Ignore the pattern.
 246   if (!P.getDstRegs().empty())
 247     return SkipReason{"Pattern defines a physical register"};
 248
 249   // Next, analyze the pattern operators.
 250   TreePatternNode *Src = P.getSrcPattern();
 251   TreePatternNode *Dst = P.getDstPattern();
 252
 253   // If the root of either pattern isn't a simple operator, ignore it.
 254   if (!isTrivialOperatorNode(Dst))
 255     return SkipReason{"Dst pattern root isn't a trivial operator"};
 256   if (!isTrivialOperatorNode(Src))
 257     return SkipReason{"Src pattern root isn't a trivial operator"};
 258
 259   Record *DstOp = Dst->getOperator();
 260   if (!DstOp->isSubClassOf("Instruction"))
 261     return SkipReason{"Pattern operator isn't an instruction"};
 262
 263   auto &DstI = Target.getInstruction(DstOp);
 264
 265   auto SrcGIOrNull = findNodeEquiv(Src->getOperator());
 266   if (!SrcGIOrNull)
 267     return SkipReason{"Pattern operator lacks an equivalent Instruction"};
 268   auto &SrcGI = *SrcGIOrNull;
 269
 270   // The operators look good: match the opcode and mutate it to the new one.
 271   M.Matchers.emplace_back(new MatchOpcode(&SrcGI));
 272   M.Actions.emplace_back(new MutateOpcode(&DstI));
 273
 274   // Next, analyze the children, only accepting patterns that don't require
 275   // any change to operands.
 276   if (Src->getNumChildren() != Dst->getNumChildren())
 277     return SkipReason{"Src/dst patterns have a different # of children"};
 278
 279   unsigned OpIdx = 0;
 280
 281   // Start with the defined operands (i.e., the results of the root operator).
 282   if (DstI.Operands.NumDefs != Src->getExtTypes().size())
 283     return SkipReason{"Src pattern results and dst MI defs are different"};
 284
 285   for (const EEVT::TypeSet &Ty : Src->getExtTypes()) {
 286     Record *DstIOpRec = DstI.Operands[OpIdx].Rec;
 287     if (!DstIOpRec->isSubClassOf("RegisterClass"))
 288       return SkipReason{"Dst MI def isn't a register class"};
 289
 290     auto OpTyOrNone = MVTToLLT(Ty.getConcrete());
 291     if (!OpTyOrNone)
 292       return SkipReason{"Dst operand has an unsupported type"};
 293
 294     M.Matchers.emplace_back(new MatchRegOpType(OpIdx, *OpTyOrNone));
 295     M.Matchers.emplace_back(
 296         new MatchRegOpBank(OpIdx, Target.getRegisterClass(DstIOpRec)));
 297     ++OpIdx;
 298   }
 299
 300   // Finally match the used operands (i.e., the children of the root operator).
 301   for (unsigned i = 0, e = Src->getNumChildren(); i != e; ++i) {
 302     auto *SrcChild = Src->getChild(i);
 303     auto *DstChild = Dst->getChild(i);
 304
 305     // Patterns can reorder operands.  Ignore those for now.
 306     if (SrcChild->getName() != DstChild->getName())
 307       return SkipReason{"Src/dst pattern children not in same order"};
 308
 309     // The only non-leaf child we accept is 'bb': it's an operator because
 310     // BasicBlockSDNode isn't inline, but in MI it's just another operand.
 311     if (!SrcChild->isLeaf()) {
 312       if (DstChild->isLeaf() ||
 313           SrcChild->getOperator() != DstChild->getOperator())
 314         return SkipReason{"Src/dst pattern child operator mismatch"};
 315
 316       if (SrcChild->getOperator()->isSubClassOf("SDNode")) {
 317         auto &ChildSDNI = CGP.getSDNodeInfo(SrcChild->getOperator());
 318         if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
 319           M.Matchers.emplace_back(new MatchMBBOp(OpIdx++));
 320           continue;
 321         }
 322       }
 323       return SkipReason{"Src pattern child isn't a leaf node"};
 324     }
 325
 326     if (SrcChild->getLeafValue() != DstChild->getLeafValue())
 327       return SkipReason{"Src/dst pattern child leaf mismatch"};
 328
 329     // Otherwise, we're looking for a bog-standard RegisterClass operand.
 330     if (SrcChild->hasAnyPredicate())
 331       return SkipReason{"Src pattern child has predicate"};
 332     auto *ChildRec = cast<DefInit>(SrcChild->getLeafValue())->getDef();
 333     if (!ChildRec->isSubClassOf("RegisterClass"))
 334       return SkipReason{"Src pattern child isn't a RegisterClass"};
 335
 336     ArrayRef<EEVT::TypeSet> ChildTypes = SrcChild->getExtTypes();
 337     if (ChildTypes.size() != 1)
 338       return SkipReason{"Src pattern child has multiple results"};
 339
 340     auto OpTyOrNone = MVTToLLT(ChildTypes.front().getConcrete());
 341     if (!OpTyOrNone)
 342       return SkipReason{"Src operand has an unsupported type"};
 343
 344     M.Matchers.emplace_back(new MatchRegOpType(OpIdx, *OpTyOrNone));
 345     M.Matchers.emplace_back(
 346         new MatchRegOpBank(OpIdx, Target.getRegisterClass(ChildRec)));
 347     ++OpIdx;
 348   }
 349
 350   // We're done with this pattern!  Emit the processed result.
 351   M.emit(OS);
 352   ++NumPatternEmitted;
 353   return None;
 354 }
 355
 356 void GlobalISelEmitter::run(raw_ostream &OS) {
 357   // Track the GINodeEquiv definitions.
 358   gatherNodeEquivs();
 359
 360   emitSourceFileHeader(("Global Instruction Selector for the " +
 361                        Target.getName() + " target").str(), OS);
 362   OS << "bool " << Target.getName()
 363      << "InstructionSelector::selectImpl"
 364         "(MachineInstr &I) const {\n  const MachineRegisterInfo &MRI = "
 365         "I.getParent()->getParent()->getRegInfo();\n";
 366
 367   // Look through the SelectionDAG patterns we found, possibly emitting some.
 368   for (const PatternToMatch &Pat : CGP.ptms()) {
 369     ++NumPatternTotal;
 370     if (auto SkipReason = runOnPattern(Pat, OS)) {
 371       if (WarnOnSkippedPatterns) {
 372         PrintWarning(Pat.getSrcRecord()->getLoc(),
 373                      "Skipped pattern: " + SkipReason->Reason);
 374       }
 375       ++NumPatternSkipped;
 376     }
 377   }
 378
 379   OS << "  return false;\n}\n";
 380 }
 381
 382 //===----------------------------------------------------------------------===//
 383
 384 namespace llvm {
 385 void EmitGlobalISel(RecordKeeper &RK, raw_ostream &OS) {
 386   GlobalISelEmitter(RK).run(OS);
 387 }
 388 } // End llvm namespace