1 //===- VarLenCodeEmitterGen.cpp - CEG for variable-length insts -----------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // The CodeEmitterGen component for variable-length instructions. 10 // 11 // The basic CodeEmitterGen is almost exclusively designed for fixed- 12 // length instructions. A good analogy for its encoding scheme is how printf 13 // works: The (immutable) formatting string represent the fixed values in the 14 // encoded instruction. Placeholders (i.e. %something), on the other hand, 15 // represent encoding for instruction operands. 16 // ``` 17 // printf("1101 %src 1001 %dst", <encoded value for operand `src`>, 18 // <encoded value for operand `dst`>); 19 // ``` 20 // VarLenCodeEmitterGen in this file provides an alternative encoding scheme 21 // that works more like a C++ stream operator: 22 // ``` 23 // OS << 0b1101; 24 // if (Cond) 25 // OS << OperandEncoding0; 26 // OS << 0b1001 << OperandEncoding1; 27 // ``` 28 // You are free to concatenate arbitrary types (and sizes) of encoding 29 // fragments on any bit position, bringing more flexibilities on defining 30 // encoding for variable-length instructions. 31 // 32 // In a more specific way, instruction encoding is represented by a DAG type 33 // `Inst` field. Here is an example: 34 // ``` 35 // dag Inst = (descend 0b1101, (operand "$src", 4), 0b1001, 36 // (operand "$dst", 4)); 37 // ``` 38 // It represents the following instruction encoding: 39 // ``` 40 // MSB LSB 41 // 1101<encoding for operand src>1001<encoding for operand dst> 42 // ``` 43 // For more details about DAG operators in the above snippet, please 44 // refer to \file include/llvm/Target/Target.td. 45 // 46 // VarLenCodeEmitter will convert the above DAG into the same helper function 47 // generated by CodeEmitter, `MCCodeEmitter::getBinaryCodeForInstr` (except 48 // for few details). 49 // 50 //===----------------------------------------------------------------------===// 51 52 #include "VarLenCodeEmitterGen.h" 53 #include "CodeGenHwModes.h" 54 #include "CodeGenInstruction.h" 55 #include "CodeGenTarget.h" 56 #include "InfoByHwMode.h" 57 #include "llvm/ADT/ArrayRef.h" 58 #include "llvm/ADT/DenseMap.h" 59 #include "llvm/Support/raw_ostream.h" 60 #include "llvm/TableGen/Error.h" 61 62 using namespace llvm; 63 64 namespace { 65 66 class VarLenCodeEmitterGen { 67 RecordKeeper &Records; 68 69 DenseMap<Record *, VarLenInst> VarLenInsts; 70 71 // Emit based values (i.e. fixed bits in the encoded instructions) 72 void emitInstructionBaseValues( 73 raw_ostream &OS, 74 ArrayRef<const CodeGenInstruction *> NumberedInstructions, 75 CodeGenTarget &Target, int HwMode = -1); 76 77 std::string getInstructionCase(Record *R, CodeGenTarget &Target); 78 std::string getInstructionCaseForEncoding(Record *R, Record *EncodingDef, 79 CodeGenTarget &Target); 80 81 public: 82 explicit VarLenCodeEmitterGen(RecordKeeper &R) : Records(R) {} 83 84 void run(raw_ostream &OS); 85 }; 86 87 } // end anonymous namespace 88 89 VarLenInst::VarLenInst(const DagInit *DI, const RecordVal *TheDef) 90 : TheDef(TheDef), NumBits(0U) { 91 buildRec(DI); 92 for (const auto &S : Segments) 93 NumBits += S.BitWidth; 94 } 95 96 void VarLenInst::buildRec(const DagInit *DI) { 97 assert(TheDef && "The def record is nullptr ?"); 98 99 std::string Op = DI->getOperator()->getAsString(); 100 101 if (Op == "ascend" || Op == "descend") { 102 bool Reverse = Op == "descend"; 103 int i = Reverse ? DI->getNumArgs() - 1 : 0; 104 int e = Reverse ? -1 : DI->getNumArgs(); 105 int s = Reverse ? -1 : 1; 106 for (; i != e; i += s) { 107 const Init *Arg = DI->getArg(i); 108 if (const auto *BI = dyn_cast<BitsInit>(Arg)) { 109 if (!BI->isComplete()) 110 PrintFatalError(TheDef->getLoc(), 111 "Expecting complete bits init in `" + Op + "`"); 112 Segments.push_back({BI->getNumBits(), BI}); 113 } else if (const auto *BI = dyn_cast<BitInit>(Arg)) { 114 if (!BI->isConcrete()) 115 PrintFatalError(TheDef->getLoc(), 116 "Expecting concrete bit init in `" + Op + "`"); 117 Segments.push_back({1, BI}); 118 } else if (const auto *SubDI = dyn_cast<DagInit>(Arg)) { 119 buildRec(SubDI); 120 } else { 121 PrintFatalError(TheDef->getLoc(), "Unrecognized type of argument in `" + 122 Op + "`: " + Arg->getAsString()); 123 } 124 } 125 } else if (Op == "operand") { 126 // (operand <operand name>, <# of bits>, [(encoder <custom encoder>)]) 127 if (DI->getNumArgs() < 2) 128 PrintFatalError(TheDef->getLoc(), 129 "Expecting at least 2 arguments for `operand`"); 130 HasDynamicSegment = true; 131 const Init *OperandName = DI->getArg(0), *NumBits = DI->getArg(1); 132 if (!isa<StringInit>(OperandName) || !isa<IntInit>(NumBits)) 133 PrintFatalError(TheDef->getLoc(), "Invalid argument types for `operand`"); 134 135 auto NumBitsVal = cast<IntInit>(NumBits)->getValue(); 136 if (NumBitsVal <= 0) 137 PrintFatalError(TheDef->getLoc(), "Invalid number of bits for `operand`"); 138 139 StringRef CustomEncoder; 140 if (DI->getNumArgs() >= 3) 141 CustomEncoder = getCustomEncoderName(DI->getArg(2)); 142 Segments.push_back( 143 {static_cast<unsigned>(NumBitsVal), OperandName, CustomEncoder}); 144 } else if (Op == "slice") { 145 // (slice <operand name>, <high / low bit>, <low / high bit>, 146 // [(encoder <custom encoder>)]) 147 if (DI->getNumArgs() < 3) 148 PrintFatalError(TheDef->getLoc(), 149 "Expecting at least 3 arguments for `slice`"); 150 HasDynamicSegment = true; 151 Init *OperandName = DI->getArg(0), *HiBit = DI->getArg(1), 152 *LoBit = DI->getArg(2); 153 if (!isa<StringInit>(OperandName) || !isa<IntInit>(HiBit) || 154 !isa<IntInit>(LoBit)) 155 PrintFatalError(TheDef->getLoc(), "Invalid argument types for `slice`"); 156 157 auto HiBitVal = cast<IntInit>(HiBit)->getValue(), 158 LoBitVal = cast<IntInit>(LoBit)->getValue(); 159 if (HiBitVal < 0 || LoBitVal < 0) 160 PrintFatalError(TheDef->getLoc(), "Invalid bit range for `slice`"); 161 bool NeedSwap = false; 162 unsigned NumBits = 0U; 163 if (HiBitVal < LoBitVal) { 164 NeedSwap = true; 165 NumBits = static_cast<unsigned>(LoBitVal - HiBitVal + 1); 166 } else { 167 NumBits = static_cast<unsigned>(HiBitVal - LoBitVal + 1); 168 } 169 170 StringRef CustomEncoder; 171 if (DI->getNumArgs() >= 4) 172 CustomEncoder = getCustomEncoderName(DI->getArg(3)); 173 174 if (NeedSwap) { 175 // Normalization: Hi bit should always be the second argument. 176 Init *const NewArgs[] = {OperandName, LoBit, HiBit}; 177 Segments.push_back({NumBits, 178 DagInit::get(DI->getOperator(), nullptr, NewArgs, {}), 179 CustomEncoder}); 180 } else { 181 Segments.push_back({NumBits, DI, CustomEncoder}); 182 } 183 } 184 } 185 186 void VarLenCodeEmitterGen::run(raw_ostream &OS) { 187 CodeGenTarget Target(Records); 188 auto Insts = Records.getAllDerivedDefinitions("Instruction"); 189 190 auto NumberedInstructions = Target.getInstructionsByEnumValue(); 191 const CodeGenHwModes &HWM = Target.getHwModes(); 192 193 // The set of HwModes used by instruction encodings. 194 std::set<unsigned> HwModes; 195 for (const CodeGenInstruction *CGI : NumberedInstructions) { 196 Record *R = CGI->TheDef; 197 198 // Create the corresponding VarLenInst instance. 199 if (R->getValueAsString("Namespace") == "TargetOpcode" || 200 R->getValueAsBit("isPseudo")) 201 continue; 202 203 if (const RecordVal *RV = R->getValue("EncodingInfos")) { 204 if (auto *DI = dyn_cast_or_null<DefInit>(RV->getValue())) { 205 EncodingInfoByHwMode EBM(DI->getDef(), HWM); 206 for (auto &KV : EBM) { 207 HwModes.insert(KV.first); 208 Record *EncodingDef = KV.second; 209 RecordVal *RV = EncodingDef->getValue("Inst"); 210 DagInit *DI = cast<DagInit>(RV->getValue()); 211 VarLenInsts.insert({EncodingDef, VarLenInst(DI, RV)}); 212 } 213 continue; 214 } 215 } 216 RecordVal *RV = R->getValue("Inst"); 217 DagInit *DI = cast<DagInit>(RV->getValue()); 218 VarLenInsts.insert({R, VarLenInst(DI, RV)}); 219 } 220 221 // Emit function declaration 222 OS << "void " << Target.getName() 223 << "MCCodeEmitter::getBinaryCodeForInstr(const MCInst &MI,\n" 224 << " SmallVectorImpl<MCFixup> &Fixups,\n" 225 << " APInt &Inst,\n" 226 << " APInt &Scratch,\n" 227 << " const MCSubtargetInfo &STI) const {\n"; 228 229 // Emit instruction base values 230 if (HwModes.empty()) { 231 emitInstructionBaseValues(OS, NumberedInstructions, Target); 232 } else { 233 for (unsigned HwMode : HwModes) 234 emitInstructionBaseValues(OS, NumberedInstructions, Target, (int)HwMode); 235 } 236 237 if (!HwModes.empty()) { 238 OS << " const unsigned **Index;\n"; 239 OS << " const uint64_t *InstBits;\n"; 240 OS << " unsigned HwMode = STI.getHwMode();\n"; 241 OS << " switch (HwMode) {\n"; 242 OS << " default: llvm_unreachable(\"Unknown hardware mode!\"); break;\n"; 243 for (unsigned I : HwModes) { 244 OS << " case " << I << ": InstBits = InstBits_" << HWM.getMode(I).Name 245 << "; Index = Index_" << HWM.getMode(I).Name << "; break;\n"; 246 } 247 OS << " };\n"; 248 } 249 250 // Emit helper function to retrieve base values. 251 OS << " auto getInstBits = [&](unsigned Opcode) -> APInt {\n" 252 << " unsigned NumBits = Index[Opcode][0];\n" 253 << " if (!NumBits)\n" 254 << " return APInt::getZeroWidth();\n" 255 << " unsigned Idx = Index[Opcode][1];\n" 256 << " ArrayRef<uint64_t> Data(&InstBits[Idx], " 257 << "APInt::getNumWords(NumBits));\n" 258 << " return APInt(NumBits, Data);\n" 259 << " };\n"; 260 261 // Map to accumulate all the cases. 262 std::map<std::string, std::vector<std::string>> CaseMap; 263 264 // Construct all cases statement for each opcode 265 for (Record *R : Insts) { 266 if (R->getValueAsString("Namespace") == "TargetOpcode" || 267 R->getValueAsBit("isPseudo")) 268 continue; 269 std::string InstName = 270 (R->getValueAsString("Namespace") + "::" + R->getName()).str(); 271 std::string Case = getInstructionCase(R, Target); 272 273 CaseMap[Case].push_back(std::move(InstName)); 274 } 275 276 // Emit initial function code 277 OS << " const unsigned opcode = MI.getOpcode();\n" 278 << " switch (opcode) {\n"; 279 280 // Emit each case statement 281 for (const auto &C : CaseMap) { 282 const std::string &Case = C.first; 283 const auto &InstList = C.second; 284 285 ListSeparator LS("\n"); 286 for (const auto &InstName : InstList) 287 OS << LS << " case " << InstName << ":"; 288 289 OS << " {\n"; 290 OS << Case; 291 OS << " break;\n" 292 << " }\n"; 293 } 294 // Default case: unhandled opcode 295 OS << " default:\n" 296 << " std::string msg;\n" 297 << " raw_string_ostream Msg(msg);\n" 298 << " Msg << \"Not supported instr: \" << MI;\n" 299 << " report_fatal_error(Msg.str().c_str());\n" 300 << " }\n"; 301 OS << "}\n\n"; 302 } 303 304 static void emitInstBits(raw_ostream &IS, raw_ostream &SS, const APInt &Bits, 305 unsigned &Index) { 306 if (!Bits.getNumWords()) { 307 IS.indent(4) << "{/*NumBits*/0, /*Index*/0},"; 308 return; 309 } 310 311 IS.indent(4) << "{/*NumBits*/" << Bits.getBitWidth() << ", " 312 << "/*Index*/" << Index << "},"; 313 314 SS.indent(4); 315 for (unsigned I = 0; I < Bits.getNumWords(); ++I, ++Index) 316 SS << "UINT64_C(" << utostr(Bits.getRawData()[I]) << "),"; 317 } 318 319 void VarLenCodeEmitterGen::emitInstructionBaseValues( 320 raw_ostream &OS, ArrayRef<const CodeGenInstruction *> NumberedInstructions, 321 CodeGenTarget &Target, int HwMode) { 322 std::string IndexArray, StorageArray; 323 raw_string_ostream IS(IndexArray), SS(StorageArray); 324 325 const CodeGenHwModes &HWM = Target.getHwModes(); 326 if (HwMode == -1) { 327 IS << " static const unsigned Index[][2] = {\n"; 328 SS << " static const uint64_t InstBits[] = {\n"; 329 } else { 330 StringRef Name = HWM.getMode(HwMode).Name; 331 IS << " static const unsigned Index_" << Name << "[][2] = {\n"; 332 SS << " static const uint64_t InstBits_" << Name << "[] = {\n"; 333 } 334 335 unsigned NumFixedValueWords = 0U; 336 for (const CodeGenInstruction *CGI : NumberedInstructions) { 337 Record *R = CGI->TheDef; 338 339 if (R->getValueAsString("Namespace") == "TargetOpcode" || 340 R->getValueAsBit("isPseudo")) { 341 IS.indent(4) << "{/*NumBits*/0, /*Index*/0},\n"; 342 continue; 343 } 344 345 Record *EncodingDef = R; 346 if (const RecordVal *RV = R->getValue("EncodingInfos")) { 347 if (auto *DI = dyn_cast_or_null<DefInit>(RV->getValue())) { 348 EncodingInfoByHwMode EBM(DI->getDef(), HWM); 349 if (EBM.hasMode(HwMode)) 350 EncodingDef = EBM.get(HwMode); 351 } 352 } 353 354 auto It = VarLenInsts.find(EncodingDef); 355 if (It == VarLenInsts.end()) 356 PrintFatalError(EncodingDef, "VarLenInst not found for this record"); 357 const VarLenInst &VLI = It->second; 358 359 unsigned i = 0U, BitWidth = VLI.size(); 360 361 // Start by filling in fixed values. 362 APInt Value(BitWidth, 0); 363 auto SI = VLI.begin(), SE = VLI.end(); 364 // Scan through all the segments that have fixed-bits values. 365 while (i < BitWidth && SI != SE) { 366 unsigned SegmentNumBits = SI->BitWidth; 367 if (const auto *BI = dyn_cast<BitsInit>(SI->Value)) { 368 for (unsigned Idx = 0U; Idx != SegmentNumBits; ++Idx) { 369 auto *B = cast<BitInit>(BI->getBit(Idx)); 370 Value.setBitVal(i + Idx, B->getValue()); 371 } 372 } 373 if (const auto *BI = dyn_cast<BitInit>(SI->Value)) 374 Value.setBitVal(i, BI->getValue()); 375 376 i += SegmentNumBits; 377 ++SI; 378 } 379 380 emitInstBits(IS, SS, Value, NumFixedValueWords); 381 IS << '\t' << "// " << R->getName() << "\n"; 382 if (Value.getNumWords()) 383 SS << '\t' << "// " << R->getName() << "\n"; 384 } 385 IS.indent(4) << "{/*NumBits*/0, /*Index*/0}\n };\n"; 386 SS.indent(4) << "UINT64_C(0)\n };\n"; 387 388 OS << IS.str() << SS.str(); 389 } 390 391 std::string VarLenCodeEmitterGen::getInstructionCase(Record *R, 392 CodeGenTarget &Target) { 393 std::string Case; 394 if (const RecordVal *RV = R->getValue("EncodingInfos")) { 395 if (auto *DI = dyn_cast_or_null<DefInit>(RV->getValue())) { 396 const CodeGenHwModes &HWM = Target.getHwModes(); 397 EncodingInfoByHwMode EBM(DI->getDef(), HWM); 398 Case += " switch (HwMode) {\n"; 399 Case += " default: llvm_unreachable(\"Unhandled HwMode\");\n"; 400 for (auto &KV : EBM) { 401 Case += " case " + itostr(KV.first) + ": {\n"; 402 Case += getInstructionCaseForEncoding(R, KV.second, Target); 403 Case += " break;\n"; 404 Case += " }\n"; 405 } 406 Case += " }\n"; 407 return Case; 408 } 409 } 410 return getInstructionCaseForEncoding(R, R, Target); 411 } 412 413 std::string VarLenCodeEmitterGen::getInstructionCaseForEncoding( 414 Record *R, Record *EncodingDef, CodeGenTarget &Target) { 415 auto It = VarLenInsts.find(EncodingDef); 416 if (It == VarLenInsts.end()) 417 PrintFatalError(EncodingDef, "Parsed encoding record not found"); 418 const VarLenInst &VLI = It->second; 419 size_t BitWidth = VLI.size(); 420 421 CodeGenInstruction &CGI = Target.getInstruction(R); 422 423 std::string Case; 424 raw_string_ostream SS(Case); 425 // Resize the scratch buffer. 426 if (BitWidth && !VLI.isFixedValueOnly()) 427 SS.indent(6) << "Scratch = Scratch.zext(" << BitWidth << ");\n"; 428 // Populate based value. 429 SS.indent(6) << "Inst = getInstBits(opcode);\n"; 430 431 // Process each segment in VLI. 432 size_t Offset = 0U; 433 for (const auto &ES : VLI) { 434 unsigned NumBits = ES.BitWidth; 435 const Init *Val = ES.Value; 436 // If it's a StringInit or DagInit, it's a reference to an operand 437 // or part of an operand. 438 if (isa<StringInit>(Val) || isa<DagInit>(Val)) { 439 StringRef OperandName; 440 unsigned LoBit = 0U; 441 if (const auto *SV = dyn_cast<StringInit>(Val)) { 442 OperandName = SV->getValue(); 443 } else { 444 // Normalized: (slice <operand name>, <high bit>, <low bit>) 445 const auto *DV = cast<DagInit>(Val); 446 OperandName = cast<StringInit>(DV->getArg(0))->getValue(); 447 LoBit = static_cast<unsigned>(cast<IntInit>(DV->getArg(2))->getValue()); 448 } 449 450 auto OpIdx = CGI.Operands.ParseOperandName(OperandName); 451 unsigned FlatOpIdx = CGI.Operands.getFlattenedOperandNumber(OpIdx); 452 StringRef CustomEncoder = CGI.Operands[OpIdx.first].EncoderMethodName; 453 if (ES.CustomEncoder.size()) 454 CustomEncoder = ES.CustomEncoder; 455 456 SS.indent(6) << "Scratch.clearAllBits();\n"; 457 SS.indent(6) << "// op: " << OperandName.drop_front(1) << "\n"; 458 if (CustomEncoder.empty()) 459 SS.indent(6) << "getMachineOpValue(MI, MI.getOperand(" 460 << utostr(FlatOpIdx) << ")"; 461 else 462 SS.indent(6) << CustomEncoder << "(MI, /*OpIdx=*/" << utostr(FlatOpIdx); 463 464 SS << ", /*Pos=*/" << utostr(Offset) << ", Scratch, Fixups, STI);\n"; 465 466 SS.indent(6) << "Inst.insertBits(" 467 << "Scratch.extractBits(" << utostr(NumBits) << ", " 468 << utostr(LoBit) << ")" 469 << ", " << Offset << ");\n"; 470 } 471 Offset += NumBits; 472 } 473 474 StringRef PostEmitter = R->getValueAsString("PostEncoderMethod"); 475 if (!PostEmitter.empty()) 476 SS.indent(6) << "Inst = " << PostEmitter << "(MI, Inst, STI);\n"; 477 478 return Case; 479 } 480 481 namespace llvm { 482 483 void emitVarLenCodeEmitter(RecordKeeper &R, raw_ostream &OS) { 484 VarLenCodeEmitterGen(R).run(OS); 485 } 486 487 } // end namespace llvm 488