[RISCV] Added isCompressibleInst() to estimate size in getInstSizeInBytes()

[apazos]

Summary

Modified compression emitter tablegen backend to emit isCompressibleInst()
check which in turn is used by getInstSizeInBytes() to better estimate
instruction size. Note the generation of compressed instructions in RISC-V
happens late in the assembler therefore instruction size estimate might be off
if computed before.

[asb]

I like the direction of this, Thanks Ana. Did you look at modifying getInstSizeInBytes? That would benefit other callers beyond the outliner.

[lewis-revill]

Hi Ana, I'm yet to try this out on our benchmarks, but it looks like a good implementation to me. Considering Alex's comments above, should this patch be reduced to just the isCompressible check and I can merge the rest into the machine outliner patch after adding this one as a parent?

llvm/lib/Target/RISCV/RISCVInstrInfo.cpp

502

Nitpick: this should be called isCompressibleInst (IE with an i rather than an a).

[apazos]

Thanks Alex and Lewis.
I will break the patch in 3 commits:

1. fix missing ImmLeaf predicate, which I will merge directly (no review).
2. Compress Instr table gen back end changes. I will post this patch for review.
3. Modify getInstSizeInBytes to invoke isCompressibleInst (thanks for the name fix!). This one I will run a few more correctness tests, and then post for review.

[apazos]

llvm/lib/Target/RISCV/RISCVInstrInfoC.td

141 ↗

(On Diff #222675)

just noted a copy/paste error: I used isShiftedUInt, instead of isShiftedInt in both simm9_lsb0 and simm12_lsb0. Will fix it when committing the change.

[apazos]

Added check to verify whether MI is parentless or not because isCompressible call depends of function/module info.

[lenary]

Did this get merged, or is it still waiting on reviewers?

[apazos]

Rebased.
With this change, the regressions observed with the machine outliner are eliminated.
Sam, I don't think any one has reviewed yet.

[asb]

LGTM, thanks!

[lewis-revill]

Is this waiting for someone with commit access to go ahead?

[apazos]

My commit permissions were fixed last week, I will rebase and merge.

[apazos]

Rebased

llvm/lib/Target/RISCV/RISCVInstrInfo.cpp

 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/TargetRegistry.h"
 
 #define GET_INSTRINFO_CTOR_DTOR
 #include "RISCVGenInstrInfo.inc"
 
 using namespace llvm;
 
+#define GEN_CHECK_COMPRESS_INSTR
+#include "RISCVGenCompressInstEmitter.inc"
+
 RISCVInstrInfo::RISCVInstrInfo()
     : RISCVGenInstrInfo(RISCV::ADJCALLSTACKDOWN, RISCV::ADJCALLSTACKUP) {}
 
 unsigned RISCVInstrInfo::isLoadFromStackSlot(const MachineInstr &MI,
                                              int &FrameIndex) const {
   switch (MI.getOpcode()) {
   default:
     return 0;
case RISCV::PseudoBR:
     return isIntN(21, BrOffset);
   }
 }
 
 unsigned RISCVInstrInfo::getInstSizeInBytes(const MachineInstr &MI) const {
   unsigned Opcode = MI.getOpcode();
 
   switch (Opcode) {
-  default: { return get(Opcode).getSize(); }
+  default: {
+    if (MI.getParent() && MI.getParent()->getParent()) {
+      const auto MF = MI.getMF();
+      const auto &TM = static_cast<const RISCVTargetMachine &>(MF->getTarget());
+      const MCRegisterInfo &MRI = *TM.getMCRegisterInfo();
+      const MCSubtargetInfo &STI = *TM.getMCSubtargetInfo();
+      const RISCVSubtarget &ST = MF->getSubtarget<RISCVSubtarget>();
+      if (isCompressibleInst(MI, &ST, MRI, STI))
+        return 2;
+    }
+    return get(Opcode).getSize();
+  }
   case TargetOpcode::EH_LABEL:
   case TargetOpcode::IMPLICIT_DEF:
   case TargetOpcode::KILL:
   case TargetOpcode::DBG_VALUE:
     return 0;
   case RISCV::PseudoCALLReg:
   case RISCV::PseudoCALL:
   case RISCV::PseudoTAIL:
switch(Opcode) {
     default:
       break;
     case RISCV::ADDI:
     case RISCV::ORI:
     case RISCV::XORI:
       return (MI.getOperand(1).isReg() && MI.getOperand(1).getReg() == RISCV::X0);
   }
   return MI.isAsCheapAsAMove();
 }

llvm/utils/TableGen/RISCVCompressInstEmitter.cpp

 // bool compressInst(MCInst& OutInst, const MCInst &MI,
 //                   const MCSubtargetInfo &STI,
 //                   MCContext &Context);
 //
 // bool uncompressInst(MCInst& OutInst, const MCInst &MI,
 //                     const MCRegisterInfo &MRI,
 //                     const MCSubtargetInfo &STI);
 //
+// In addition, it exports a function for checking whether
+// an instruction is compressable:
+//
+// bool isCompressibleInst(const MachineInstr& MI,
+//                           const RISCVSubtarget *Subtarget,
+//                           const MCRegisterInfo &MRI,
+//                           const MCSubtargetInfo &STI);
+//
 // The clients that include this auto-generated header file and
 // invoke these functions can compress an instruction before emitting
 // it in the target-specific ASM or ELF streamer or can uncompress
 // an instruction before printing it when the expanded instruction
 // format aliases is favored.
 
 //===----------------------------------------------------------------------===//
 
IndexedMap<OpData>
         DestOperandMap; // Maps operands in the Dest Instruction
                         // to the corresponding Source instruction operand.
     CompressPat(CodeGenInstruction &S, CodeGenInstruction &D,
                 std::vector<Record *> RF, IndexedMap<OpData> &SourceMap,
                 IndexedMap<OpData> &DestMap)
         : Source(S), Dest(D), PatReqFeatures(RF), SourceOperandMap(SourceMap),
           DestOperandMap(DestMap) {}
   };
-
+  enum EmitterType { Compress, Uncompress, CheckCompress };
   RecordKeeper &Records;
   CodeGenTarget Target;
   SmallVector<CompressPat, 4> CompressPatterns;
 
   void addDagOperandMapping(Record *Rec, DagInit *Dag, CodeGenInstruction &Inst,
                             IndexedMap<OpData> &OperandMap, bool IsSourceInst);
   void evaluateCompressPat(Record *Compress);
-  void emitCompressInstEmitter(raw_ostream &o, bool Compress);
+  void emitCompressInstEmitter(raw_ostream &o, EmitterType EType);
   bool validateTypes(Record *SubType, Record *Type, bool IsSourceInst);
   bool validateRegister(Record *Reg, Record *RegClass);
   void createDagOperandMapping(Record *Rec, StringMap<unsigned> &SourceOperands,
                                StringMap<unsigned> &DestOperands,
                                DagInit *SourceDag, DagInit *DestDag,
                                IndexedMap<OpData> &SourceOperandMap);
 
   void createInstOperandMapping(Record *Rec, DagInit *SourceDag,
for (auto &R : ReqFeatures) {
     assert(!Ops.empty() && "AssemblerCondString cannot be empty");
     for (auto &Op : Ops) {
       assert(!Op.empty() && "Empty operator");
       FeaturesSet.insert(Op);
     }
   }
 }
 
-unsigned getMCOpPredicate(DenseMap<const Record *, unsigned> &MCOpPredicateMap,
-                          std::vector<const Record *> &MCOpPredicates,
-                          Record *Rec) {
-  unsigned Entry = MCOpPredicateMap[Rec];
+static unsigned getPredicates(DenseMap<const Record *, unsigned> &PredicateMap,
+                              std::vector<const Record *> &Predicates,
+                              Record *Rec, StringRef Name) {
+  unsigned Entry = PredicateMap[Rec];
   if (Entry)
     return Entry;
 
-  if (!Rec->isValueUnset("MCOperandPredicate")) {
-    MCOpPredicates.push_back(Rec);
-    Entry = MCOpPredicates.size();
-    MCOpPredicateMap[Rec] = Entry;
+  if (!Rec->isValueUnset(Name)) {
+    Predicates.push_back(Rec);
+    Entry = Predicates.size();
+    PredicateMap[Rec] = Entry;
     return Entry;
   }
 
-  PrintFatalError(Rec->getLoc(),
-                  "No MCOperandPredicate on this operand at all: " +
-                      Rec->getName().str() + "'");
+  PrintFatalError(Rec->getLoc(), "No " + Name +
+    " predicate on this operand at all: '" + Rec->getName().str() + "'");
   return 0;
 }
 
+static void printPredicates(std::vector<const Record *> &Predicates,
+                            StringRef Name, raw_ostream &o) {
+  for (unsigned i = 0; i < Predicates.size(); ++i) {
+    Init *Pred = Predicates[i]->getValueInit(Name);
+    if (CodeInit *SI = dyn_cast<CodeInit>(Pred))
+      o << "  case " << i + 1 << ": {\n"
+        << "  // " << Predicates[i]->getName().str() << "\n"
+        << "  " << SI->getValue() << "\n"
+        << "  }\n";
+    else
+      llvm_unreachable("Unexpected predicate field!");
+  }
+}
+
 static std::string mergeCondAndCode(raw_string_ostream &CondStream,
                                     raw_string_ostream &CodeStream) {
   std::string S;
   raw_string_ostream CombinedStream(S);
   CombinedStream.indent(4)
       << "if ("
       << CondStream.str().substr(
              6, CondStream.str().length() -
                     10) // remove first indentation and last '&&'.
       << ") {\n";
   CombinedStream << CodeStream.str();
   CombinedStream.indent(4) << "  return true;\n";
   CombinedStream.indent(4) << "} // if\n";
   return CombinedStream.str();
 }
 
 void RISCVCompressInstEmitter::emitCompressInstEmitter(raw_ostream &o,
-                                                       bool Compress) {
+                                                       EmitterType EType) {
   Record *AsmWriter = Target.getAsmWriter();
   if (!AsmWriter->getValueAsInt("PassSubtarget"))
     PrintFatalError(AsmWriter->getLoc(),
                     "'PassSubtarget' is false. SubTargetInfo object is needed "
                     "for target features.\n");
 
   std::string Namespace = Target.getName();
 
   // Sort entries in CompressPatterns to handle instructions that can have more
   // than one candidate for compression\uncompression, e.g ADD can be
   // transformed to a C_ADD or a C_MV. When emitting 'uncompress()' function the
   // source and destination are flipped and the sort key needs to change
   // accordingly.
   llvm::stable_sort(CompressPatterns,
-                    [Compress](const CompressPat &LHS, const CompressPat &RHS) {
-                      if (Compress)
+                    [EType](const CompressPat &LHS, const CompressPat &RHS) {
+                      if (EType == EmitterType::Compress ||
+                        EType == EmitterType::CheckCompress)
                         return (LHS.Source.TheDef->getName().str() <
                                 RHS.Source.TheDef->getName().str());
                       else
                         return (LHS.Dest.TheDef->getName().str() <
                                 RHS.Dest.TheDef->getName().str());
                     });
 
   // A list of MCOperandPredicates for all operands in use, and the reverse map.
   std::vector<const Record *> MCOpPredicates;
   DenseMap<const Record *, unsigned> MCOpPredicateMap;
+  // A list of ImmLeaf Predicates for all operands in use, and the reverse map.
+  std::vector<const Record *> ImmLeafPredicates;
+  DenseMap<const Record *, unsigned> ImmLeafPredicateMap;
 
   std::string F;
   std::string FH;
   raw_string_ostream Func(F);
   raw_string_ostream FuncH(FH);
   bool NeedMRI = false;
 
-  if (Compress)
+  if (EType == EmitterType::Compress)
     o << "\n#ifdef GEN_COMPRESS_INSTR\n"
       << "#undef GEN_COMPRESS_INSTR\n\n";
-  else
+  else if (EType == EmitterType::Uncompress)
     o << "\n#ifdef GEN_UNCOMPRESS_INSTR\n"
       << "#undef GEN_UNCOMPRESS_INSTR\n\n";
+  else if (EType == EmitterType::CheckCompress)
+    o << "\n#ifdef GEN_CHECK_COMPRESS_INSTR\n"
+      << "#undef GEN_CHECK_COMPRESS_INSTR\n\n";
 
-  if (Compress) {
+  if (EType == EmitterType::Compress) {
     FuncH << "static bool compressInst(MCInst& OutInst,\n";
     FuncH.indent(25) << "const MCInst &MI,\n";
     FuncH.indent(25) << "const MCSubtargetInfo &STI,\n";
     FuncH.indent(25) << "MCContext &Context) {\n";
-  } else {
+  } else if (EType == EmitterType::Uncompress){
     FuncH << "static bool uncompressInst(MCInst& OutInst,\n";
     FuncH.indent(27) << "const MCInst &MI,\n";
     FuncH.indent(27) << "const MCRegisterInfo &MRI,\n";
     FuncH.indent(27) << "const MCSubtargetInfo &STI) {\n";
+  } else if (EType == EmitterType::CheckCompress) {
+    FuncH << "static bool isCompressibleInst(const MachineInstr& MI,\n";
+    FuncH.indent(27) << "const RISCVSubtarget *Subtarget,\n";
+    FuncH.indent(27) << "const MCRegisterInfo &MRI,\n";
+    FuncH.indent(27) << "const MCSubtargetInfo &STI) {\n";
   }
 
   if (CompressPatterns.empty()) {
     o << FuncH.str();
     o.indent(2) << "return false;\n}\n";
-    if (Compress)
+    if (EType == EmitterType::Compress)
       o << "\n#endif //GEN_COMPRESS_INSTR\n";
-    else
+    else if (EType == EmitterType::Uncompress)
       o << "\n#endif //GEN_UNCOMPRESS_INSTR\n\n";
+    else if (EType == EmitterType::CheckCompress)
+      o << "\n#endif //GEN_CHECK_COMPRESS_INSTR\n\n";
     return;
   }
 
   std::string CaseString("");
   raw_string_ostream CaseStream(CaseString);
   std::string PrevOp("");
   std::string CurOp("");
   CaseStream << "  switch (MI.getOpcode()) {\n";
   CaseStream << "    default: return false;\n";
 
+  bool CompressOrCheck =
+    EType == EmitterType::Compress || EType == EmitterType::CheckCompress;
+  bool CompressOrUncompress =
+    EType == EmitterType::Compress || EType == EmitterType::Uncompress;
+
   for (auto &CompressPat : CompressPatterns) {
     std::string CondString;
     std::string CodeString;
     raw_string_ostream CondStream(CondString);
     raw_string_ostream CodeStream(CodeString);
     CodeGenInstruction &Source =
-        Compress ? CompressPat.Source : CompressPat.Dest;
-    CodeGenInstruction &Dest = Compress ? CompressPat.Dest : CompressPat.Source;
-    IndexedMap<OpData> SourceOperandMap =
-        Compress ? CompressPat.SourceOperandMap : CompressPat.DestOperandMap;
-    IndexedMap<OpData> &DestOperandMap =
-        Compress ? CompressPat.DestOperandMap : CompressPat.SourceOperandMap;
+        CompressOrCheck ?  CompressPat.Source : CompressPat.Dest;
+    CodeGenInstruction &Dest =
+        CompressOrCheck ? CompressPat.Dest : CompressPat.Source;
+    IndexedMap<OpData> SourceOperandMap = CompressOrCheck ?
+      CompressPat.SourceOperandMap : CompressPat.DestOperandMap;
+    IndexedMap<OpData> &DestOperandMap = CompressOrCheck ?
+      CompressPat.DestOperandMap : CompressPat.SourceOperandMap;
 
     CurOp = Source.TheDef->getName().str();
     // Check current and previous opcode to decide to continue or end a case.
     if (CurOp != PrevOp) {
       if (PrevOp != "")
         CaseStream.indent(6) << "break;\n    } // case " + PrevOp + "\n";
       CaseStream.indent(4) << "case " + Namespace + "::" + CurOp + ": {\n";
     }
for (OpNo = 0; OpNo < Source.Operands.size(); ++OpNo) {
         CondStream.indent(6) << "(MI.getOperand(" + std::to_string(OpNo) +
                                     ").getReg() == " + Namespace +
                                     "::" + Reg->getName().str() + ") &&\n";
         break;
       }
       }
     }
     CodeStream.indent(6) << "// " + Dest.AsmString + "\n";
+    if (CompressOrUncompress)
       CodeStream.indent(6) << "OutInst.setOpcode(" + Namespace +
                                 "::" + Dest.TheDef->getName().str() + ");\n";
     OpNo = 0;
     for (const auto &DestOperand : Dest.Operands) {
       CodeStream.indent(6) << "// Operand: " + DestOperand.Name + "\n";
       switch (DestOperandMap[OpNo].Kind) {
       case OpData::Operand: {
         unsigned OpIdx = DestOperandMap[OpNo].Data.Operand;
         // Check that the operand in the Source instruction fits
         // the type for the Dest instruction.
         if (DestOperand.Rec->isSubClassOf("RegisterClass")) {
           NeedMRI = true;
           // This is a register operand. Check the register class.
           // Don't check register class if this is a tied operand, it was done
           // for the operand its tied to.
           if (DestOperand.getTiedRegister() == -1)
             CondStream.indent(6)
                 << "(MRI.getRegClass(" + Namespace +
                        "::" + DestOperand.Rec->getName().str() +
                        "RegClassID).contains(" + "MI.getOperand(" +
                        std::to_string(OpIdx) + ").getReg())) &&\n";
 
+          if (CompressOrUncompress)
             CodeStream.indent(6) << "OutInst.addOperand(MI.getOperand(" +
                                         std::to_string(OpIdx) + "));\n";
         } else {
           // Handling immediate operands.
-          unsigned Entry = getMCOpPredicate(MCOpPredicateMap, MCOpPredicates,
-                                            DestOperand.Rec);
+          if (CompressOrUncompress) {
+            unsigned Entry = getPredicates(MCOpPredicateMap, MCOpPredicates,
+              DestOperand.Rec, StringRef("MCOperandPredicate"));
             CondStream.indent(6) << Namespace + "ValidateMCOperand(" +
                                         "MI.getOperand(" + std::to_string(OpIdx) +
                                         "), STI, " + std::to_string(Entry) +
                                         ") &&\n";
+          } else {
+            unsigned Entry = getPredicates(ImmLeafPredicateMap, ImmLeafPredicates,
+              DestOperand.Rec, StringRef("ImmediateCode"));
+            CondStream.indent(6) << "MI.getOperand(" + std::to_string(OpIdx) +
+                                    ").isImm() && \n";
+            CondStream.indent(6) << Namespace + "ValidateMachineOperand(" +
+                                        "MI.getOperand(" + std::to_string(OpIdx) +
+                                        "), Subtarget, " + std::to_string(Entry) +
+                                        ") &&\n";
+          }
+          if (CompressOrUncompress)
             CodeStream.indent(6) << "OutInst.addOperand(MI.getOperand(" +
                                         std::to_string(OpIdx) + "));\n";
         }
         break;
       }
       case OpData::Imm: {
-        unsigned Entry =
-            getMCOpPredicate(MCOpPredicateMap, MCOpPredicates, DestOperand.Rec);
+        if (CompressOrUncompress) {
+          unsigned Entry = getPredicates(MCOpPredicateMap, MCOpPredicates,
+            DestOperand.Rec, StringRef("MCOperandPredicate"));
           CondStream.indent(6)
               << Namespace + "ValidateMCOperand(" + "MCOperand::createImm(" +
                      std::to_string(DestOperandMap[OpNo].Data.Imm) + "), STI, " +
                      std::to_string(Entry) + ") &&\n";
+        } else {
+          unsigned Entry = getPredicates(ImmLeafPredicateMap, ImmLeafPredicates,
+            DestOperand.Rec, StringRef("ImmediateCode"));
+          CondStream.indent(6)
+              << Namespace + "ValidateMachineOperand(" + "MachineOperand::CreateImm(" +
+                     std::to_string(DestOperandMap[OpNo].Data.Imm) + "), SubTarget, " +
+                     std::to_string(Entry) + ") &&\n";
+        }
+        if (CompressOrUncompress)
           CodeStream.indent(6)
               << "OutInst.addOperand(MCOperand::createImm(" +
                      std::to_string(DestOperandMap[OpNo].Data.Imm) + "));\n";
       } break;
       case OpData::Reg: {
+        if (CompressOrUncompress) {
           // Fixed register has been validated at pattern validation time.
           Record *Reg = DestOperandMap[OpNo].Data.Reg;
           CodeStream.indent(6) << "OutInst.addOperand(MCOperand::createReg(" +
                                       Namespace + "::" + Reg->getName().str() +
                                       "));\n";
+        }
       } break;
       }
       ++OpNo;
     }
     CaseStream << mergeCondAndCode(CondStream, CodeStream);
     PrevOp = CurOp;
   }
   Func << CaseStream.str() << "\n";
   // Close brace for the last case.
   Func.indent(4) << "} // case " + CurOp + "\n";
   Func.indent(2) << "} // switch\n";
   Func.indent(2) << "return false;\n}\n";
 
   if (!MCOpPredicates.empty()) {
     o << "static bool " << Namespace
       << "ValidateMCOperand(const MCOperand &MCOp,\n"
       << "                  const MCSubtargetInfo &STI,\n"
       << "                  unsigned PredicateIndex) {\n"
       << "  switch (PredicateIndex) {\n"
       << "  default:\n"
       << "    llvm_unreachable(\"Unknown MCOperandPredicate kind\");\n"
       << "    break;\n";
 
-    for (unsigned i = 0; i < MCOpPredicates.size(); ++i) {
-      Init *MCOpPred = MCOpPredicates[i]->getValueInit("MCOperandPredicate");
-      if (CodeInit *SI = dyn_cast<CodeInit>(MCOpPred))
-        o << "  case " << i + 1 << ": {\n"
-          << "   // " << MCOpPredicates[i]->getName().str() << SI->getValue()
-          << "\n"
-          << "    }\n";
-      else
-        llvm_unreachable("Unexpected MCOperandPredicate field!");
-    }
+    printPredicates(MCOpPredicates, "MCOperandPredicate", o);
+
+    o << "  }\n"
+      << "}\n\n";
+
+  if (!ImmLeafPredicates.empty()) {
+    o << "static bool " << Namespace
+      << "ValidateMachineOperand(const MachineOperand &MO,\n"
+      << "                  const RISCVSubtarget *Subtarget,\n"
+      << "                  unsigned PredicateIndex) {\n"
+      << "  int64_t Imm = MO.getImm(); \n"
+      << "  switch (PredicateIndex) {\n"
+      << "  default:\n"
+      << "    llvm_unreachable(\"Unknown ImmLeaf Predicate kind\");\n"
+      << "    break;\n";
+
+    printPredicates(ImmLeafPredicates, "ImmediateCode", o);
+
     o << "  }\n"
       << "}\n\n";
   }
 
   o << FuncH.str();
-  if (NeedMRI && Compress)
+  if (NeedMRI && EType == EmitterType::Compress)
     o.indent(2) << "const MCRegisterInfo &MRI = *Context.getRegisterInfo();\n";
   o << Func.str();
 
-  if (Compress)
+  if (EType == EmitterType::Compress)
     o << "\n#endif //GEN_COMPRESS_INSTR\n";
-  else
+  else if (EType == EmitterType::Uncompress)
     o << "\n#endif //GEN_UNCOMPRESS_INSTR\n\n";
+  else if (EType == EmitterType::CheckCompress)
+    o << "\n#endif //GEN_CHECK_COMPRESS_INSTR\n\n";
 }
 
 void RISCVCompressInstEmitter::run(raw_ostream &o) {
   Record *CompressClass = Records.getClass("CompressPat");
   assert(CompressClass && "Compress class definition missing!");
   std::vector<Record *> Insts;
   for (const auto &D : Records.getDefs()) {
     if (D.second->isSubClassOf(CompressClass))
       Insts.push_back(D.second.get());
   }
 
   // Process the CompressPat definitions, validating them as we do so.
   for (unsigned i = 0, e = Insts.size(); i != e; ++i)
     evaluateCompressPat(Insts[i]);
 
   // Emit file header.
   emitSourceFileHeader("Compress instruction Source Fragment", o);
   // Generate compressInst() function.
-  emitCompressInstEmitter(o, true);
+  emitCompressInstEmitter(o, EmitterType::Compress);
   // Generate uncompressInst() function.
-  emitCompressInstEmitter(o, false);
+  emitCompressInstEmitter(o, EmitterType::Uncompress);
+  // Generate isCompressibleInst() function.
+  emitCompressInstEmitter(o, EmitterType::CheckCompress);
 }
 
 namespace llvm {
 
 void EmitCompressInst(RecordKeeper &RK, raw_ostream &OS) {
   RISCVCompressInstEmitter(RK).run(OS);
 }
 
 } // namespace llvm