[GlobalISel][Tablegen] Assign small opcodes to pseudos

[rtereshin]

Summary

Sort pseudo instructions first while emitting enum's for target
instructions info. That puts them close to each other and to generic
G_* opcodes for GlobalISel. This makes it easier to build small jump
tables over opcodes that could be directly embedded into MatchTable's
Tablegen'erated for GlobalISel's InstructionSelect.

New order breaks instregex, thus this patch also fixes that.

There is an NFC going before this patch to tidy up the implementation a little and make the diff smaller.

[bogner]

lg

utils/TableGen/CodeGenTarget.cpp

386–387 ↗

(On Diff #148140)

Should probably update this comment.

[rtereshin]

Hi Justin,

Thanks for looking into this.

Roman

utils/TableGen/CodeGenTarget.cpp

386–387 ↗

(On Diff #148140)

Good catch! Will do.

llvm/trunk/utils/TableGen/CodeGenSchedule.cpp

struct InstRegexOp : public SetTheory::Operator {
   }
 
   void apply(SetTheory &ST, DagInit *Expr, SetTheory::RecSet &Elts,
              ArrayRef<SMLoc> Loc) override {
     ArrayRef<const CodeGenInstruction *> Instructions =
         Target.getInstructionsByEnumValue();
 
     unsigned NumGeneric = Target.getNumFixedInstructions();
+    unsigned NumPseudos = Target.getNumPseudoInstructions();
     auto Generics = Instructions.slice(0, NumGeneric);
-    auto NonGenerics = Instructions.slice(NumGeneric);
+    auto Pseudos = Instructions.slice(NumGeneric, NumPseudos);
+    auto NonPseudos = Instructions.slice(NumGeneric + NumPseudos);
 
     for (Init *Arg : make_range(Expr->arg_begin(), Expr->arg_end())) {
       StringInit *SI = dyn_cast<StringInit>(Arg);
       if (!SI)
         PrintFatalError(Loc, "instregex requires pattern string: " +
                                  Expr->getAsString());
       StringRef Original = SI->getValue();
 
for (Init *Arg : make_range(Expr->arg_begin(), Expr->arg_end())) {
         StringRef InstName = Inst->TheDef->getName();
         if (InstName.startswith(Prefix) &&
             (!Regexpr || Regexpr->match(InstName.substr(Prefix.size())))) {
           Elts.insert(Inst->TheDef);
           NumMatches++;
         }
       }
 
-      // Target instructions are sorted. Find the range that starts with our
-      // prefix.
+      // Target instructions are split into two ranges: pseudo instructions
+      // first, than non-pseudos. Each range is in lexicographical order
+      // sorted by name. Find the sub-ranges that start with our prefix.
       struct Comp {
         bool operator()(const CodeGenInstruction *LHS, StringRef RHS) {
           return LHS->TheDef->getName() < RHS;
         }
         bool operator()(StringRef LHS, const CodeGenInstruction *RHS) {
           return LHS < RHS->TheDef->getName() &&
                  !RHS->TheDef->getName().startswith(LHS);
         }
       };
-      auto Range = std::equal_range(NonGenerics.begin(), NonGenerics.end(),
+      auto Range1 =
+          std::equal_range(Pseudos.begin(), Pseudos.end(), Prefix, Comp());
+      auto Range2 = std::equal_range(NonPseudos.begin(), NonPseudos.end(),
                                      Prefix, Comp());
 
-      // For this range we know that it starts with the prefix. Check if there's
-      // a regex that needs to be checked.
+      // For these ranges we know that instruction names start with the prefix.
+      // Check if there's a regex that needs to be checked.
       const auto HandleNonGeneric = [&](const CodeGenInstruction *Inst) {
         StringRef InstName = Inst->TheDef->getName();
         if (!Regexpr || Regexpr->match(InstName.substr(Prefix.size()))) {
           Elts.insert(Inst->TheDef);
           NumMatches++;
         }
       };
-      std::for_each(Range.first, Range.second, HandleNonGeneric);
+      std::for_each(Range1.first, Range1.second, HandleNonGeneric);
+      std::for_each(Range2.first, Range2.second, HandleNonGeneric);
 
       if (0 == NumMatches)
         PrintFatalError(Loc, "instregex has no matches: " + Original);
     }
   }
 };
 
 } // end anonymous namespace

llvm/trunk/utils/TableGen/CodeGenTarget.h

class CodeGenTarget {
   CodeGenHwModes CGH;
   void ReadRegAltNameIndices() const;
   void ReadInstructions() const;
   void ReadLegalValueTypes() const;
 
   mutable std::unique_ptr<CodeGenSchedModels> SchedModels;
 
   mutable std::vector<const CodeGenInstruction*> InstrsByEnum;
+  mutable unsigned NumPseudoInstructions = 0;
 public:
   CodeGenTarget(RecordKeeper &Records);
   ~CodeGenTarget();
 
   Record *getTargetRecord() const { return TargetRec; }
   const StringRef getName() const;
 
   /// getInstNamespace - Return the target-specific instruction namespace.
CodeGenInstruction &getInstruction(const Record *InstRec) const {
     auto I = Instructions.find(InstRec);
     assert(I != Instructions.end() && "Not an instruction");
     return *I->second;
   }
 
   /// Returns the number of predefined instructions.
   static unsigned getNumFixedInstructions();
 
+  /// Returns the number of pseudo instructions.
+  unsigned getNumPseudoInstructions() const {
+    if (InstrsByEnum.empty())
+      ComputeInstrsByEnum();
+    return NumPseudoInstructions;
+  }
+
   /// Return all of the instructions defined by the target, ordered by their
   /// enum value.
+  /// The following order of instructions is also guaranteed:
+  /// - fixed / generic instructions as declared in TargetOpcodes.def, in order;
+  /// - pseudo instructions in lexicographical order sorted by name;
+  /// - other instructions in lexicographical order sorted by name.
   ArrayRef<const CodeGenInstruction *> getInstructionsByEnumValue() const {
     if (InstrsByEnum.empty())
       ComputeInstrsByEnum();
     return InstrsByEnum;
   }
 
   typedef ArrayRef<const CodeGenInstruction *>::const_iterator inst_iterator;
   inst_iterator inst_begin() const{return getInstructionsByEnumValue().begin();}

llvm/trunk/utils/TableGen/CodeGenTarget.cpp

for (const char *const *p = FixedInstrs; *p; ++p) {
     InstrsByEnum.push_back(Instr);
   }
   unsigned EndOfPredefines = InstrsByEnum.size();
   assert(EndOfPredefines == getNumFixedInstructions() &&
          "Missing generic opcode");
 
   for (const auto &I : Insts) {
     const CodeGenInstruction *CGI = I.second.get();
-    if (CGI->Namespace != "TargetOpcode")
+    if (CGI->Namespace != "TargetOpcode") {
       InstrsByEnum.push_back(CGI);
+      if (CGI->TheDef->getValueAsBit("isPseudo"))
+        ++NumPseudoInstructions;
+    }
   }
 
   assert(InstrsByEnum.size() == Insts.size() && "Missing predefined instr");
 
   // All of the instructions are now in random order based on the map iteration.
-  // Sort them by name.
-  llvm::sort(InstrsByEnum.begin() + EndOfPredefines, InstrsByEnum.end(),
-             [](const CodeGenInstruction *Rec1,
-                const CodeGenInstruction *Rec2) {
-    return Rec1->TheDef->getName() < Rec2->TheDef->getName();
+  llvm::sort(
+      InstrsByEnum.begin() + EndOfPredefines, InstrsByEnum.end(),
+      [](const CodeGenInstruction *Rec1, const CodeGenInstruction *Rec2) {
+        const auto &D1 = *Rec1->TheDef;
+        const auto &D2 = *Rec2->TheDef;
+        return std::make_tuple(!D1.getValueAsBit("isPseudo"), D1.getName()) <
+               std::make_tuple(!D2.getValueAsBit("isPseudo"), D2.getName());
       });
 }
 
 
 /// isLittleEndianEncoding - Return whether this target encodes its instruction
 /// in little-endian format, i.e. bits laid out in the order [0..n]
 ///
 bool CodeGenTarget::isLittleEndianEncoding() const {
   return getInstructionSet()->getValueAsBit("isLittleEndianEncoding");