FastISelEmitter.cpp revision 7b2e579546d1ebf49c2e187efab2c76be9e32050
1//===- FastISelEmitter.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 "fast" instruction selector. 11// 12// This instruction selection method is designed to emit very poor code 13// quickly. Also, it is not designed to do much lowering, so most illegal 14// types (e.g. i64 on 32-bit targets) and operations (e.g. calls) are not 15// supported and cannot easily be added. Blocks containing operations 16// that are not supported need to be handled by a more capable selector, 17// such as the SelectionDAG selector. 18// 19// The intended use for "fast" instruction selection is "-O0" mode 20// compilation, where the quality of the generated code is irrelevant when 21// weighed against the speed at which the code can be generated. 22// 23// If compile time is so important, you might wonder why we don't just 24// skip codegen all-together, emit LLVM bytecode files, and execute them 25// with an interpreter. The answer is that it would complicate linking and 26// debugging, and also because that isn't how a compiler is expected to 27// work in some circles. 28// 29// If you need better generated code or more lowering than what this 30// instruction selector provides, use the SelectionDAG (DAGISel) instruction 31// selector instead. If you're looking here because SelectionDAG isn't fast 32// enough, consider looking into improving the SelectionDAG infastructure 33// instead. At the time of this writing there remain several major 34// opportunities for improvement. 35// 36//===----------------------------------------------------------------------===// 37 38#include "FastISelEmitter.h" 39#include "Record.h" 40#include "llvm/Support/Debug.h" 41#include "llvm/Support/Streams.h" 42#include "llvm/ADT/VectorExtras.h" 43using namespace llvm; 44 45namespace { 46 47/// OperandsSignature - This class holds a description of a list of operand 48/// types. It has utility methods for emitting text based on the operands. 49/// 50struct OperandsSignature { 51 std::vector<std::string> Operands; 52 53 bool operator<(const OperandsSignature &O) const { 54 return Operands < O.Operands; 55 } 56 57 bool empty() const { return Operands.empty(); } 58 59 /// initialize - Examine the given pattern and initialize the contents 60 /// of the Operands array accordingly. Return true if all the operands 61 /// are supported, false otherwise. 62 /// 63 bool initialize(TreePatternNode *InstPatNode, 64 const CodeGenTarget &Target, 65 MVT::SimpleValueType VT, 66 const CodeGenRegisterClass *DstRC) { 67 if (!InstPatNode->isLeaf() && 68 InstPatNode->getOperator()->getName() == "imm") { 69 Operands.push_back("i"); 70 return true; 71 } 72 73 for (unsigned i = 0, e = InstPatNode->getNumChildren(); i != e; ++i) { 74 TreePatternNode *Op = InstPatNode->getChild(i); 75 // For now, filter out any operand with a predicate. 76 if (!Op->getPredicateFn().empty()) 77 return false; 78 // For now, filter out any operand with multiple values. 79 if (Op->getExtTypes().size() != 1) 80 return false; 81 // For now, all the operands must have the same type. 82 if (Op->getTypeNum(0) != VT) 83 return false; 84 if (!Op->isLeaf()) { 85 if (Op->getOperator()->getName() == "imm") { 86 Operands.push_back("i"); 87 return true; 88 } 89 // For now, ignore fpimm and other non-leaf nodes. 90 return false; 91 } 92 DefInit *OpDI = dynamic_cast<DefInit*>(Op->getLeafValue()); 93 if (!OpDI) 94 return false; 95 Record *OpLeafRec = OpDI->getDef(); 96 // TODO: handle instructions which have physreg operands. 97 if (OpLeafRec->isSubClassOf("Register")) 98 return false; 99 // For now, the only other thing we accept is register operands. 100 if (!OpLeafRec->isSubClassOf("RegisterClass")) 101 return false; 102 // For now, require the register operands' register classes to all 103 // be the same. 104 const CodeGenRegisterClass *RC = &Target.getRegisterClass(OpLeafRec); 105 if (!RC) 106 return false; 107 // For now, all the operands must have the same register class. 108 if (DstRC != RC) 109 return false; 110 Operands.push_back("r"); 111 } 112 return true; 113 } 114 115 void PrintParameters(std::ostream &OS) const { 116 for (unsigned i = 0, e = Operands.size(); i != e; ++i) { 117 if (Operands[i] == "r") { 118 OS << "unsigned Op" << i; 119 } else if (Operands[i] == "i") { 120 OS << "uint64_t imm" << i; 121 } else { 122 assert("Unknown operand kind!"); 123 abort(); 124 } 125 if (i + 1 != e) 126 OS << ", "; 127 } 128 } 129 130 void PrintArguments(std::ostream &OS) const { 131 for (unsigned i = 0, e = Operands.size(); i != e; ++i) { 132 if (Operands[i] == "r") { 133 OS << "Op" << i; 134 } else if (Operands[i] == "i") { 135 OS << "imm" << i; 136 } else { 137 assert("Unknown operand kind!"); 138 abort(); 139 } 140 if (i + 1 != e) 141 OS << ", "; 142 } 143 } 144 145 void PrintManglingSuffix(std::ostream &OS) const { 146 for (unsigned i = 0, e = Operands.size(); i != e; ++i) { 147 OS << Operands[i]; 148 } 149 } 150}; 151 152/// InstructionMemo - This class holds additional information about an 153/// instruction needed to emit code for it. 154/// 155struct InstructionMemo { 156 std::string Name; 157 const CodeGenRegisterClass *RC; 158}; 159 160} 161 162static std::string getOpcodeName(Record *Op, CodeGenDAGPatterns &CGP) { 163 return CGP.getSDNodeInfo(Op).getEnumName(); 164} 165 166static std::string getLegalCName(std::string OpName) { 167 std::string::size_type pos = OpName.find("::"); 168 if (pos != std::string::npos) 169 OpName.replace(pos, 2, "_"); 170 return OpName; 171} 172 173void FastISelEmitter::run(std::ostream &OS) { 174 EmitSourceFileHeader("\"Fast\" Instruction Selector for the " + 175 Target.getName() + " target", OS); 176 177 OS << "#include \"llvm/CodeGen/FastISel.h\"\n"; 178 OS << "\n"; 179 OS << "namespace llvm {\n"; 180 OS << "\n"; 181 OS << "namespace " << InstNS.substr(0, InstNS.size() - 2) << " {\n"; 182 OS << "\n"; 183 184 typedef std::map<std::string, InstructionMemo> PredMap; 185 typedef std::map<MVT::SimpleValueType, PredMap> RetPredMap; 186 typedef std::map<MVT::SimpleValueType, RetPredMap> TypeRetPredMap; 187 typedef std::map<std::string, TypeRetPredMap> OpcodeTypeRetPredMap; 188 typedef std::map<OperandsSignature, OpcodeTypeRetPredMap> OperandsOpcodeTypeRetPredMap; 189 OperandsOpcodeTypeRetPredMap SimplePatterns; 190 191 // Scan through all the patterns and record the simple ones. 192 for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(), 193 E = CGP.ptm_end(); I != E; ++I) { 194 const PatternToMatch &Pattern = *I; 195 196 // For now, just look at Instructions, so that we don't have to worry 197 // about emitting multiple instructions for a pattern. 198 TreePatternNode *Dst = Pattern.getDstPattern(); 199 if (Dst->isLeaf()) continue; 200 Record *Op = Dst->getOperator(); 201 if (!Op->isSubClassOf("Instruction")) 202 continue; 203 CodeGenInstruction &II = CGP.getTargetInfo().getInstruction(Op->getName()); 204 if (II.OperandList.empty()) 205 continue; 206 207 // For now, ignore instructions where the first operand is not an 208 // output register. 209 Record *Op0Rec = II.OperandList[0].Rec; 210 if (!Op0Rec->isSubClassOf("RegisterClass")) 211 continue; 212 const CodeGenRegisterClass *DstRC = &Target.getRegisterClass(Op0Rec); 213 if (!DstRC) 214 continue; 215 216 // Inspect the pattern. 217 TreePatternNode *InstPatNode = Pattern.getSrcPattern(); 218 if (!InstPatNode) continue; 219 if (InstPatNode->isLeaf()) continue; 220 221 Record *InstPatOp = InstPatNode->getOperator(); 222 std::string OpcodeName = getOpcodeName(InstPatOp, CGP); 223 MVT::SimpleValueType VT = InstPatNode->getTypeNum(0); 224 225 // For now, filter out instructions which just set a register to 226 // an Operand or an immediate, like MOV32ri. 227 if (InstPatOp->isSubClassOf("Operand")) 228 continue; 229 230 // For now, filter out any instructions with predicates. 231 if (!InstPatNode->getPredicateFn().empty()) 232 continue; 233 234 // Check all the operands. 235 OperandsSignature Operands; 236 if (!Operands.initialize(InstPatNode, Target, VT, DstRC)) 237 continue; 238 239 // Get the predicate that guards this pattern. 240 std::string PredicateCheck = Pattern.getPredicateCheck(); 241 242 // Ok, we found a pattern that we can handle. Remember it. 243 InstructionMemo Memo = { 244 Pattern.getDstPattern()->getOperator()->getName(), 245 DstRC 246 }; 247 assert(!SimplePatterns[Operands][OpcodeName][VT][VT].count(PredicateCheck) && 248 "Duplicate pattern!"); 249 SimplePatterns[Operands][OpcodeName][VT][VT][PredicateCheck] = Memo; 250 } 251 252 // Declare the target FastISel class. 253 OS << "class FastISel : public llvm::FastISel {\n"; 254 for (OperandsOpcodeTypeRetPredMap::const_iterator OI = SimplePatterns.begin(), 255 OE = SimplePatterns.end(); OI != OE; ++OI) { 256 const OperandsSignature &Operands = OI->first; 257 const OpcodeTypeRetPredMap &OTM = OI->second; 258 259 for (OpcodeTypeRetPredMap::const_iterator I = OTM.begin(), E = OTM.end(); 260 I != E; ++I) { 261 const std::string &Opcode = I->first; 262 const TypeRetPredMap &TM = I->second; 263 264 for (TypeRetPredMap::const_iterator TI = TM.begin(), TE = TM.end(); 265 TI != TE; ++TI) { 266 MVT::SimpleValueType VT = TI->first; 267 268 OS << " unsigned FastEmit_" << getLegalCName(Opcode) 269 << "_" << getLegalCName(getName(VT)) << "_"; 270 Operands.PrintManglingSuffix(OS); 271 OS << "("; 272 Operands.PrintParameters(OS); 273 OS << ");\n"; 274 } 275 276 OS << " unsigned FastEmit_" << getLegalCName(Opcode) << "_"; 277 Operands.PrintManglingSuffix(OS); 278 OS << "(MVT::SimpleValueType VT"; 279 if (!Operands.empty()) 280 OS << ", "; 281 Operands.PrintParameters(OS); 282 OS << ");\n"; 283 } 284 285 OS << " unsigned FastEmit_"; 286 Operands.PrintManglingSuffix(OS); 287 OS << "(MVT::SimpleValueType VT, ISD::NodeType Opcode"; 288 if (!Operands.empty()) 289 OS << ", "; 290 Operands.PrintParameters(OS); 291 OS << ");\n"; 292 } 293 OS << "\n"; 294 295 // Declare the Subtarget member, which is used for predicate checks. 296 OS << " const " << InstNS.substr(0, InstNS.size() - 2) 297 << "Subtarget *Subtarget;\n"; 298 OS << "\n"; 299 300 // Declare the constructor. 301 OS << "public:\n"; 302 OS << " explicit FastISel(MachineFunction &mf)\n"; 303 OS << " : llvm::FastISel(mf),\n"; 304 OS << " Subtarget(&TM.getSubtarget<" << InstNS.substr(0, InstNS.size() - 2) 305 << "Subtarget>()) {}\n"; 306 OS << "};\n"; 307 OS << "\n"; 308 309 // Define the target FastISel creation function. 310 OS << "llvm::FastISel *createFastISel(MachineFunction &mf) {\n"; 311 OS << " return new FastISel(mf);\n"; 312 OS << "}\n"; 313 OS << "\n"; 314 315 // Now emit code for all the patterns that we collected. 316 for (OperandsOpcodeTypeRetPredMap::const_iterator OI = SimplePatterns.begin(), 317 OE = SimplePatterns.end(); OI != OE; ++OI) { 318 const OperandsSignature &Operands = OI->first; 319 const OpcodeTypeRetPredMap &OTM = OI->second; 320 321 for (OpcodeTypeRetPredMap::const_iterator I = OTM.begin(), E = OTM.end(); 322 I != E; ++I) { 323 const std::string &Opcode = I->first; 324 const TypeRetPredMap &TM = I->second; 325 326 OS << "// FastEmit functions for " << Opcode << ".\n"; 327 OS << "\n"; 328 329 // Emit one function for each opcode,type pair. 330 for (TypeRetPredMap::const_iterator TI = TM.begin(), TE = TM.end(); 331 TI != TE; ++TI) { 332 MVT::SimpleValueType VT = TI->first; 333 const RetPredMap &RM = TI->second; 334 335 for (RetPredMap::const_iterator RI = RM.begin(), RE = RM.end(); 336 RI != RE; ++RI) { 337 const PredMap &PM = RI->second; 338 bool HasPred = false; 339 340 OS << "unsigned FastISel::FastEmit_" 341 << getLegalCName(Opcode) 342 << "_" << getLegalCName(getName(VT)) << "_"; 343 Operands.PrintManglingSuffix(OS); 344 OS << "("; 345 Operands.PrintParameters(OS); 346 OS << ") {\n"; 347 348 // Emit code for each possible instruction. There may be 349 // multiple if there are subtarget concerns. 350 for (PredMap::const_iterator PI = PM.begin(), PE = PM.end(); 351 PI != PE; ++PI) { 352 std::string PredicateCheck = PI->first; 353 const InstructionMemo &Memo = PI->second; 354 355 if (PredicateCheck.empty()) { 356 assert(!HasPred && 357 "Multiple instructions match, at least one has " 358 "a predicate and at least one doesn't!"); 359 } else { 360 OS << " if (" + PredicateCheck + ")\n"; 361 OS << " "; 362 HasPred = true; 363 } 364 OS << " return FastEmitInst_"; 365 Operands.PrintManglingSuffix(OS); 366 OS << "(" << InstNS << Memo.Name << ", "; 367 OS << InstNS << Memo.RC->getName() << "RegisterClass"; 368 if (!Operands.empty()) 369 OS << ", "; 370 Operands.PrintArguments(OS); 371 OS << ");\n"; 372 } 373 // Return 0 if none of the predicates were satisfied. 374 if (HasPred) 375 OS << " return 0;\n"; 376 OS << "}\n"; 377 OS << "\n"; 378 } 379 } 380 381 // Emit one function for the opcode that demultiplexes based on the type. 382 OS << "unsigned FastISel::FastEmit_" 383 << getLegalCName(Opcode) << "_"; 384 Operands.PrintManglingSuffix(OS); 385 OS << "(MVT::SimpleValueType VT"; 386 if (!Operands.empty()) 387 OS << ", "; 388 Operands.PrintParameters(OS); 389 OS << ") {\n"; 390 OS << " switch (VT) {\n"; 391 for (TypeRetPredMap::const_iterator TI = TM.begin(), TE = TM.end(); 392 TI != TE; ++TI) { 393 MVT::SimpleValueType VT = TI->first; 394 std::string TypeName = getName(VT); 395 OS << " case " << TypeName << ": return FastEmit_" 396 << getLegalCName(Opcode) << "_" << getLegalCName(TypeName) << "_"; 397 Operands.PrintManglingSuffix(OS); 398 OS << "("; 399 Operands.PrintArguments(OS); 400 OS << ");\n"; 401 } 402 OS << " default: return 0;\n"; 403 OS << " }\n"; 404 OS << "}\n"; 405 OS << "\n"; 406 } 407 408 OS << "// Top-level FastEmit function.\n"; 409 OS << "\n"; 410 411 // Emit one function for the operand signature that demultiplexes based 412 // on opcode and type. 413 OS << "unsigned FastISel::FastEmit_"; 414 Operands.PrintManglingSuffix(OS); 415 OS << "(MVT::SimpleValueType VT, ISD::NodeType Opcode"; 416 if (!Operands.empty()) 417 OS << ", "; 418 Operands.PrintParameters(OS); 419 OS << ") {\n"; 420 OS << " switch (Opcode) {\n"; 421 for (OpcodeTypeRetPredMap::const_iterator I = OTM.begin(), E = OTM.end(); 422 I != E; ++I) { 423 const std::string &Opcode = I->first; 424 425 OS << " case " << Opcode << ": return FastEmit_" 426 << getLegalCName(Opcode) << "_"; 427 Operands.PrintManglingSuffix(OS); 428 OS << "(VT"; 429 if (!Operands.empty()) 430 OS << ", "; 431 Operands.PrintArguments(OS); 432 OS << ");\n"; 433 } 434 OS << " default: return 0;\n"; 435 OS << " }\n"; 436 OS << "}\n"; 437 OS << "\n"; 438 } 439 440 OS << "} // namespace X86\n"; 441 OS << "\n"; 442 OS << "} // namespace llvm\n"; 443} 444 445FastISelEmitter::FastISelEmitter(RecordKeeper &R) 446 : Records(R), 447 CGP(R), 448 Target(CGP.getTargetInfo()), 449 InstNS(Target.getInstNamespace() + "::") { 450 451 assert(InstNS.size() > 2 && "Can't determine target-specific namespace!"); 452} 453