<div dir="ltr">Hi all,<br><br>The goal of this RFC is to make information related to variant scheduling<br>classes accessible at MC level. This would help tools like llvm-mca<br>understand/resolve variant scheduling classes.<br><br>To achieve this goal, I plan to introduce a new class of scheduling predicates<br>named MCSchedPredicate. An MCSchedPredicate allows the definition of boolean<br>expressions with a well-known semantic, that can be used to generate code for<br>both MachineInstr and MCInst.<br><br>The new predicates are designed to be completely optional. Scheduling models<br>can use a combination of SchedPredicate and MCSchedPredicate to describe<br>variant reads and writes. Old scheduling predicate definitions would still be<br>valid. New MCSchedPredicates would behave like normal scheduling predicates.<br><br>A bit of background<br>-------------------<br><br>Variant scheduling classes model situations where the instruction profile<br>depends on the value of certain operands.<br><br>For example, modern x86 processors know that a register-register XOR is a<br>zero-idiom if both operands are the same register. That means, the XOR would<br>be optimized out at register renaming stage, and no opcode issued to the<br>pipelines. A variant scheduling class can be used to describe this case (see<br>example below):<br><br>```<br>def ZeroIdiomWrite : SchedWriteRes<[]> { let Latency = 0; }<br><br>def ZeroIdiom : SchedPredicate<[{<br>    MI->getOpcode() == X86::XORrr &&<br>    MI->getOperand(0).getReg() == MI->getOperand(1).getReg()<br>}]>;<br><br>def WriteXOR : SchedWriteVariant<[<br>   SchedVar<ZeroIdiom,   [ZeroIdiomWrite],<br>   SchedVar<NoSchedPred, [WriteALU]<br>>;<br>```<br><br>Problems with the current design<br>--------------------------------<br><br>A SchedPredicate is essentially a custom block of C++ code used by the<br>SubtargetEmitter to generate a condition through a boolean expression.<br>A SchedPredicate sees all the definitions that are "captured" by the<br>`PredicateProlog` (another block of C++ code). It can also access public<br>members of TargetSchedule.<br><br>A common pattern used by the ARM scheduling models to define predicates is:<br> - PredicateProlog "captures" the TargetInstrInfo object from the<br>   TargetSchedule object.<br> - Each predicate uses the "captured" TargetInstrInfo object (TII) to call<br>   helpers exposed by the (target specific) InstrInfo interface.<br><br>Note that TargetSchedule and TargetInstrInfo are both CodeGen concepts.<br><br>SchedPredicate definitions only work on MachineInstr objects. Therefore, the<br>C++ code block is not portable (i.e. it doesn't work if the input instruction<br>is a MCInst).  The `MI` used by the ZeroIdiom definition from the previous<br>example is a MachineInstr *.<br><br>The main problem with this design is that predicates don't have a "portable"<br>semantic.  A predicate is essentially an opaque block of code, and the<br>semantic of predicates is unknown to tablegen. Tablegen can only trust the<br>user, and just "copy-paste" code blocks from the various predicates to an<br>auto-generated `XXXGenSubtargetInfo::resolveSchedClass()` function.<br><br>This limits our ability to reason on predicates. In particular, it makes it<br>extremely hard (if not impossible) for tools that can only access the MC layer<br>to reuse predicate definitions to resolve variant scheduling classes.<br><br>If instead we expose the semantic of predicates to tablegen, we can then teach<br>tablegen how to generate an equivalent code-block that works on MCInst.<br><br>In the next section I show how I plan to expose the semantic of scheduling<br>predicates to tablegen. I will then go through a couple of examples describing<br>how the new predicate syntax can be used, and finally I will describe the<br>patches required to implement this feature.<br><br>A new class of scheduling predicates<br>------------------------------------<br><br>MCSchedPredicate allows the definition of scheduling predicates that have a<br>well-defined portable semantic. They can be used in place of SchedPredicate to<br>define SchedReadVariant and SchedWriteVariant definitions in tablegen.<br><br>An MCSchedPredicate definition is built on top of an MCPredicate. MCPredicate<br>definitions can be composed together to form complex boolean expressions.<br><br>To better understand how these new predicates work, let's have a look at the<br>following example.<br><br>```<br>def M3BranchLinkFastPred  : SchedPredicate<[{MI->getOpcode() == AArch64::BLR &&<br>                                             MI->getOperand(0).isReg() &&<br>                                             MI->getOperand(0).getReg() !=<br>                                             AArch64::LR}]>;<br>```<br><br>This tablegen code snippet has been taken from AArch64/AArch64SchedExynosM3.td<br><br>Predicate `M3BranchLinkFastPred` can be rewritten using an MCSchedPredicate<br>definition as follows:<br><br>```<br>def M3BranchLinkFastPred  : MCSchedPredicate<<br>  CheckAllOf<[<br>    CheckOpcode<[BLR]>,<br>    CheckRegOperand<0>,<br>    CheckNot<CheckRegOperandValue<0, LR>>]><br>  >;<br>```<br><br>The MCSchedPredicate uses a `CheckAllOf`, which is a "composition of<br>predicates", and returns true only if every predicate in the composition<br>returns true. Note that `CheckAllOf`, `CheckOpcode`, `CheckRegOperand` and<br>`CheckNot` are all MCPredicate classes.<br><br>Each predicate class has a well known semantic. For example, `CheckOpcode` is<br>only used to check if the opcode of an instruction is part of a set of opcodes.<br>In this example, CheckOpcode is used to check if the instruction is a BLR.<br><br>This new syntax allows the definition of predicates in a declarative way.<br>These new predicates don't require custom blocks of C++, and can be used to<br>define conditions without being bound to a particular representation (i.e.<br>MachineInstr vs MCInst).<br><br>It also means that tablegen backends are now able to parse and understand the<br>logic of each predicate check. But more importantly, tablegen backends gained<br>the ability to "lower" scheduling predicates into code that work on MCInst too.<br><br>A more complicated example involving TII method calls.<br>------------------------------------------------------<br><br>This code is taken from the AArch64 Cyclone scheduling model:<br><br>```<br>def WriteZPred : SchedPredicate<[{TII->isGPRZero(*MI)}]>;<br>def WriteImmZ  : SchedWriteVariant<[<br>                   SchedVar<WriteZPred, [WriteX]>,<br>                   SchedVar<NoSchedPred, [WriteImm]>]>;<br>```<br><br>Predicate WriteZPred is used to check if a GPR instruction is a zero-idiom.<br>The rationale is that zero-idioms have zero latency and don't consume<br>processor resources.<br><br>The predicate logic is defined by method `isGPRZero()`, which is accessible<br>through the TII object (i.e. a `const AArch64InstrInfo *`).<br><br>Below is the definition of `isGPRZero` in AArch64/AArch64InstrInfo.cpp:<br><br>```<br>// Return true if this instruction simply sets its single destination register<br>// to zero. This is equivalent to a register rename of the zero-register.<br>bool AArch64InstrInfo::isGPRZero(const MachineInstr &MI) {<br>  switch (MI.getOpcode()) {<br>  default:<br>    break;<br>  case AArch64::MOVZWi:<br>  case AArch64::MOVZXi: // movz Rd, #0 (LSL #0)<br>    if (MI.getOperand(1).isImm() && MI.getOperand(1).getImm() == 0) {<br>      assert(MI.getDesc().getNumOperands() == 3 &&<br>             MI.getOperand(2).getImm() == 0 && "invalid MOVZi operands");<br>      return true;<br>    }<br>    break;<br>  case AArch64::ANDWri: // and Rd, Rzr, #imm<br>    return MI.getOperand(1).getReg() == AArch64::WZR;<br>  case AArch64::ANDXri:<br>    return MI.getOperand(1).getReg() == AArch64::XZR;<br>  case TargetOpcode::COPY:<br>    return MI.getOperand(1).getReg() == AArch64::WZR;<br>  }<br>  return false;<br>}<br>```<br><br>That logic can be replaced by the following MCPredicate definitions:<br><br>```<br>def CheckMOVZ : CheckAllOf<[<br>  CheckOpcode<[MOVZWi, MOVZXi]>,<br>  CheckNumOperands<3>,<br>  CheckImmOperand<1>,<br>  CheckZeroOperand<1>,<br>  CheckImmOperand<2>,<br>  CheckZeroOperand<2><br>]>;<br><br>def CheckANDW : CheckAllOf<[<br>  CheckOpcode<[ANDWri]>,<br>  CheckRegOperand<1>,<br>  CheckRegOperandValue<1, WZR><br>]>;<br><br>def CheckANDX : CheckAllOf<[<br>  CheckOpcode<[ANDXri]>,<br>  CheckRegOperand<1>,<br>  CheckRegOperandValue<1, XZR><br>]>;<br><br>def CheckCOPY : CheckAllOf<[<br>  CheckPseudo<[COPY]>,<br>  CheckRegOperand<1>,<br>  CheckRegOperandValue<1, WZR><br>]>;<br><br>// Return true if this instruction simply sets its single destination register<br>// to zero. This is equivalent to a register rename of the zero-register.<br><br>def IsGPRZero : TIIPredicate<"AArch64", "isGPRZero",<br>  AnyOfMCPredicates<[CheckMOVZ, CheckANDW, CheckANDX, CheckCOPY]>>;<br>```<br><br>TIIPredicate definitions are used to model calls to the target-specific<br>InstrInfo.<br><br>A TIIPredicate definition is treated specially by the InstrInfoEmitter<br>tablegen backend, which will use it to automatically generate a definition<br>in the target specific `GenInstrInfo` class.<br><br>Basically, we can tell tablegen to generate that definition for us.<br><br>Now that the description of IsGPRZero is available in the form of a<br>MCPredicate, we can modify the original SchedWriteVariant WriteImmZ as follows:<br><br>```<br>def WriteZPred : MCSchedPredicate<IsGPRZero>;<br><br>def WriteImmZ : SchedWriteVariant<[<br>                  SchedVar<WriteZPred, [WriteX]>,<br>                  SchedVar<SchedDefault, [WriteImm]>]>;<br>```<br><br>How to resolve scheduling classes from MC<br>-----------------------------------------<br><br>MCSubtargetInfo will gain a new method:<br><br>```<br>  /// Resolve a variant scheduling class for the given MCInst and CPU.<br>  virtual unsigned<br>  resolveVariantSchedClass(unsigned SchedClass, const MCInst *MI,<br>                           unsigned CPUID) const {<br>    return 0;<br>  }<br>```<br><br>The SubtargetEmitter is resonsible for processing scheduling classes and<br>generate an override for that method.<br><br>This is what the SubtargetEmitter generates for the Cyclone and Exynos3M if we<br>implement the changes described by the previous sections:<br><br>```<br>unsigned resolveVariantSchedClass(unsigned SchedClass,<br>    const MCInst *MI, unsigned CPUID) const override {<br>  switch (SchedClass) {<br>  case 117: // BLR<br>    if (CPUID == 5) { // ExynosM3Model<br>      if ((<br>          ( MI->getOpcode() == AArch64::BLR )<br>          && MI->getOperand(0).isReg()<br>          && MI->getOperand(0).getReg() != AArch64::LR<br>        ))<br>        return 934; // M3WriteAB<br>      if (true)<br>        return 935; // M3WriteAC<br>    }<br>    break;<br>  case 386: // MOVZWi_MOVZXi<br>    if (CPUID == 3) { // CycloneModel<br>      if (AArch64_MC::isGPRZero(*MI))<br>        return 930; // WriteX<br>      if (true)<br>        return 962; // WriteImm<br>    }<br>    break;<br>  case 387: // ANDWri_ANDXri<br>    if (CPUID == 3) { // CycloneModel<br>      if (AArch64_MC::isGPRZero(*MI))<br>        return 930; // WriteX<br>      if (true)<br>        return 962; // WriteImm<br>    }<br>    break;<br>  case 695: // ANDWri<br>    if (CPUID == 3) { // CycloneModel<br>      if (AArch64_MC::isGPRZero(*MI))<br>        return 930; // WriteX<br>      if (true)<br>        return 962; // WriteImm<br>    }<br>    break;<br>  };<br>  // Don't know how to resolve this scheduling class.<br>  return 0;<br>  }<br>};<br>```<br><br>Note that this override will become a member of a new tablegen'd class named<br>AArch64GenMCSubtargetInfo. That class would directly extend MCSubtargetInfo.<br>Class AArch64GenMCSubtargetInfo is what will get instantiated by method<br>`Target::createMCSubtargetInfo()`.<br><br>----<br>Let's go back to the definition of IsGPRZero using a TIIPredicate.<br><br>```<br>def IsGPRZero : TIIPredicate<"AArch64", "isGPRZero",<br>  AnyOfMCPredicates<[CheckMOVZ, CheckANDW, CheckANDX, CheckCOPY]>>;<br>```<br><br>This is how the InstructionInfoEmitter expands the method in the tablegen'd<br>class AArch64GenInstrInfo:<br><br>```<br>  static bool isGPRZero(const MachineInstr &MI) {<br>    return (<br>      (<br>        (<br>          MI.getOpcode() == AArch64::MOVZWi<br>          || MI.getOpcode() == AArch64::MOVZXi<br>        )<br>        && MI.getNumOperands() == 3<br>        && MI.getOperand(1).isImm()<br>        && MI.getOperand(1).getImm() == 0<br>        && MI.getOperand(2).isImm()<br>        && MI.getOperand(2).getImm() == 0<br>      )<br>      || (<br>        ( MI.getOpcode() == AArch64::ANDWri )<br>        && MI.getOperand(1).isReg()<br>        && MI.getOperand(1).getReg() == AArch64::WZR<br>      )<br>      || (<br>        ( MI.getOpcode() == AArch64::ANDXri )<br>        && MI.getOperand(1).isReg()<br>        && MI.getOperand(1).getReg() == AArch64::XZR<br>      )<br>      || (<br>        ( MI.getOpcode() == TargetOpcode::COPY )<br>        && MI.getOperand(1).isReg()<br>        && MI.getOperand(1).getReg() == AArch64::WZR<br>      )<br>    );<br>  }<br>```<br><br>Another variant of function `isGPRZero` is expanded in the AArch64_MC<br>namespace (see below):<br><br>```<br>#ifdef GET_GENINSTRINFO_MC_DECL<br>#undef GET_GENINSTRINFO_MC_DECL<br>namespace llvm {<br>class MCInst;<br><br>namespace AArch64_MC {<br><br>bool isGPRZero(const MCInst &MI);<br><br>} // end AArch64_MC namespace<br>} // end llvm namespace<br>#endif // GET_GENINSTRINFO_MC_DECL<br><br>#ifdef GET_GENINSTRINFO_MC_HELPERS<br>#undef GET_GENINSTRINFO_MC_HELPERS<br>namespace llvm {<br>namespace AArch64_MC {<br><br>bool isGPRZero(const MCInst &MI) {<br>  return (<br>    (<br>      (<br>        MI.getOpcode() == AArch64::MOVZWi<br>        || MI.getOpcode() == AArch64::MOVZXi<br>      )<br>      && <...snip...><br>    )<br>  );<br>}  <br>} // end AArch64_MC namespace<br>} // end llvm namespace<br>#endif // GET_GENISTRINFO_MC_HELPERS<br>```<br><br>Function isGPRZero would live in namespace AArch64_MC.<br>The declaration of AArch64_MC::isGPRZero has to be made visible to<br>AArch64MCTargetDesc.h, so that it becomes known to the new<br>`resolveVariantSchedClass()` method.<br><br>As a side note: all this code is guarded by macro definitions. This allows to<br>control their expansion (if we decide that we don't want them).<br><br><br>What to do next<br>---------------<br>I have a series of three patches ready to be sent upstream for review.<br><br>The first patch is mostly a no functional change. It introduces the new<br>scheduling predicate class in tablegen, and it teaches the<br>InstructionInfoEmitter and the SubtargetEmitter how to expand MCSchedPredicate<br>definitions.<br>The first patch is up for review here: https:://<a href="http://reviews.llvm.org/D46695">reviews.llvm.org/D46695</a>.<br><br>The second patch would teach the SubtargetEmitter how to generate method<br>resolveVariantSchedClass().<br><br>The last patch of the sequence will teach llvm-mca how to use method<br>`resolveVariantSchedClass()` to resolve variant classes. llvm-mca will generate an error if the variant scheduling class cannot be resolved.<br><br>Review <a href="https://reviews.llvm.org/D46697">https://reviews.llvm.org/D46697</a> is the union of patch1 and patch2 only.<br>It is not meant to be reviewed at this stage, since it contains the code<br>changes related to patch1.<br><br>The third patch is available here: <a href="https://reviews.llvm.org/D46698">https://reviews.llvm.org/D46698</a>.<br>D46698 requires patch1 and patch2.<br><br>Bonus (optional) patches:<br> 1) [X86] Teach scheduling models how to recognize zero-idioms.<br>    This would make easier to review the llvm-mca change.<br> 2) [X86] Add variant scheduling classes for LEA instructions.<br> 3) [AArch64] Rewrite the predicates mentioned by this RFC.<br><br>People that are interested in seeing how to implement "optional" patch 3 can<br>have a look at the review here: <a href="https://reviews.llvm.org/D46701">https://reviews.llvm.org/D46701</a><br><br>Please let me know what you think.<br><br>Thanks,<br>Andrea<br></div>