LLVM学习笔记（39）

3.5.2.3. 指令描述数组

首先看到385行的getInstructionsByEnumValue方法，指令的这个遍历次序很重要。接着，我们看到387行的SequenceToOffsetTable类型的变量InstrNames，这意味着我们将要进行差分编码。391行则告诉我们，要进行差分编码的是指令的名字。

InstrInfoEmitter::run（续）

381      // Emit all of the MCInstrDesc records in their ENUM ordering.

382        //

383      OS << "\nextern const MCInstrDesc " << TargetName << "Insts[] = {\n";

384      const std::vector< const CodeGenInstruction*> &NumberedInstructions =

385      Target. getInstructionsByEnumValue ();

386     

387      SequenceToOffsetTable<std::string> InstrNames;

388      unsigned Num = 0;

389      for ( const CodeGenInstruction *Inst : NumberedInstructions) {

390      // Keep a list of the instruction names.

391      InstrNames.(Inst->TheDef->getName());

392      // Emit the record into the table.

393      (*Inst, Num++, InstrInfo, EmittedLists, OperandInfoIDs, OS);

394      }

395      OS << "};\n\n";

注意在393行调用的emitRecord，参数Num是指令的处理序号。记住我们总是以相同的次序遍历指令。参数InstrInfo就是X86InstrInfo（定义在X86.td）的Record对象，不过emitRecord方法并没有用它。参数EmittedLists则是以指令定义中的Uses或Defs的Record对象为键值，给出这些对象输出所在ImplicitList Num 数组的序号（即 Num ）。同样参数OpInfo以输出到OperandInfo Num 数组的字符串为键值，给出该OperandInfo Num 数组的序号。

464      void InstrInfoEmitter::emitRecord ( const CodeGenInstruction &Inst, unsigned Num,

465      Record *InstrInfo,

466      std::map<std::vector<Record*>, unsigned> &EmittedLists,

467      const OperandInfoMapTy &OpInfo,

468      raw_ostream &OS) {

469      int MinOperands = 0;

470      if (!Inst.Operands.empty())

471      // Each logical operand can be multiple MI operands.

472      MinOperands = Inst.Operands.back().MIOperandNo +

473      Inst.Operands.back().MINumOperands;

474     

475      OS << "  { ";

476      OS << Num << ",\t" << MinOperands << ",\t"

477      << Inst.Operands.NumDefs << ",\t"

478      << Inst.TheDef->getValueAsInt("Size") << ",\t"

479      << SchedModels.getSchedClassIdx(Inst) << ",\t0";

480     

481      // Emit all of the target independent flags...

482      if (Inst.isPseudo)           OS << "|(1ULL<<MCID::Pseudo)";

483      if (Inst.isReturn)           OS << "|(1ULL<<MCID::Return)";

484      if (Inst.isBranch)           OS << "|(1ULL<<MCID::Branch)";

485      if (Inst.isIndirectBranch)   OS << "|(1ULL<<MCID::IndirectBranch)";

486      if (Inst.isCompare)          OS << "|(1ULL<<MCID::Compare)";

487      if (Inst.isMoveImm)          OS << "|(1ULL<<MCID::MoveImm)";

488      if (Inst.isBitcast)          OS << "|(1ULL<<MCID::Bitcast)";

489      if (Inst.isSelect)           OS << "|(1ULL<<MCID::Select)";

490      if (Inst.isBarrier)          OS << "|(1ULL<<MCID::Barrier)";

491      if (Inst.hasDelaySlot)       OS << "|(1ULL<<MCID::DelaySlot)";

492      if (Inst.isCall)             OS << "|(1ULL<<MCID::Call)";

493      if (Inst.canFoldAsLoad)      OS << "|(1ULL<<MCID::FoldableAsLoad)";

494      if (Inst.mayLoad)            OS << "|(1ULL<<MCID::MayLoad)";

495      if (Inst.mayStore)           OS << "|(1ULL<<MCID::MayStore)";

496      if (Inst.isPredicable)       OS << "|(1ULL<<MCID::Predicable)";

497      if (Inst.isConvertibleToThreeAddress) OS << "|(1ULL<<MCID::ConvertibleTo3Addr)";

498      if (Inst.isCommutable)       OS << "|(1ULL<<MCID::Commutable)";

499      if (Inst.isTerminator)       OS << "|(1ULL<<MCID::Terminator)";

500      if (Inst.isReMaterializable) OS << "|(1ULL<<MCID::Rematerializable)";

501      if (Inst.isNotDuplicable)    OS << "|(1ULL<<MCID::NotDuplicable)";

502      if (Inst.Operands.hasOptionalDef) OS << "|(1ULL<<MCID::HasOptionalDef)";

503      if (Inst.usesCustomInserter) OS << "|(1ULL<<MCID::UsesCustomInserter)";

504      if (Inst.hasPostISelHook)    OS << "|(1ULL<<MCID::HasPostISelHook)";

505      if (Inst.Operands.isVariadic)OS << "|(1ULL<<MCID::Variadic)";

506      if (Inst.hasSideEffects)     OS << "|(1ULL<<MCID::UnmodeledSideEffects)";

507      if (Inst.isAsCheapAsAMove)   OS << "|(1ULL<<MCID::CheapAsAMove)";

508      if (Inst.hasExtraSrcRegAllocReq) OS << "|(1ULL<<MCID::ExtraSrcRegAllocReq)";

509      if (Inst.hasExtraDefRegAllocReq) OS << "|(1ULL<<MCID::ExtraDefRegAllocReq)";

510      if (Inst.isRegSequence) OS << "|(1ULL<<MCID::RegSequence)";

511      if (Inst.isExtractSubreg) OS << "|(1ULL<<MCID::ExtractSubreg)";

512      if (Inst.isInsertSubreg) OS << "|(1ULL<<MCID::InsertSubreg)";

513      if (Inst.isConvergent) OS << "|(1ULL<<MCID::Convergent)";

514     

515      // Emit all of the target-specific flags...

516      BitsInit *TSF = Inst.TheDef->getValueAsBitsInit("TSFlags");

517      if (!TSF)

518      PrintFatalError("no TSFlags?");

519      uint64_t Value = 0;

520      for (unsigned i = 0, e = TSF->getNumBits(); i != e; ++i) {

521      if (BitInit *Bit = dyn_cast<BitInit>(TSF->getBit(i)))

522      Value |= uint64_t(Bit->getValue()) << i;

523      else

524      PrintFatalError("Invalid TSFlags bit in " + Inst.TheDef->getName());

525      }

526      OS << ", 0x";

527      OS.write_hex(Value);

528      OS << "ULL, ";

529     

530      // Emit the implicit uses and defs lists...

531      std::vector<Record*> UseList = Inst.TheDef->getValueAsListOfDefs("Uses");

532      if (UseList.empty())

533      OS << "nullptr, ";

534      else

535      OS << "ImplicitList" << EmittedLists[UseList] << ", ";

536     

537      std::vector<Record*> DefList = Inst.TheDef->getValueAsListOfDefs("Defs");

538      if (DefList.empty())

539      OS << "nullptr, ";

540      else

541      OS << "ImplicitList" << EmittedLists[DefList] << ", ";

542     

543      // Emit the operand info.

544      std::vector<std::string> OperandInfo =(Inst);

545      if (OperandInfo.empty())

546      OS << "nullptr";

547      else

548      OS << "OperandInfo" << OpInfo.find(OperandInfo)->second;

549     

550      CodeGenTarget &Target = CDP.getTargetInfo();

551      if (Inst.HasComplexDeprecationPredicate)

552      // Emit a function pointer to the complex predicate method.

553      OS << ", -1 "

554      << ",&get" << Inst.DeprecatedReason << "DeprecationInfo";

555      else if (!Inst.DeprecatedReason.empty())

556      // Emit the Subtarget feature.

557      OS << ", " << Target.getInstNamespace() << "::" << Inst.DeprecatedReason

558      << " ,nullptr";

559      else

560          // Instruction isn't deprecated.

561      OS << ", -1 ,nullptr";

562     

563      OS << " },  // Inst #" << Num << " = " << Inst.TheDef->getName() << "\n";

564      }

emitRecord要输出的是一个元素类型为MCInstrDesc的数组。显然，MCInstrDesc是MC用于描述指令的类型，它有如下的数据成员：

138      class MCInstrDesc {

139      public :

140      unsigned short Opcode;        // The opcode number

141      unsigned short NumOperands;   // Num of args (may be more if variable_ops)

142      unsigned char NumDefs;        // Num of args that are definitions

143      unsigned char Size;           // Number of bytes in encoding.

144      unsigned short SchedClass;    // enum identifying instr sched class

145      uint64_t Flags;               // Flags identifying machine instr class

146      uint64_t TSFlags;             // Target Specific Flag values

147      const uint16_t *ImplicitUses; // Registers implicitly read by this instr

148      const uint16_t *ImplicitDefs; // Registers implicitly defined by this instr

149      const *OpInfo;  // 'NumOperands' entries about operands

150        // Subtarget feature that this is deprecated on, if any

151        // -1 implies this is not deprecated by any single feature. It may still be

152        // deprecated due to a "complex" reason, below.

153      int64_t DeprecatedFeature;

在emitRecord的输出里，140行的Opcode是该MCInstrDesc实例在输出数组中的索引号。143行的Size则是该指令的编码大小。144行的SchedClass实际上是指令的调度类型在CodeGenSchedModels的SchedClasses容器里的序号（getSchedClassIdx方法通过InstrClassMap来确定指令的调度类型，这些调度类型都是第一部分类型）。147~149行的ImplicitUses，ImplicitDefs，OpInfo分别在535，541及548行由EmittedLists及OpInfo负责填充。为了使用OpInfo，在544行调用了GetOperandInfo以获取作为键值的字符串。输出的内容的例子：

extern const MCInstrDesc X86Insts[] = {

…

{ 31, 6, 1, 0, 0, 0|(1ULL<<MCID::MayLoad), 0x0ULL, nullptr, nullptr, OperandInfo15, -1 ,nullptr }, // Inst #31 = ACQUIRE_MOV16rm

{ 32, 6, 1, 0, 0, 0|(1ULL<<MCID::MayLoad), 0x0ULL, nullptr, nullptr, OperandInfo16, -1 ,nullptr }, // Inst #32 = ACQUIRE_MOV32rm

{ 33, 6, 1, 0, 0, 0|(1ULL<<MCID::MayLoad), 0x0ULL, nullptr, nullptr, OperandInfo17, -1 ,nullptr }, // Inst #33 = ACQUIRE_MOV64rm

…

{ 12100, 0, 0, 0, 0, 0|(1ULL<<MCID::UnmodeledSideEffects), 0x80004036ULL, nullptr, ImplicitList3, nullptr, -1 ,nullptr }, // Inst #12100 = XTEST

};

注意这个数组与前面在X86名字空间里输出的匿名枚举常量是一一对应的，因为它们以相同的次序遍历指令集。因此140行Opcode的值实际上就是这些匿名枚举常量。

​​​​​​​3.5.2.4. 指令名差分表

指令名字里存在大量重复的片段，因此使用差分表可以起到不错的压缩率。下面398~411行输出名为X86InstrNameData的差分表及X86InstrNameIndices的差分索引表。

InstrInfoEmitter::run（续）

397      // Emit the array of instruction names.

398      InstrNames.();

399      OS << "extern const char " << TargetName << "InstrNameData[] = {\n";

400      InstrNames.(OS, printChar);

401      OS << "};\n\n";

402     

403      OS << "extern const unsigned " << TargetName <<"InstrNameIndices[] = {";

404      Num = 0;

405      for ( const CodeGenInstruction *Inst : NumberedInstructions) {

406      // Newline every eight entries.

407      if (Num % 8 == 0)

408      OS << "\n    ";

409      OS << InstrNames.(Inst->TheDef->getName()) << "U, ";

410      ++Num;

411      }

412     

413      OS << "\n};\n\n";

414     

415      // MCInstrInfo initialization routine.

416      OS << "static inline void Init" << TargetName

417      << "MCInstrInfo(MCInstrInfo *II) {\n";

418      OS << "  II->InitMCInstrInfo(" << TargetName << "Insts, "

419      << TargetName << "InstrNameIndices, " << TargetName << "InstrNameData, "

420      << NumberedInstructions.size() << ");\n}\n\n";

421     

422      OS << "} // End llvm namespace \n";

423     

424      OS << "#endif // GET_INSTRINFO_MC_DESC\n\n";

425     

426      // Create a TargetInstrInfo subclass to hide the MC layer initialization.

427      OS << "\n#ifdef GET_INSTRINFO_HEADER\n";

428      OS << "#undef GET_INSTRINFO_HEADER\n";

429     

430      std::string ClassName = TargetName + "GenInstrInfo";

431      OS << "namespace llvm {\n";

432      OS << "struct " << ClassName << " : public TargetInstrInfo {\n"

433      << "  explicit " << ClassName

434      << "(int CFSetupOpcode = -1, int CFDestroyOpcode = -1);\n"

435      << "  virtual ~" << ClassName << "();\n"

436      << "};\n";

437      OS << "} // End llvm namespace \n";

438     

439      OS << "#endif // GET_INSTRINFO_HEADER\n\n";

440     

441      OS << "\n#ifdef GET_INSTRINFO_CTOR_DTOR\n";

442      OS << "#undef GET_INSTRINFO_CTOR_DTOR\n";

443     

444      OS << "namespace llvm {\n";

445      OS << "extern const MCInstrDesc " << TargetName << "Insts[];\n";

446      OS << "extern const unsigned " << TargetName << "InstrNameIndices[];\n";

447      OS << "extern const char " << TargetName << "InstrNameData[];\n";

448      OS << ClassName << "::" << ClassName

449      << "(int CFSetupOpcode, int CFDestroyOpcode)\n"

450      << "  : TargetInstrInfo(CFSetupOpcode, CFDestroyOpcode) {\n"

451      << "  InitMCInstrInfo(" << TargetName << "Insts, " << TargetName

452      << "InstrNameIndices, " << TargetName << "InstrNameData, "

453      << NumberedInstructions.size() << ");\n}\n"

454      << ClassName << "::~" << ClassName << "() {}\n";

455      OS << "} // End llvm namespace \n";

456     

457      OS << "#endif // GET_INSTRINFO_CTOR_DTOR\n\n";

458     

459      emitOperandNameMappings (OS, Target, NumberedInstructions);

460     

461      (OS, Target);

462      }

416~422行输出下面的方法：

static inline void InitX86MCInstrInfo (MCInstrInfo *II) {

II->InitMCInstrInfo(X86Insts, X86InstrNameIndices, X86InstrNameData, 12101);

}

MCInstrInfo::InitMCInstrInfo方法是一个很简单的方法，却是LLVM通用处理框架与目标机器之间的一个重要接口。MCInstrInfo定义如下：

24        class MCInstrInfo {

25        const MCInstrDesc *Desc;          // Raw array to allow static init'n

26        const unsigned *InstrNameIndices; // Array for name indices in InstrNameData

27        const char *InstrNameData;        // Instruction name string pool

28        unsigned NumOpcodes;              // Number of entries in the desc array

29       

30        public :

31          /// \brief Initialize MCInstrInfo, called by TableGen auto-generated routines.

32          /// *DO NOT USE*.

33        void InitMCInstrInfo( const *D, const unsigned *NI, const char *ND,

34        unsigned NO) {

35        Desc = D;

36        InstrNameIndices = NI;

37        InstrNameData = ND;

38        NumOpcodes = NO;

39        }

40       

41        unsigned getNumOpcodes() const { return NumOpcodes; }

42       

43        /// \brief Return the machine instruction descriptor that corresponds to the

44          /// specified instruction opcode.

45        const MCInstrDesc &get(unsigned Opcode) const {

46        assert (Opcode < NumOpcodes && "Invalid opcode!");

47        return Desc[Opcode];

48        }

49       

50        /// \brief Returns the name for the instructions with the given opcode.

51        const char *getName(unsigned Opcode) const {

52        assert (Opcode < NumOpcodes && "Invalid opcode!");

53        return &InstrNameData[InstrNameIndices[Opcode]];

54        }

55        };

427~457行输出目标机器特定的TargetInstrInfo派生类。

#ifdef GET_INSTRINFO_HEADER

#undef GET_INSTRINFO_HEADER

namespace llvm {

struct X86GenInstrInfo : public TargetInstrInfo {

explicit X86GenInstrInfo(int CFSetupOpcode = -1, int CFDestroyOpcode = -1);

virtual ~X86GenInstrInfo();

};

} // End llvm namespace

#endif // GET_INSTRINFO_HEADER

#ifdef GET_INSTRINFO_CTOR_DTOR

#undef GET_INSTRINFO_CTOR_DTOR

namespace llvm {

extern const MCInstrDesc X86Insts[];

extern const unsigned X86InstrNameIndices[];

extern const char X86InstrNameData[];

X86GenInstrInfo::X86GenInstrInfo (int CFSetupOpcode, int CFDestroyOpcode)

: TargetInstrInfo(CFSetupOpcode, CFDestroyOpcode) {

InitMCInstrInfo(X86Insts, X86InstrNameIndices, X86InstrNameData, 12101);

}

X86GenInstrInfo::~X86GenInstrInfo() {}

} // End llvm namespace

#endif // GET_INSTRINFO_CTOR_DTOR

​​​​​​​3.5.3.5. getNamedOperandIdx方法与操作数类型

在459行调用的emitOperandNameMappings来为某些特别的目标机器（X86不在内）实现一个带有优化性质的方法getNamedOperandIdx。

236      void InstrInfoEmitter::emitOperandNameMappings (raw_ostream &OS,

237      const CodeGenTarget &Target,

238      const std::vector< const CodeGenInstruction*> &NumberedInstructions) {

239     

240      const std::string &Namespace = Target.getInstNamespace();

241      std::string OpNameNS = "OpName";

242      // Map of operand names to their enumeration value.  This will be used to

243        // generate the OpName enum.

244      std::map<std::string, unsigned> Operands;

245      OpNameMapTy OperandMap;

246     

247      (NumberedInstructions, Namespace, Operands, OperandMap);

248     

249      OS << "#ifdef GET_INSTRINFO_OPERAND_ENUM\n";

250      OS << "#undef GET_INSTRINFO_OPERAND_ENUM\n";

251      OS << "namespace llvm {\n";

252      OS << "namespace " << Namespace << " {\n";

253      OS << "namespace " << OpNameNS << " { \n";

254      OS << "enum {\n";

255      for ( const auto &Op : Operands)

256      OS << "  " << Op.first << " = " << Op.second << ",\n";

257     

258      OS << "OPERAND_LAST";

259      OS << "\n};\n";

260      OS << "} // End namespace OpName\n";

261      OS << "} // End namespace " << Namespace << "\n";

262      OS << "} // End namespace llvm\n";

263      OS << "#endif //GET_INSTRINFO_OPERAND_ENUM\n";

264     

265      OS << "#ifdef GET_INSTRINFO_NAMED_OPS\n";

266      OS << "#undef GET_INSTRINFO_NAMED_OPS\n";

267      OS << "namespace llvm {\n";

268      OS << "namespace " << Namespace << " {\n";

269      OS << "LLVM_READONLY\n";

270      OS << "int16_t getNamedOperandIdx(uint16_t Opcode, uint16_t NamedIdx) {\n";

271      if (!Operands.empty()) {

272      OS << "  static const int16_t OperandMap [][" << Operands.size()

273      << "] = {\n";

274      for ( const auto &Entry : OperandMap) {

275      const std::map<unsigned, unsigned> &OpList = Entry.first;

276      OS << "{";

277     

278      // Emit a row of the OperandMap table

279      for (unsigned i = 0, e = Operands.size(); i != e; ++i)

280      OS << (OpList.count(i) == 0 ? -1 : (int)OpList.find(i)->second) << ", ";

281     

282      OS << "},\n";

283      }

284      OS << "};\n";

285     

286      OS << "  switch(Opcode) {\n";

287      unsigned TableIndex = 0;

288      for ( const auto &Entry : OperandMap) {

289      for ( const std::string &Name : Entry.second)

290      OS << "  case " << Name << ":\n";

291     

292      OS << "    return OperandMap[" << TableIndex++ << "][NamedIdx];\n";

293      }

294      OS << "    default: return -1;\n";

295      OS << "  }\n";

296      } else {

297      // There are no operands, so no need to emit anything

298      OS << "  return -1;\n";

299      }

300      OS << "}\n";

301      OS << "} // End namespace " << Namespace << "\n";

302      OS << "} // End namespace llvm\n";

303      OS << "#endif //GET_INSTRINFO_NAMED_OPS\n";

304     

305      }

类似的，如果存在相当数量的指令操作数，而且相当数量的指令使用同一组操作数，TableGen提供了一个优化的方式。通过将指令定义的UseNamedOperandTable设置为1，TableGen将生成名为getNamedOperandIdx的方法，可以基于一个操作数的名字（实际上是一个枚举常量），查找在一条指令（MachineInstr）里该操作数的索引。目前只有ADMGPU使用了这个功能。

201      void InstrInfoEmitter::initOperandMapData (

202      const std::vector< const CodeGenInstruction *> &NumberedInstructions,

203      const std::string &Namespace,

204      std::map<std::string, unsigned> &Operands,

205      OpNameMapTy &OperandMap) {

206     

207      unsigned NumOperands = 0;

208      for ( const CodeGenInstruction *Inst : NumberedInstructions) {

209      if (!Inst->TheDef->getValueAsBit("UseNamedOperandTable"))

210      continue ;

211      std::map<unsigned, unsigned> OpList;

212      for ( const auto &Info : Inst->Operands) {

213      StrUintMapIter I = Operands.find(Info.Name);

214     

215      if (I == Operands.end()) {

216      I = Operands.insert(Operands.begin(),

217      std::pair<std::string, unsigned>(Info.Name, NumOperands++));

218      }

219      OpList[I->second] = Info.MIOperandNo;

220      }

221      OperandMap[OpList].push_back(Namespace + "::" + Inst->TheDef->getName());

222      }

223      }

这个机制最重要的数据结构是一个[Instruction定义中UseNamedOperandTable域为1的指令数]✕[所涉及操作数个数]数组。以指令Opcode作为第一维索引，该指令操作数的相关枚举常量作为第二维，对应项给出该操作数在这个指令里的索引号。

initOperandMapData方法就是准备这个数组的内容。而emitOperandNameMappings就是根据initOperandMapData准备的数据生成getNamedOperandIdx方法以实现上述的查表。

在InstrInfoEmitter::run的最后，调用下面的方法输出代表目标机器所有指令操作数类型的枚举常量。这些枚举常量实际上是.td文件里目标机器Operand派生定义按名字 排序 的次序。另外，匿名指令操作数不在考虑之列。

310      void InstrInfoEmitter::emitOperandTypesEnum (raw_ostream &OS,

311      const CodeGenTarget &Target) {

312     

313      const std::string &Namespace = Target.getInstNamespace();

314      std::vector<Record *> Operands = Records.getAllDerivedDefinitions("Operand");

315     

316      OS << "\n#ifdef GET_INSTRINFO_OPERAND_TYPES_ENUM\n";

317      OS << "#undef GET_INSTRINFO_OPERAND_TYPES_ENUM\n";

318      OS << "namespace llvm {\n";

319      OS << "namespace " << Namespace << " {\n";

320      OS << "namespace OpTypes { \n";

321      OS << "enum OperandType {\n";

322     

323      unsigned EnumVal = 0;

324      for ( const Record *Op : Operands) {

325      if (!Op->isAnonymous())

326      OS << "  " << Op->getName() << " = " << EnumVal << ",\n";

327      ++EnumVal;

328      }

329     

330      OS << "  OPERAND_TYPE_LIST_END" << "\n};\n";

331      OS << "} // End namespace OpTypes\n";

332      OS << "} // End namespace " << Namespace << "\n";

333      OS << "} // End namespace llvm\n";

334      OS << "#endif // GET_INSTRINFO_OPERAND_TYPES_ENUM\n";

335      }

对X86目标机器而言，这些操作数类型定义都在X86InstrInfo.td文件里，一共有79个，没有匿名定义。

#ifdef GET_INSTRINFO_OPERAND_TYPES_ENUM

#undef GET_INSTRINFO_OPERAND_TYPES_ENUM

namespace llvm {

namespace X86 {

namespace OpTypes {

enum OperandType {

AVX512ICC = 0,

AVX512RC = 1,

AVXCC = 2,

…

vz64mem = 79,

OPERAND_TYPE_LIST_END

};

} // End namespace OpTypes

} // End namespace X86

} // End namespace llvm

#endif // GET_INSTRINFO_OPERAND_TYPES_ENUM

至此，对X86GenInstrInfo.inc的输出完成。不过，我们并没有看到有关调度器输出。这是因为LLVM是一个“很有规矩的”项目，X86GenInstrInfo.inc只能给出关于X86指令的数据。调度器数据必须输出到X86GenSubtargetInfo.inc文件，这是下一节的目标。