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 #include "llvm/TableGen/Record.h" 62 63 #include <algorithm> 64 65 using namespace llvm; 66 67 namespace { 68 69 class VarLenCodeEmitterGen { 70 const RecordKeeper &Records; 71 72 // Representaton of alternative encodings used for HwModes. 73 using AltEncodingTy = int; 74 // Mode identifier when only one encoding is defined. 75 const AltEncodingTy Universal = -1; 76 // The set of alternative instruction encodings with a descriptive 77 // name suffix to improve readability of the generated code. 78 std::map<AltEncodingTy, std::string> Modes; 79 80 DenseMap<const Record *, DenseMap<AltEncodingTy, VarLenInst>> VarLenInsts; 81 82 // Emit based values (i.e. fixed bits in the encoded instructions) 83 void emitInstructionBaseValues( 84 raw_ostream &OS, 85 ArrayRef<const CodeGenInstruction *> NumberedInstructions, 86 const CodeGenTarget &Target, AltEncodingTy Mode); 87 88 std::string getInstructionCases(const Record *R, const CodeGenTarget &Target); 89 std::string getInstructionCaseForEncoding(const Record *R, AltEncodingTy Mode, 90 const VarLenInst &VLI, 91 const CodeGenTarget &Target, 92 int Indent); 93 94 public: 95 explicit VarLenCodeEmitterGen(const RecordKeeper &R) : Records(R) {} 96 97 void run(raw_ostream &OS); 98 }; 99 } // end anonymous namespace 100 101 // Get the name of custom encoder or decoder, if there is any. 102 // Returns `{encoder name, decoder name}`. 103 static std::pair<StringRef, StringRef> 104 getCustomCoders(ArrayRef<const Init *> Args) { 105 std::pair<StringRef, StringRef> Result; 106 for (const auto *Arg : Args) { 107 const auto *DI = dyn_cast<DagInit>(Arg); 108 if (!DI) 109 continue; 110 const Init *Op = DI->getOperator(); 111 if (!isa<DefInit>(Op)) 112 continue; 113 // syntax: `(<encoder | decoder> "function name")` 114 StringRef OpName = cast<DefInit>(Op)->getDef()->getName(); 115 if (OpName != "encoder" && OpName != "decoder") 116 continue; 117 if (!DI->getNumArgs() || !isa<StringInit>(DI->getArg(0))) 118 PrintFatalError("expected '" + OpName + 119 "' directive to be followed by a custom function name."); 120 StringRef FuncName = cast<StringInit>(DI->getArg(0))->getValue(); 121 if (OpName == "encoder") 122 Result.first = FuncName; 123 else 124 Result.second = FuncName; 125 } 126 return Result; 127 } 128 129 VarLenInst::VarLenInst(const DagInit *DI, const RecordVal *TheDef) 130 : TheDef(TheDef), NumBits(0U), HasDynamicSegment(false) { 131 buildRec(DI); 132 for (const auto &S : Segments) 133 NumBits += S.BitWidth; 134 } 135 136 void VarLenInst::buildRec(const DagInit *DI) { 137 assert(TheDef && "The def record is nullptr ?"); 138 139 std::string Op = DI->getOperator()->getAsString(); 140 141 if (Op == "ascend" || Op == "descend") { 142 bool Reverse = Op == "descend"; 143 int i = Reverse ? DI->getNumArgs() - 1 : 0; 144 int e = Reverse ? -1 : DI->getNumArgs(); 145 int s = Reverse ? -1 : 1; 146 for (; i != e; i += s) { 147 const Init *Arg = DI->getArg(i); 148 if (const auto *BI = dyn_cast<BitsInit>(Arg)) { 149 if (!BI->isComplete()) 150 PrintFatalError(TheDef->getLoc(), 151 "Expecting complete bits init in `" + Op + "`"); 152 Segments.push_back({BI->getNumBits(), BI}); 153 } else if (const auto *BI = dyn_cast<BitInit>(Arg)) { 154 if (!BI->isConcrete()) 155 PrintFatalError(TheDef->getLoc(), 156 "Expecting concrete bit init in `" + Op + "`"); 157 Segments.push_back({1, BI}); 158 } else if (const auto *SubDI = dyn_cast<DagInit>(Arg)) { 159 buildRec(SubDI); 160 } else { 161 PrintFatalError(TheDef->getLoc(), "Unrecognized type of argument in `" + 162 Op + "`: " + Arg->getAsString()); 163 } 164 } 165 } else if (Op == "operand") { 166 // (operand <operand name>, <# of bits>, 167 // [(encoder <custom encoder>)][, (decoder <custom decoder>)]) 168 if (DI->getNumArgs() < 2) 169 PrintFatalError(TheDef->getLoc(), 170 "Expecting at least 2 arguments for `operand`"); 171 HasDynamicSegment = true; 172 const Init *OperandName = DI->getArg(0), *NumBits = DI->getArg(1); 173 if (!isa<StringInit>(OperandName) || !isa<IntInit>(NumBits)) 174 PrintFatalError(TheDef->getLoc(), "Invalid argument types for `operand`"); 175 176 auto NumBitsVal = cast<IntInit>(NumBits)->getValue(); 177 if (NumBitsVal <= 0) 178 PrintFatalError(TheDef->getLoc(), "Invalid number of bits for `operand`"); 179 180 auto [CustomEncoder, CustomDecoder] = 181 getCustomCoders(DI->getArgs().slice(2)); 182 Segments.push_back({static_cast<unsigned>(NumBitsVal), OperandName, 183 CustomEncoder, CustomDecoder}); 184 } else if (Op == "slice") { 185 // (slice <operand name>, <high / low bit>, <low / high bit>, 186 // [(encoder <custom encoder>)][, (decoder <custom decoder>)]) 187 if (DI->getNumArgs() < 3) 188 PrintFatalError(TheDef->getLoc(), 189 "Expecting at least 3 arguments for `slice`"); 190 HasDynamicSegment = true; 191 const Init *OperandName = DI->getArg(0), *HiBit = DI->getArg(1), 192 *LoBit = DI->getArg(2); 193 if (!isa<StringInit>(OperandName) || !isa<IntInit>(HiBit) || 194 !isa<IntInit>(LoBit)) 195 PrintFatalError(TheDef->getLoc(), "Invalid argument types for `slice`"); 196 197 auto HiBitVal = cast<IntInit>(HiBit)->getValue(), 198 LoBitVal = cast<IntInit>(LoBit)->getValue(); 199 if (HiBitVal < 0 || LoBitVal < 0) 200 PrintFatalError(TheDef->getLoc(), "Invalid bit range for `slice`"); 201 bool NeedSwap = false; 202 unsigned NumBits = 0U; 203 if (HiBitVal < LoBitVal) { 204 NeedSwap = true; 205 NumBits = static_cast<unsigned>(LoBitVal - HiBitVal + 1); 206 } else { 207 NumBits = static_cast<unsigned>(HiBitVal - LoBitVal + 1); 208 } 209 210 auto [CustomEncoder, CustomDecoder] = 211 getCustomCoders(DI->getArgs().slice(3)); 212 213 if (NeedSwap) { 214 // Normalization: Hi bit should always be the second argument. 215 const Init *const NewArgs[] = {OperandName, LoBit, HiBit}; 216 Segments.push_back({NumBits, 217 DagInit::get(DI->getOperator(), nullptr, NewArgs, {}), 218 CustomEncoder, CustomDecoder}); 219 } else { 220 Segments.push_back({NumBits, DI, CustomEncoder, CustomDecoder}); 221 } 222 } 223 } 224 225 void VarLenCodeEmitterGen::run(raw_ostream &OS) { 226 CodeGenTarget Target(Records); 227 228 auto NumberedInstructions = Target.getInstructionsByEnumValue(); 229 230 for (const CodeGenInstruction *CGI : NumberedInstructions) { 231 const Record *R = CGI->TheDef; 232 // Create the corresponding VarLenInst instance. 233 if (R->getValueAsString("Namespace") == "TargetOpcode" || 234 R->getValueAsBit("isPseudo")) 235 continue; 236 237 // Setup alternative encodings according to HwModes 238 if (const RecordVal *RV = R->getValue("EncodingInfos")) { 239 if (auto *DI = dyn_cast_or_null<DefInit>(RV->getValue())) { 240 const CodeGenHwModes &HWM = Target.getHwModes(); 241 EncodingInfoByHwMode EBM(DI->getDef(), HWM); 242 for (const auto [Mode, EncodingDef] : EBM) { 243 Modes.insert({Mode, "_" + HWM.getMode(Mode).Name.str()}); 244 const RecordVal *RV = EncodingDef->getValue("Inst"); 245 const DagInit *DI = cast<DagInit>(RV->getValue()); 246 VarLenInsts[R].insert({Mode, VarLenInst(DI, RV)}); 247 } 248 continue; 249 } 250 } 251 const RecordVal *RV = R->getValue("Inst"); 252 const DagInit *DI = cast<DagInit>(RV->getValue()); 253 VarLenInsts[R].insert({Universal, VarLenInst(DI, RV)}); 254 } 255 256 if (Modes.empty()) 257 Modes.insert({Universal, ""}); // Base case, skip suffix. 258 259 // Emit function declaration 260 OS << "void " << Target.getName() 261 << "MCCodeEmitter::getBinaryCodeForInstr(const MCInst &MI,\n" 262 << " SmallVectorImpl<MCFixup> &Fixups,\n" 263 << " APInt &Inst,\n" 264 << " APInt &Scratch,\n" 265 << " const MCSubtargetInfo &STI) const {\n"; 266 267 // Emit instruction base values 268 for (const auto &Mode : Modes) 269 emitInstructionBaseValues(OS, NumberedInstructions, Target, Mode.first); 270 271 if (Modes.size() > 1) { 272 OS << " unsigned Mode = STI.getHwMode();\n"; 273 } 274 275 for (const auto &Mode : Modes) { 276 // Emit helper function to retrieve base values. 277 OS << " auto getInstBits" << Mode.second 278 << " = [&](unsigned Opcode) -> APInt {\n" 279 << " unsigned NumBits = Index" << Mode.second << "[Opcode][0];\n" 280 << " if (!NumBits)\n" 281 << " return APInt::getZeroWidth();\n" 282 << " unsigned Idx = Index" << Mode.second << "[Opcode][1];\n" 283 << " ArrayRef<uint64_t> Data(&InstBits" << Mode.second << "[Idx], " 284 << "APInt::getNumWords(NumBits));\n" 285 << " return APInt(NumBits, Data);\n" 286 << " };\n"; 287 } 288 289 // Map to accumulate all the cases. 290 std::map<std::string, std::vector<std::string>> CaseMap; 291 292 // Construct all cases statement for each opcode 293 for (const Record *R : Records.getAllDerivedDefinitions("Instruction")) { 294 if (R->getValueAsString("Namespace") == "TargetOpcode" || 295 R->getValueAsBit("isPseudo")) 296 continue; 297 std::string InstName = 298 (R->getValueAsString("Namespace") + "::" + R->getName()).str(); 299 std::string Case = getInstructionCases(R, Target); 300 301 CaseMap[Case].push_back(std::move(InstName)); 302 } 303 304 // Emit initial function code 305 OS << " const unsigned opcode = MI.getOpcode();\n" 306 << " switch (opcode) {\n"; 307 308 // Emit each case statement 309 for (const auto &C : CaseMap) { 310 const std::string &Case = C.first; 311 const auto &InstList = C.second; 312 313 ListSeparator LS("\n"); 314 for (const auto &InstName : InstList) 315 OS << LS << " case " << InstName << ":"; 316 317 OS << " {\n"; 318 OS << Case; 319 OS << " break;\n" 320 << " }\n"; 321 } 322 // Default case: unhandled opcode 323 OS << " default:\n" 324 << " std::string msg;\n" 325 << " raw_string_ostream Msg(msg);\n" 326 << " Msg << \"Not supported instr: \" << MI;\n" 327 << " report_fatal_error(Msg.str().c_str());\n" 328 << " }\n"; 329 OS << "}\n\n"; 330 } 331 332 static void emitInstBits(raw_ostream &IS, raw_ostream &SS, const APInt &Bits, 333 unsigned &Index) { 334 if (!Bits.getNumWords()) { 335 IS.indent(4) << "{/*NumBits*/0, /*Index*/0},"; 336 return; 337 } 338 339 IS.indent(4) << "{/*NumBits*/" << Bits.getBitWidth() << ", " << "/*Index*/" 340 << Index << "},"; 341 342 SS.indent(4); 343 for (unsigned I = 0; I < Bits.getNumWords(); ++I, ++Index) 344 SS << "UINT64_C(" << utostr(Bits.getRawData()[I]) << "),"; 345 } 346 347 void VarLenCodeEmitterGen::emitInstructionBaseValues( 348 raw_ostream &OS, ArrayRef<const CodeGenInstruction *> NumberedInstructions, 349 const CodeGenTarget &Target, AltEncodingTy Mode) { 350 std::string IndexArray, StorageArray; 351 raw_string_ostream IS(IndexArray), SS(StorageArray); 352 353 IS << " static const unsigned Index" << Modes[Mode] << "[][2] = {\n"; 354 SS << " static const uint64_t InstBits" << Modes[Mode] << "[] = {\n"; 355 356 unsigned NumFixedValueWords = 0U; 357 for (const CodeGenInstruction *CGI : NumberedInstructions) { 358 const Record *R = CGI->TheDef; 359 360 if (R->getValueAsString("Namespace") == "TargetOpcode" || 361 R->getValueAsBit("isPseudo")) { 362 IS.indent(4) << "{/*NumBits*/0, /*Index*/0},\n"; 363 continue; 364 } 365 366 const auto InstIt = VarLenInsts.find(R); 367 if (InstIt == VarLenInsts.end()) 368 PrintFatalError(R, "VarLenInst not found for this record"); 369 auto ModeIt = InstIt->second.find(Mode); 370 if (ModeIt == InstIt->second.end()) 371 ModeIt = InstIt->second.find(Universal); 372 if (ModeIt == InstIt->second.end()) { 373 IS.indent(4) << "{/*NumBits*/0, /*Index*/0},\t" << "// " << R->getName() 374 << " no encoding\n"; 375 continue; 376 } 377 const VarLenInst &VLI = ModeIt->second; 378 unsigned i = 0U, BitWidth = VLI.size(); 379 380 // Start by filling in fixed values. 381 APInt Value(BitWidth, 0); 382 auto SI = VLI.begin(), SE = VLI.end(); 383 // Scan through all the segments that have fixed-bits values. 384 while (i < BitWidth && SI != SE) { 385 unsigned SegmentNumBits = SI->BitWidth; 386 if (const auto *BI = dyn_cast<BitsInit>(SI->Value)) { 387 for (unsigned Idx = 0U; Idx != SegmentNumBits; ++Idx) { 388 auto *B = cast<BitInit>(BI->getBit(Idx)); 389 Value.setBitVal(i + Idx, B->getValue()); 390 } 391 } 392 if (const auto *BI = dyn_cast<BitInit>(SI->Value)) 393 Value.setBitVal(i, BI->getValue()); 394 395 i += SegmentNumBits; 396 ++SI; 397 } 398 399 emitInstBits(IS, SS, Value, NumFixedValueWords); 400 IS << '\t' << "// " << R->getName() << "\n"; 401 if (Value.getNumWords()) 402 SS << '\t' << "// " << R->getName() << "\n"; 403 } 404 IS.indent(4) << "{/*NumBits*/0, /*Index*/0}\n };\n"; 405 SS.indent(4) << "UINT64_C(0)\n };\n"; 406 407 OS << IndexArray << StorageArray; 408 } 409 410 std::string 411 VarLenCodeEmitterGen::getInstructionCases(const Record *R, 412 const CodeGenTarget &Target) { 413 auto It = VarLenInsts.find(R); 414 if (It == VarLenInsts.end()) 415 PrintFatalError(R, "Parsed encoding record not found"); 416 const auto &Map = It->second; 417 418 // Is this instructions encoding universal (same for all modes)? 419 // Allways true if there is only one mode. 420 if (Map.size() == 1 && Map.begin()->first == Universal) { 421 // Universal, just pick the first mode. 422 AltEncodingTy Mode = Modes.begin()->first; 423 const auto &Encoding = Map.begin()->second; 424 return getInstructionCaseForEncoding(R, Mode, Encoding, Target, 425 /*Indent=*/6); 426 } 427 428 std::string Case; 429 Case += " switch (Mode) {\n"; 430 Case += " default: llvm_unreachable(\"Unhandled Mode\");\n"; 431 for (const auto &Mode : Modes) { 432 Case += " case " + itostr(Mode.first) + ": {\n"; 433 const auto &It = Map.find(Mode.first); 434 if (It == Map.end()) { 435 Case += 436 " llvm_unreachable(\"Undefined encoding in this mode\");\n"; 437 } else { 438 Case += getInstructionCaseForEncoding(R, It->first, It->second, Target, 439 /*Indent=*/8); 440 } 441 Case += " break;\n"; 442 Case += " }\n"; 443 } 444 Case += " }\n"; 445 return Case; 446 } 447 448 std::string VarLenCodeEmitterGen::getInstructionCaseForEncoding( 449 const Record *R, AltEncodingTy Mode, const VarLenInst &VLI, 450 const CodeGenTarget &Target, int Indent) { 451 CodeGenInstruction &CGI = Target.getInstruction(R); 452 453 std::string Case; 454 raw_string_ostream SS(Case); 455 // Populate based value. 456 SS.indent(Indent) << "Inst = getInstBits" << Modes[Mode] << "(opcode);\n"; 457 458 // Process each segment in VLI. 459 size_t Offset = 0U; 460 unsigned HighScratchAccess = 0U; 461 for (const auto &ES : VLI) { 462 unsigned NumBits = ES.BitWidth; 463 const Init *Val = ES.Value; 464 // If it's a StringInit or DagInit, it's a reference to an operand 465 // or part of an operand. 466 if (isa<StringInit>(Val) || isa<DagInit>(Val)) { 467 StringRef OperandName; 468 unsigned LoBit = 0U; 469 if (const auto *SV = dyn_cast<StringInit>(Val)) { 470 OperandName = SV->getValue(); 471 } else { 472 // Normalized: (slice <operand name>, <high bit>, <low bit>) 473 const auto *DV = cast<DagInit>(Val); 474 OperandName = cast<StringInit>(DV->getArg(0))->getValue(); 475 LoBit = static_cast<unsigned>(cast<IntInit>(DV->getArg(2))->getValue()); 476 } 477 478 auto OpIdx = CGI.Operands.ParseOperandName(OperandName); 479 unsigned FlatOpIdx = CGI.Operands.getFlattenedOperandNumber(OpIdx); 480 StringRef CustomEncoder = 481 CGI.Operands[OpIdx.first].EncoderMethodNames[OpIdx.second]; 482 if (ES.CustomEncoder.size()) 483 CustomEncoder = ES.CustomEncoder; 484 485 SS.indent(Indent) << "Scratch.clearAllBits();\n"; 486 SS.indent(Indent) << "// op: " << OperandName.drop_front(1) << "\n"; 487 if (CustomEncoder.empty()) 488 SS.indent(Indent) << "getMachineOpValue(MI, MI.getOperand(" 489 << utostr(FlatOpIdx) << ")"; 490 else 491 SS.indent(Indent) << CustomEncoder << "(MI, /*OpIdx=*/" 492 << utostr(FlatOpIdx); 493 494 SS << ", /*Pos=*/" << utostr(Offset) << ", Scratch, Fixups, STI);\n"; 495 496 SS.indent(Indent) << "Inst.insertBits(" 497 << "Scratch.extractBits(" << utostr(NumBits) << ", " 498 << utostr(LoBit) << ")" 499 << ", " << Offset << ");\n"; 500 501 HighScratchAccess = std::max(HighScratchAccess, NumBits + LoBit); 502 } 503 Offset += NumBits; 504 } 505 506 StringRef PostEmitter = R->getValueAsString("PostEncoderMethod"); 507 if (!PostEmitter.empty()) 508 SS.indent(Indent) << "Inst = " << PostEmitter << "(MI, Inst, STI);\n"; 509 510 // Resize the scratch buffer if it's to small. 511 std::string ScratchResizeStr; 512 if (VLI.size() && !VLI.isFixedValueOnly()) { 513 raw_string_ostream RS(ScratchResizeStr); 514 RS.indent(Indent) << "if (Scratch.getBitWidth() < " << HighScratchAccess 515 << ") { Scratch = Scratch.zext(" << HighScratchAccess 516 << "); }\n"; 517 } 518 519 return ScratchResizeStr + Case; 520 } 521 522 void llvm::emitVarLenCodeEmitter(const RecordKeeper &R, raw_ostream &OS) { 523 VarLenCodeEmitterGen(R).run(OS); 524 } 525