521 lines · cpp
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-exception6//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 printf13// works: The (immutable) formatting string represent the fixed values in the14// 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 scheme21// 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 encoding29// fragments on any bit position, bringing more flexibilities on defining30// encoding for variable-length instructions.31//32// In a more specific way, instruction encoding is represented by a DAG type33// `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 LSB41// 1101<encoding for operand src>1001<encoding for operand dst>42// ```43// For more details about DAG operators in the above snippet, please44// refer to \file include/llvm/Target/Target.td.45//46// VarLenCodeEmitter will convert the above DAG into the same helper function47// generated by CodeEmitter, `MCCodeEmitter::getBinaryCodeForInstr` (except48// 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 65using namespace llvm;66 67namespace {68 69class 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 descriptive77 // 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 94public:95 explicit VarLenCodeEmitterGen(const RecordKeeper &R) : Records(R) {}96 97 void run(raw_ostream &OS);98};99} // end anonymous namespace100 101// Get the name of custom encoder or decoder, if there is any.102// Returns `{encoder name, decoder name}`.103static std::pair<StringRef, StringRef>104getCustomCoders(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 else124 Result.second = FuncName;125 }126 return Result;127}128 129VarLenInst::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 136void 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 SmallVector<std::pair<const Init *, const StringInit *>> NewArgs(216 DI->getArgAndNames());217 std::swap(NewArgs[1], NewArgs[2]);218 Segments.push_back({NumBits, DagInit::get(DI->getOperator(), NewArgs),219 CustomEncoder, CustomDecoder});220 } else {221 Segments.push_back({NumBits, DI, CustomEncoder, CustomDecoder});222 }223 }224}225 226void VarLenCodeEmitterGen::run(raw_ostream &OS) {227 CodeGenTarget Target(Records);228 229 auto NumberedInstructions = Target.getInstructions();230 231 for (const CodeGenInstruction *CGI : NumberedInstructions) {232 const Record *R = CGI->TheDef;233 // Create the corresponding VarLenInst instance.234 if (R->getValueAsString("Namespace") == "TargetOpcode" ||235 R->getValueAsBit("isPseudo"))236 continue;237 238 // Setup alternative encodings according to HwModes239 if (const Record *RV = R->getValueAsOptionalDef("EncodingInfos")) {240 const CodeGenHwModes &HWM = Target.getHwModes();241 EncodingInfoByHwMode EBM(RV, HWM);242 for (const auto [Mode, EncodingDef] : EBM) {243 Modes.try_emplace(Mode, "_" + HWM.getMode(Mode).Name.str());244 const RecordVal *RV = EncodingDef->getValue("Inst");245 const DagInit *DI = cast<DagInit>(RV->getValue());246 VarLenInsts[R].try_emplace(Mode, VarLenInst(DI, RV));247 }248 continue;249 }250 const RecordVal *RV = R->getValue("Inst");251 const DagInit *DI = cast<DagInit>(RV->getValue());252 VarLenInsts[R].try_emplace(Universal, VarLenInst(DI, RV));253 }254 255 if (Modes.empty())256 Modes.try_emplace(Universal, ""); // Base case, skip suffix.257 258 // Emit function declaration259 OS << "void " << Target.getName()260 << "MCCodeEmitter::getBinaryCodeForInstr(const MCInst &MI,\n"261 << " SmallVectorImpl<MCFixup> &Fixups,\n"262 << " APInt &Inst,\n"263 << " APInt &Scratch,\n"264 << " const MCSubtargetInfo &STI) const {\n";265 266 // Emit instruction base values267 for (const auto &Mode : Modes)268 emitInstructionBaseValues(OS, NumberedInstructions, Target, Mode.first);269 270 if (Modes.size() > 1) {271 OS << " unsigned Mode = STI.getHwMode();\n";272 }273 274 for (const auto &Mode : Modes) {275 // Emit helper function to retrieve base values.276 OS << " auto getInstBits" << Mode.second277 << " = [&](unsigned Opcode) -> APInt {\n"278 << " unsigned NumBits = Index" << Mode.second << "[Opcode][0];\n"279 << " if (!NumBits)\n"280 << " return APInt::getZeroWidth();\n"281 << " unsigned Idx = Index" << Mode.second << "[Opcode][1];\n"282 << " ArrayRef<uint64_t> Data(&InstBits" << Mode.second << "[Idx], "283 << "APInt::getNumWords(NumBits));\n"284 << " return APInt(NumBits, Data);\n"285 << " };\n";286 }287 288 // Map to accumulate all the cases.289 std::map<std::string, std::vector<std::string>> CaseMap;290 291 // Construct all cases statement for each opcode292 for (const Record *R : Records.getAllDerivedDefinitions("Instruction")) {293 if (R->getValueAsString("Namespace") == "TargetOpcode" ||294 R->getValueAsBit("isPseudo"))295 continue;296 std::string InstName =297 (R->getValueAsString("Namespace") + "::" + R->getName()).str();298 std::string Case = getInstructionCases(R, Target);299 300 CaseMap[Case].push_back(std::move(InstName));301 }302 303 // Emit initial function code304 OS << " const unsigned opcode = MI.getOpcode();\n"305 << " switch (opcode) {\n";306 307 // Emit each case statement308 for (const auto &C : CaseMap) {309 const std::string &Case = C.first;310 const auto &InstList = C.second;311 312 ListSeparator LS("\n");313 for (const auto &InstName : InstList)314 OS << LS << " case " << InstName << ":";315 316 OS << " {\n";317 OS << Case;318 OS << " break;\n"319 << " }\n";320 }321 // Default case: unhandled opcode322 OS << " default:\n"323 << " reportUnsupportedInst(MI);\n"324 << " }\n";325 OS << "}\n\n";326}327 328static void emitInstBits(raw_ostream &IS, raw_ostream &SS, const APInt &Bits,329 unsigned &Index) {330 if (!Bits.getNumWords()) {331 IS.indent(4) << "{/*NumBits*/0, /*Index*/0},";332 return;333 }334 335 IS.indent(4) << "{/*NumBits*/" << Bits.getBitWidth() << ", " << "/*Index*/"336 << Index << "},";337 338 SS.indent(4);339 for (unsigned I = 0; I < Bits.getNumWords(); ++I, ++Index)340 SS << "UINT64_C(" << utostr(Bits.getRawData()[I]) << "),";341}342 343void VarLenCodeEmitterGen::emitInstructionBaseValues(344 raw_ostream &OS, ArrayRef<const CodeGenInstruction *> NumberedInstructions,345 const CodeGenTarget &Target, AltEncodingTy Mode) {346 std::string IndexArray, StorageArray;347 raw_string_ostream IS(IndexArray), SS(StorageArray);348 349 IS << " static const unsigned Index" << Modes[Mode] << "[][2] = {\n";350 SS << " static const uint64_t InstBits" << Modes[Mode] << "[] = {\n";351 352 unsigned NumFixedValueWords = 0U;353 for (const CodeGenInstruction *CGI : NumberedInstructions) {354 const Record *R = CGI->TheDef;355 356 if (R->getValueAsString("Namespace") == "TargetOpcode" ||357 R->getValueAsBit("isPseudo")) {358 IS.indent(4) << "{/*NumBits*/0, /*Index*/0},\n";359 continue;360 }361 362 const auto InstIt = VarLenInsts.find(R);363 if (InstIt == VarLenInsts.end())364 PrintFatalError(R, "VarLenInst not found for this record");365 auto ModeIt = InstIt->second.find(Mode);366 if (ModeIt == InstIt->second.end())367 ModeIt = InstIt->second.find(Universal);368 if (ModeIt == InstIt->second.end()) {369 IS.indent(4) << "{/*NumBits*/0, /*Index*/0},\t" << "// " << R->getName()370 << " no encoding\n";371 continue;372 }373 const VarLenInst &VLI = ModeIt->second;374 unsigned i = 0U, BitWidth = VLI.size();375 376 // Start by filling in fixed values.377 APInt Value(BitWidth, 0);378 auto SI = VLI.begin(), SE = VLI.end();379 // Scan through all the segments that have fixed-bits values.380 while (i < BitWidth && SI != SE) {381 unsigned SegmentNumBits = SI->BitWidth;382 if (const auto *BI = dyn_cast<BitsInit>(SI->Value)) {383 for (unsigned Idx = 0U; Idx != SegmentNumBits; ++Idx) {384 auto *B = cast<BitInit>(BI->getBit(Idx));385 Value.setBitVal(i + Idx, B->getValue());386 }387 }388 if (const auto *BI = dyn_cast<BitInit>(SI->Value))389 Value.setBitVal(i, BI->getValue());390 391 i += SegmentNumBits;392 ++SI;393 }394 395 emitInstBits(IS, SS, Value, NumFixedValueWords);396 IS << '\t' << "// " << R->getName() << "\n";397 if (Value.getNumWords())398 SS << '\t' << "// " << R->getName() << "\n";399 }400 IS.indent(4) << "{/*NumBits*/0, /*Index*/0}\n };\n";401 SS.indent(4) << "UINT64_C(0)\n };\n";402 403 OS << IndexArray << StorageArray;404}405 406std::string407VarLenCodeEmitterGen::getInstructionCases(const Record *R,408 const CodeGenTarget &Target) {409 auto It = VarLenInsts.find(R);410 if (It == VarLenInsts.end())411 PrintFatalError(R, "Parsed encoding record not found");412 const auto &Map = It->second;413 414 // Is this instructions encoding universal (same for all modes)?415 // Allways true if there is only one mode.416 if (Map.size() == 1 && Map.begin()->first == Universal) {417 // Universal, just pick the first mode.418 AltEncodingTy Mode = Modes.begin()->first;419 const auto &Encoding = Map.begin()->second;420 return getInstructionCaseForEncoding(R, Mode, Encoding, Target,421 /*Indent=*/6);422 }423 424 std::string Case;425 Case += " switch (Mode) {\n";426 Case += " default: llvm_unreachable(\"Unhandled Mode\");\n";427 for (const auto &Mode : Modes) {428 Case += " case " + itostr(Mode.first) + ": {\n";429 const auto &It = Map.find(Mode.first);430 if (It == Map.end()) {431 Case +=432 " llvm_unreachable(\"Undefined encoding in this mode\");\n";433 } else {434 Case += getInstructionCaseForEncoding(R, It->first, It->second, Target,435 /*Indent=*/8);436 }437 Case += " break;\n";438 Case += " }\n";439 }440 Case += " }\n";441 return Case;442}443 444std::string VarLenCodeEmitterGen::getInstructionCaseForEncoding(445 const Record *R, AltEncodingTy Mode, const VarLenInst &VLI,446 const CodeGenTarget &Target, int Indent) {447 const CodeGenInstruction &CGI = Target.getInstruction(R);448 449 std::string Case;450 raw_string_ostream SS(Case);451 // Populate based value.452 SS.indent(Indent) << "Inst = getInstBits" << Modes[Mode] << "(opcode);\n";453 454 // Process each segment in VLI.455 size_t Offset = 0U;456 unsigned HighScratchAccess = 0U;457 for (const auto &ES : VLI) {458 unsigned NumBits = ES.BitWidth;459 const Init *Val = ES.Value;460 // If it's a StringInit or DagInit, it's a reference to an operand461 // or part of an operand.462 if (isa<StringInit>(Val) || isa<DagInit>(Val)) {463 StringRef OperandName;464 unsigned LoBit = 0U;465 if (const auto *SV = dyn_cast<StringInit>(Val)) {466 OperandName = SV->getValue();467 } else {468 // Normalized: (slice <operand name>, <high bit>, <low bit>)469 const auto *DV = cast<DagInit>(Val);470 OperandName = cast<StringInit>(DV->getArg(0))->getValue();471 LoBit = static_cast<unsigned>(cast<IntInit>(DV->getArg(2))->getValue());472 }473 474 auto OpIdx = CGI.Operands.parseOperandName(OperandName);475 unsigned FlatOpIdx = CGI.Operands.getFlattenedOperandNumber(OpIdx);476 StringRef CustomEncoder =477 CGI.Operands[OpIdx.first].EncoderMethodNames[OpIdx.second];478 if (ES.CustomEncoder.size())479 CustomEncoder = ES.CustomEncoder;480 481 SS.indent(Indent) << "Scratch.clearAllBits();\n";482 SS.indent(Indent) << "// op: " << OperandName.drop_front(1) << "\n";483 if (CustomEncoder.empty())484 SS.indent(Indent) << "getMachineOpValue(MI, MI.getOperand("485 << utostr(FlatOpIdx) << ")";486 else487 SS.indent(Indent) << CustomEncoder << "(MI, /*OpIdx=*/"488 << utostr(FlatOpIdx);489 490 SS << ", /*Pos=*/" << utostr(Offset) << ", Scratch, Fixups, STI);\n";491 492 SS.indent(Indent) << "Inst.insertBits("493 << "Scratch.extractBits(" << utostr(NumBits) << ", "494 << utostr(LoBit) << ")"495 << ", " << Offset << ");\n";496 497 HighScratchAccess = std::max(HighScratchAccess, NumBits + LoBit);498 }499 Offset += NumBits;500 }501 502 StringRef PostEmitter = R->getValueAsString("PostEncoderMethod");503 if (!PostEmitter.empty())504 SS.indent(Indent) << "Inst = " << PostEmitter << "(MI, Inst, STI);\n";505 506 // Resize the scratch buffer if it's to small.507 std::string ScratchResizeStr;508 if (VLI.size() && !VLI.isFixedValueOnly()) {509 raw_string_ostream RS(ScratchResizeStr);510 RS.indent(Indent) << "if (Scratch.getBitWidth() < " << HighScratchAccess511 << ") { Scratch = Scratch.zext(" << HighScratchAccess512 << "); }\n";513 }514 515 return ScratchResizeStr + Case;516}517 518void llvm::emitVarLenCodeEmitter(const RecordKeeper &R, raw_ostream &OS) {519 VarLenCodeEmitterGen(R).run(OS);520}521