[GlobalISel] NFCI, Getting GlobalISel ~5% faster

[rtereshin]

Summary

by replacing DenseMap with IndexedMap for LLTs within MRI, as
benchmarked by cross-compiling sqlite3 amalgamation for AArch64
on x86 machine.

Per-pass diffs follow:

IRTranslator: +0.1%
Legalizer: -4.5%
RegBankSelect: -4.4%
Localizer: -2.5%
InstructionSelect: -8.8%

Total GlobalISel: -5.5%

More data below:

llc -O0 -mtriple arm64-ios-apple sqlite3.bc -time-passes -time-compilations=20

	Before	After	Diff
GlobalISel 5 Passes	7.7847	7.3563
	7.7927	7.3586
	7.7896	7.3576
	7.7876	7.3538
	7.7703	7.3615
Min	7.770	7.354	-5.4%
Avg	7.785	7.358	-5.5%
Err	0.3%	0.1%
IRTranslator	1.7660	1.7682
	1.7737	1.7678
	1.7682	1.7674
	1.7626	1.7702
	1.7595	1.7667
Min	1.760	1.767	0.4%
Avg	1.766	1.768	0.1%
Err	0.8%	0.2%
Legalizer	0.8089	0.7729
	0.8073	0.7729
	0.8088	0.7732
	0.8099	0.7705
	0.8074	0.7720
Min	0.807	0.771	-4.6%
Avg	0.808	0.772	-4.5%
Err	0.3%	0.4%
RegBankSelect	0.8034	0.7638
	0.7988	0.7669
	0.8011	0.7635
	0.8004	0.7640
	0.7985	0.7670
Min	0.799	0.764	-4.4%
Avg	0.800	0.765	-4.4%
Err	0.6%	0.5%
Localizer	0.4800	0.4693
	0.4800	0.4684
	0.4804	0.4680
	0.4803	0.4676
	0.4797	0.4679
Min	0.480	0.468	-2.5%
Avg	0.480	0.468	-2.5%
Err	0.1%	0.4%
InstructionSelect	3.9264	3.5821
	3.9329	3.5826
	3.9311	3.5855
	3.9344	3.5815
	3.9252	3.5879
Min	3.925	3.582	-8.8%
Avg	3.930	3.584	-8.8%
Err	0.2%	0.2%
Notes:	Err = (Max - Min) / Min
	Diff = (After - Before) / Before

[paquette]

This is pretty non-invasive, so code LGTM aside from one minor stylistic comment on an assertion. I would wait for comments from another reviewer though, since I'm not super familiar with this particular bit of code.

It'd also be nice to just see the high level results of a CTMark run if possible? I love the in-depth data analysis here, but I think it would be nice to have a couple more data points just to make sure there are no regressions.

lib/CodeGen/GlobalISel/InstructionSelect.cpp

205

Maybe something like "VReg's low-level type and register class have different sizes" would be a bit more concise?

[rtereshin]

Updating a GISelFailure message so it sounds more like English ;-)

[rtereshin]

lib/CodeGen/GlobalISel/InstructionSelect.cpp

205

Absolutely, thanks for the suggestion. I'm updating the patch.

[qcolombet]

Nice finding Roman.

I second Jessica, we should have more comprehensive testing to make sure we are not optimizing for one benchmark.

Otherwise LGTM.

[rtereshin]

In D46809#1105122, @qcolombet wrote:

Nice finding Roman.

I second Jessica, we should have more comprehensive testing to make sure we are not optimizing for one benchmark.

Otherwise LGTM.

Thanks!

Here we go:

Name	Prev	Current	%	Δ	MAD	N
CTMark/7zip/7zip-benchmark	15.3903	15.2923	-0.64%	-0.0980	0.0047	30
CTMark/7zip/7zip-benchmark-link	0.0750	0.0745	-0.67%	-0.0005	0.0024	30
CTMark/Bullet/bullet	12.0264	11.9626	-0.53%	-0.0638	0.0081	30
CTMark/Bullet/bullet-link	0.0666	0.0662	-0.60%	-0.0004	0.0005	30
CTMark/ClamAV/clamscan	3.2851	3.2562	-0.88%	-0.0289	0.0034	30
CTMark/ClamAV/clamscan-link	0.0275	0.0275	0.00%	0.0000	0.0003	30
CTMark/SPASS/SPASS	2.6950	2.6815	-0.50%	-0.0135	0.0029	30
CTMark/SPASS/SPASS-link	0.0303	0.0303	0.00%	0.0000	0.0002	30
CTMark/consumer-typeset/consumer-typeset	2.5922	2.5650	-1.05%	-0.0272	0.0047	30
CTMark/consumer-typeset/consumer-typeset-link	0.0252	0.0252	0.00%	0.0000	0.0002	30
CTMark/kimwitu++/kc	5.8438	5.8180	-0.44%	-0.0258	0.0075	30
CTMark/kimwitu++/kc-link	0.0652	0.0649	-0.46%	-0.0003	0.0003	30
CTMark/lencod/lencod	2.4405	2.4152	-1.04%	-0.0253	0.0028	30
CTMark/lencod/lencod-link	0.0264	0.0264	0.00%	0.0000	0.0001	30
CTMark/mafft/pairlocalalign	1.2078	1.1960	-0.98%	-0.0118	0.0027	30
CTMark/mafft/pairlocalalign-link	0.0189	0.0189	0.00%	0.0000	0.0001	30
CTMark/sqlite3/sqlite3	0.6303	0.6200	-1.63%	-0.0103	0.0026	30
CTMark/sqlite3/sqlite3-link	0.0194	0.0193	-0.52%	-0.0001	0.0000	30
CTMark/tramp3d-v4/tramp3d-v4	3.6254	3.5962	-0.81%	-0.0292	0.0113	30
CTMark/tramp3d-v4/tramp3d-v4-link	0.1176	0.1173	-0.26%	-0.0003	0.0004	30

• Aggregation Function is Minimum
• Prev is r333057 (fb0360d185d35, Wed May 23 03:01:45 2018), MatchTable second level grouping, perf patch 5 has been recently applied.
• Current is the same + this patch.

Both are LLVM + Clang Release builds, assertions off, targets enabled are x86 and AArch64.

lnt is ran the following way:

lnt runtest test-suite --sandbox tmp --cc ./llvm/build/obj/bin/clang \
  --cxx ./llvm/build/obj/bin/clang++ --use-cmake /usr/local/bin/cmake \
  --use-lit ./llvm/build/obj/bin/llvm-lit --test-suite $SRC/llvm-test-suite \
  --cflags '-O0' --cxxflags '-O0' --only-compile --build-threads 1 \
  --cmake-define TEST_SUITE_SUBDIRS=CTMark \
  --cmake-cache ./llvm-test-suite/cmake/caches/target-arm64-iphoneos.cmake \
  --benchmarking-only --compile-multisample 30 --succinct-compile-output

The hardware is iMac (SSD) running macOS.

[rtereshin]

With the same config, but comparing pre- and post-https://reviews.llvm.org/D44700 (partially committed) + this patch:

Name	Prev	Current	%	Δ	MAD
CTMark/7zip/7zip-benchmark	15.4272	15.2943	-0.86%	-0.1329	0.0096
CTMark/7zip/7zip-benchmark-link	0.0779	0.0779	0.00%	0	0.0009
CTMark/Bullet/bullet	12.048	11.9608	-0.72%	-0.0872	0.0069
CTMark/Bullet/bullet-link	0.067	0.067	0.00%	0	0.0004
CTMark/ClamAV/clamscan	3.3472	3.2349	-3.36%	-0.1123	0.0037
CTMark/ClamAV/clamscan-link	0.028	0.028	0.00%	0	0.0002
CTMark/SPASS/SPASS	2.7473	2.6692	-2.84%	-0.0781	0.0027
CTMark/SPASS/SPASS-link	0.0305	0.0305	0.00%	0	0.0001
CTMark/consumer-typeset/consumer-typeset	2.6514	2.5437	-4.06%	-0.1077	0.0049
CTMark/consumer-typeset/consumer-typeset-link	0.0255	0.0255	0.00%	0	0.0001
CTMark/kimwitu++/kc	5.9477	5.8094	-2.33%	-0.1383	0.0057
CTMark/kimwitu++/kc-link	0.0653	0.0653	-0.08%	0	0.0003
CTMark/lencod/lencod	2.5105	2.3974	-4.51%	-0.1132	0.0026
CTMark/lencod/lencod-link	0.0268	0.0268	0.00%	0	0.0002
CTMark/mafft/pairlocalalign	1.2383	1.1894	-3.94%	-0.0489	0.0034
CTMark/mafft/pairlocalalign-link	0.019	0.019	0.00%	0	0.0001
CTMark/sqlite3/sqlite3	0.6788	0.6089	-10.30%	-0.0699	0.0027
CTMark/sqlite3/sqlite3-link	0.0195	0.0195	0.00%	0	0.0001
CTMark/tramp3d-v4/tramp3d-v4	3.7155	3.5861	-3.48%	-0.1294	0.0091
CTMark/tramp3d-v4/tramp3d-v4-link	0.1185	0.1184	-0.08%	-0.0001	0.0005

include/llvm/CodeGen/MachineRegisterInfo.h

private:
   BitVector UsedPhysRegMask;
 
   /// ReservedRegs - This is a bit vector of reserved registers.  The target
   /// may change its mind about which registers should be reserved.  This
   /// vector is the frozen set of reserved registers when register allocation
   /// started.
   BitVector ReservedRegs;
 
-  using VRegToTypeMap = DenseMap<unsigned, LLT>;
-  /// Map generic virtual registers to their actual size.
-  mutable std::unique_ptr<VRegToTypeMap> VRegToType;
+  using VRegToTypeMap = IndexedMap<LLT, VirtReg2IndexFunctor>;
+  /// Map generic virtual registers to their low-level type.
+  VRegToTypeMap VRegToType;
 
   /// Keep track of the physical registers that are live in to the function.
   /// Live in values are typically arguments in registers.  LiveIn values are
   /// allowed to have virtual registers associated with them, stored in the
   /// second element.
   std::vector<std::pair<unsigned, unsigned>> LiveIns;
 
 public:
public:
   /// the live range.
   bool recomputeRegClass(unsigned Reg);
 
   /// createVirtualRegister - Create and return a new virtual register in the
   /// function with the specified register class.
   unsigned createVirtualRegister(const TargetRegisterClass *RegClass,
                                  StringRef Name = "");
 
-  /// Accessor for VRegToType. This accessor should only be used
-  /// by global-isel related work.
-  VRegToTypeMap &getVRegToType() const {
-    if (!VRegToType)
-      VRegToType.reset(new VRegToTypeMap);
-    return *VRegToType.get();
-  }
-
-  /// Get the low-level type of \p VReg or LLT{} if VReg is not a generic
+  /// Get the low-level type of \p Reg or LLT{} if Reg is not a generic
   /// (target independent) virtual register.
-  LLT getType(unsigned VReg) const;
+  LLT getType(unsigned Reg) const {
+    if (TargetRegisterInfo::isVirtualRegister(Reg) && VRegToType.inBounds(Reg))
+      return VRegToType[Reg];
+    return LLT{};
+  }
 
   /// Set the low-level type of \p VReg to \p Ty.
   void setType(unsigned VReg, LLT Ty);
 
   /// Create and return a new generic virtual register with low-level
   /// type \p Ty.
   unsigned createGenericVirtualRegister(LLT Ty, StringRef Name = "");
 

lib/CodeGen/GlobalISel/InstructionSelect.cpp

bool InstructionSelect::runOnMachineFunction(MachineFunction &MF) {
   CodeGenCoverage CoverageInfo;
   assert(ISel && "Cannot work without InstructionSelector");
 
   // An optimization remark emitter. Used to report failures.
   MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
 
   // FIXME: There are many other MF/MFI fields we need to initialize.
 
-  const MachineRegisterInfo &MRI = MF.getRegInfo();
+  MachineRegisterInfo &MRI = MF.getRegInfo();
 #ifndef NDEBUG
   // Check that our input is fully legal: we require the function to have the
   // Legalized property, so it should be.
   // FIXME: This should be in the MachineVerifier, as the RegBankSelected
   // property check already is.
   if (!DisableGISelLegalityCheck)
     if (const MachineInstr *MI = machineFunctionIsIllegal(MF)) {
       reportGISelFailure(MF, TPC, MORE, "gisel-select",
for (auto MII = std::prev(MBB.end()), Begin = MBB.begin(); !ReachedBegin;) {
       else
         --MII;
       if (MI.getOpcode() != TargetOpcode::COPY)
         continue;
       unsigned SrcReg = MI.getOperand(1).getReg();
       unsigned DstReg = MI.getOperand(0).getReg();
       if (TargetRegisterInfo::isVirtualRegister(SrcReg) &&
           TargetRegisterInfo::isVirtualRegister(DstReg)) {
-        MachineRegisterInfo &MRI = MF.getRegInfo();
         auto SrcRC = MRI.getRegClass(SrcReg);
         auto DstRC = MRI.getRegClass(DstReg);
         if (SrcRC == DstRC) {
           MRI.replaceRegWith(DstReg, SrcReg);
           MI.eraseFromParentAndMarkDBGValuesForRemoval();
         }
       }
     }
   }
 
   // Now that selection is complete, there are no more generic vregs.  Verify
   // that the size of the now-constrained vreg is unchanged and that it has a
   // register class.
-  for (auto &VRegToType : MRI.getVRegToType()) {
-    unsigned VReg = VRegToType.first;
-    auto *RC = MRI.getRegClassOrNull(VReg);
+  for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {
+    unsigned VReg = TargetRegisterInfo::index2VirtReg(I);
+
     MachineInstr *MI = nullptr;
     if (!MRI.def_empty(VReg))
       MI = &*MRI.def_instr_begin(VReg);
     else if (!MRI.use_empty(VReg))
       MI = &*MRI.use_instr_begin(VReg);
+    if (!MI)
+      continue;
 
-    if (MI && !RC) {
+    const TargetRegisterClass *RC = MRI.getRegClassOrNull(VReg);
+    if (!RC) {
       reportGISelFailure(MF, TPC, MORE, "gisel-select",
                          "VReg has no regclass after selection", *MI);
       return false;
-    } else if (!RC)
-      continue;
+    }
 
-    if (VRegToType.second.isValid() &&
-        VRegToType.second.getSizeInBits() > TRI.getRegSizeInBits(*RC)) {
-      reportGISelFailure(MF, TPC, MORE, "gisel-select",
-                         "VReg has explicit size different from class size",
-                         *MI);
+    const LLT Ty = MRI.getType(VReg);
+    if (Ty.isValid() && Ty.getSizeInBits() > TRI.getRegSizeInBits(*RC)) {
+      reportGISelFailure(
+          MF, TPC, MORE, "gisel-select",
+          "VReg's low-level type and register class have different sizes", *MI);
       return false;
     }
   }
 
   if (MF.size() != NumBlocks) {
     MachineOptimizationRemarkMissed R("gisel-select", "GISelFailure",
                                       MF.getFunction().getSubprogram(),
                                       /*MBB=*/nullptr);
CoverageInfo.emit(CoveragePrefix,
                         .getTargetLowering()
                         ->getTargetMachine()
                         .getTarget()
                         .getBackendName());
 
   // If we successfully selected the function nothing is going to use the vreg
   // types after us (otherwise MIRPrinter would need them). Make sure the types
   // disappear.
-  MRI.getVRegToType().clear();
+  MRI.clearVirtRegTypes();
 
   // FIXME: Should we accurately track changes?
   return true;
 }

lib/CodeGen/MachineRegisterInfo.cpp

MachineRegisterInfo::createVirtualRegister(const TargetRegisterClass *RegClass,
   // New virtual register number.
   unsigned Reg = createIncompleteVirtualRegister(Name);
   VRegInfo[Reg].first = RegClass;
   if (TheDelegate)
     TheDelegate->MRI_NoteNewVirtualRegister(Reg);
   return Reg;
 }
 
-LLT MachineRegisterInfo::getType(unsigned VReg) const {
-  VRegToTypeMap::const_iterator TypeIt = getVRegToType().find(VReg);
-  return TypeIt != getVRegToType().end() ? TypeIt->second : LLT{};
-}
-
 void MachineRegisterInfo::setType(unsigned VReg, LLT Ty) {
   // Check that VReg doesn't have a class.
   assert((getRegClassOrRegBank(VReg).isNull() ||
          !getRegClassOrRegBank(VReg).is<const TargetRegisterClass *>()) &&
          "Can't set the size of a non-generic virtual register");
-  getVRegToType()[VReg] = Ty;
+  VRegToType.grow(VReg);
+  VRegToType[VReg] = Ty;
 }
 
 unsigned
 MachineRegisterInfo::createGenericVirtualRegister(LLT Ty, StringRef Name) {
   // New virtual register number.
   unsigned Reg = createIncompleteVirtualRegister(Name);
   // FIXME: Should we use a dummy register class?
   VRegInfo[Reg].first = static_cast<RegisterBank *>(nullptr);
-  getVRegToType()[Reg] = Ty;
+  setType(Reg, Ty);
   if (TheDelegate)
     TheDelegate->MRI_NoteNewVirtualRegister(Reg);
   return Reg;
 }
 
-void MachineRegisterInfo::clearVirtRegTypes() {
-  getVRegToType().clear();
-}
+void MachineRegisterInfo::clearVirtRegTypes() { VRegToType.clear(); }
 
 /// clearVirtRegs - Remove all virtual registers (after physreg assignment).
 void MachineRegisterInfo::clearVirtRegs() {
 #ifndef NDEBUG
   for (unsigned i = 0, e = getNumVirtRegs(); i != e; ++i) {
     unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
     if (!VRegInfo[Reg].second)
       continue;

lib/CodeGen/ResetMachineFunctionPass.cpp

public:
 
     StringRef getPassName() const override { return "ResetMachineFunction"; }
 
     bool runOnMachineFunction(MachineFunction &MF) override {
       // No matter what happened, whether we successfully selected the function
       // or not, nothing is going to use the vreg types after us. Make sure they
       // disappear.
       auto ClearVRegTypesOnReturn =
-          make_scope_exit([&MF]() { MF.getRegInfo().getVRegToType().clear(); });
+          make_scope_exit([&MF]() { MF.getRegInfo().clearVirtRegTypes(); });
 
       if (MF.getProperties().hasProperty(
               MachineFunctionProperties::Property::FailedISel)) {
         if (AbortOnFailedISel)
           report_fatal_error("Instruction selection failed");
         DEBUG(dbgs() << "Resetting: " << MF.getName() << '\n');
         ++NumFunctionsReset;
         MF.reset();