[GlobalISel] Use slot indexes to speed up huge block compile time

[aemerson]

Summary

As an alternative to setting threshold limits on CSE dominator queries, this approach requires tht the SlotIndex analysis be run before legalization, and to use the numbering to do constant time dominance checks. There is added complexity in needing to maintain the numbering as we add/remove instructions from the block.

Overall this seems to impact compile time negatively by about ~0.5% on -O0 and -Os but prevents us from having unreasonably long compile times in the worst cases.

[arsenm]

I still think the CSE MIR builder shouldn't be required to CSE and can bail early on long dominance queries

[aemerson]

In D93423#2458972, @arsenm wrote:

I still think the CSE MIR builder shouldn't be required to CSE and can bail early on long dominance queries

Agreed.

Another approach I tried which also worked is to prevent the IRTranslator from merging the constant entry block with it's successor, and delaying that until after the legalizer finished. Combined with also forcing the MIRBuilder to always look for constants to CSE in the entry block of the function, that fixed the issue. Quentin didn't think that was the right approach from a design POV. We have 3 options here, I think SlotIndexes are reasonable but they do seem to incur a slight compile time cost.

[aditya_nandakumar]

In D93423#2458972, @arsenm wrote:

I still think the CSE MIR builder shouldn't be required to CSE and can bail early on long dominance queries

I guess the concern is how exactly one defines "early" and "long". Should it be universal? Opt in? Configurable ?.. What if it bailed just a few instructions away from the target instruction. What about the compile time impact of counting and checking in loop in the cases where you don't need and so on.

[aditya_nandakumar]

If slot indexes are preserved and used in other passes that use CSE, do you think the compile time impact is amortized/minimized?

[aemerson]

In D93423#2459003, @aditya_nandakumar wrote:

In D93423#2458972, @arsenm wrote:

I still think the CSE MIR builder shouldn't be required to CSE and can bail early on long dominance queries

I guess the concern is how exactly one defines "early" and "long". Should it be universal? Opt in? Configurable ?.. What if it bailed just a few instructions away from the target instruction. What about the compile time impact of counting and checking in loop in the cases where you don't need and so on.

I don't know if it's feasible to dynamically require SlotIndexes to be run, but if it is: to ensure we never have different codegen depending on the threshold we can conditionally use SlotIndexes when we detect earlier on (maybe after translation), that the function we're compiling, or at least the entry block, is very large. If we detect that say the block is 100k generic instructions long, we could set a flag somewhere to indicate that and switch to using the indexes vs linked list walk.

[aemerson]

In D93423#2459004, @aditya_nandakumar wrote:

If slot indexes are preserved and used in other passes that use CSE, do you think the compile time impact is amortized/minimized?

It's possible it would help a bit. I think the localizer may also benefit from this. I don't see it making a big difference either way though in most code.

[aditya_nandakumar]

In D93423#2459018, @aemerson wrote:

In D93423#2459004, @aditya_nandakumar wrote:

If slot indexes are preserved and used in other passes that use CSE, do you think the compile time impact is amortized/minimized?

It's possible it would help a bit. I think the localizer may also benefit from this. I don't see it making a big difference either way though in most code.

In our out of tree backend, CSE is used and preserved for 6 passes in total. I suspect if slot indexes are also preserved, the overhead might not be too much. Hence I was curious if you actually collected some numbers. If only legalizer is being looked at for compile time impact, we're not really evaluating the compile time savings to be had in other passes (assuming amortized cost of slot index) right?

[aemerson]

In D93423#2459024, @aditya_nandakumar wrote:

In D93423#2459018, @aemerson wrote:

In D93423#2459004, @aditya_nandakumar wrote:

If slot indexes are preserved and used in other passes that use CSE, do you think the compile time impact is amortized/minimized?

It's possible it would help a bit. I think the localizer may also benefit from this. I don't see it making a big difference either way though in most code.

In our out of tree backend, CSE is used and preserved for 6 passes in total. I suspect if slot indexes are also preserved, the overhead might not be too much. Hence I was curious if you actually collected some numbers. If only legalizer is being looked at for compile time impact, we're not really evaluating the compile time savings to be had in other passes (assuming amortized cost of slot index) right?

In D93423#2459024, @aditya_nandakumar wrote:

In D93423#2459018, @aemerson wrote:

In D93423#2459004, @aditya_nandakumar wrote:

If slot indexes are preserved and used in other passes that use CSE, do you think the compile time impact is amortized/minimized?

It's possible it would help a bit. I think the localizer may also benefit from this. I don't see it making a big difference either way though in most code.

In our out of tree backend, CSE is used and preserved for 6 passes in total. I suspect if slot indexes are also preserved, the overhead might not be too much. Hence I was curious if you actually collected some numbers. If only legalizer is being looked at for compile time impact, we're not really evaluating the compile time savings to be had in other passes (assuming amortized cost of slot index) right?

In D93423#2459024, @aditya_nandakumar wrote:

In D93423#2459018, @aemerson wrote:

In D93423#2459004, @aditya_nandakumar wrote:

If slot indexes are preserved and used in other passes that use CSE, do you think the compile time impact is amortized/minimized?

It's possible it would help a bit. I think the localizer may also benefit from this. I don't see it making a big difference either way though in most code.

In our out of tree backend, CSE is used and preserved for 6 passes in total. I suspect if slot indexes are also preserved, the overhead might not be too much. Hence I was curious if you actually collected some numbers. If only legalizer is being looked at for compile time impact, we're not really evaluating the compile time savings to be had in other passes (assuming amortized cost of slot index) right?

Fair point. It might be quite difficult to ensure every pass preserves it but I'll see what I can do.

[aemerson]

This is superseded by D94264

llvm/include/llvm/CodeGen/GlobalISel/Legalizer.h

 /// instruction.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CODEGEN_GLOBALISEL_LEGALIZEMACHINEIRPASS_H
 #define LLVM_CODEGEN_GLOBALISEL_LEGALIZEMACHINEIRPASS_H
 
 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
+#include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 
 namespace llvm {
 
 class MachineRegisterInfo;
 class LostDebugLocObserver;
 
 class Legalizer : public MachineFunctionPass {
 public:
   static char ID;
 
   struct MFResult {
     bool Changed;
     const MachineInstr *FailedOn;
   };
 
 private:
   /// Initialize the field members using \p MF.
   void init(MachineFunction &MF);
 
+  SlotIndexes *Indexes;
+
 public:
   // Ctor, nothing fancy.
   Legalizer();
 
   StringRef getPassName() const override { return "Legalizer"; }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 

llvm/include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h

 #ifndef LLVM_CODEGEN_GLOBALISEL_MACHINEIRBUILDER_H
 #define LLVM_CODEGEN_GLOBALISEL_MACHINEIRBUILDER_H
 
 #include "llvm/CodeGen/GlobalISel/CSEInfo.h"
 #include "llvm/CodeGen/LowLevelType.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/SlotIndexes.h"
 #include "llvm/CodeGen/TargetOpcodes.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DebugLoc.h"
 #include "llvm/IR/Module.h"
 
 namespace llvm {
 
 // Forward declarations.
struct MachineIRBuilderState {
   /// @{
   MachineBasicBlock *MBB = nullptr;
   MachineBasicBlock::iterator II;
   /// @}
 
   GISelChangeObserver *Observer = nullptr;
 
   GISelCSEInfo *CSEInfo = nullptr;
+
+  SlotIndexes *Indexes = nullptr;
 };
 
 class DstOp {
   union {
     LLT LLTTy;
     Register Reg;
     const TargetRegisterClass *RC;
   };
public:
   MachineBasicBlock &getMBB() {
     return const_cast<MachineBasicBlock &>(
         const_cast<const MachineIRBuilder *>(this)->getMBB());
   }
 
   GISelCSEInfo *getCSEInfo() { return State.CSEInfo; }
   const GISelCSEInfo *getCSEInfo() const { return State.CSEInfo; }
 
+  SlotIndexes *getSlotIndexes() { return State.Indexes; }
+  const SlotIndexes *getSlotIndexes() const { return State.Indexes; }
+
   /// Current insertion point for new instructions.
   MachineBasicBlock::iterator getInsertPt() { return State.II; }
 
   /// Set the insertion point before the specified position.
   /// \pre MBB must be in getMF().
   /// \pre II must be a valid iterator in MBB.
   void setInsertPt(MachineBasicBlock &MBB, MachineBasicBlock::iterator II) {
     assert(MBB.getParent() == &getMF() &&
            "Basic block is in a different function");
     State.MBB = &MBB;
     State.II = II;
   }
 
   /// @}
 
   void setCSEInfo(GISelCSEInfo *Info) { State.CSEInfo = Info; }
 
+  void setSlotIndexes(SlotIndexes *indexes) { State.Indexes = indexes; }
+
   /// \name Setters for the insertion point.
   /// @{
   /// Set the MachineFunction where to build instructions.
   void setMF(MachineFunction &MF);
 
   /// Set the insertion point to the  end of \p MBB.
   /// \pre \p MBB must be contained by getMF().
   void setMBB(MachineBasicBlock &MBB) {
public:
   /// Build and insert <empty> = \p Opcode <empty>.
   /// The insertion point is the one set by the last call of either
   /// setBasicBlock or setMI.
   ///
   /// \pre setBasicBlock or setMI must have been called.
   ///
   /// \return a MachineInstrBuilder for the newly created instruction.
   MachineInstrBuilder buildInstr(unsigned Opcode) {
-    return insertInstr(buildInstrNoInsert(Opcode));
+    auto MIB = insertInstr(buildInstrNoInsert(Opcode));
+    if (State.Indexes) {
+      // We need to repair the range around the newly created instruction.
+      auto Begin = MIB->getIterator();
+      auto End = std::next(Begin);
+      State.Indexes->repairIndexesInRange(&getMBB(), Begin, End);
+    }
+    return MIB;
   }
 
   /// Build but don't insert <empty> = \p Opcode <empty>.
   ///
   /// \pre setMF, setBasicBlock or setMI  must have been called.
   ///
   /// \return a MachineInstrBuilder for the newly created instruction.
   MachineInstrBuilder buildInstrNoInsert(unsigned Opcode);

llvm/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp

 //===-- llvm/CodeGen/GlobalISel/CSEMIRBuilder.cpp - MIBuilder--*- C++ -*-==//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 /// \file
 /// This file implements the CSEMIRBuilder class which CSEs as it builds
 /// instructions.
 //===----------------------------------------------------------------------===//
 //
 
 #include "llvm/CodeGen/GlobalISel/CSEMIRBuilder.h"
 #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
+#include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/IR/DebugInfoMetadata.h"
 
 using namespace llvm;
 
 bool CSEMIRBuilder::dominates(MachineBasicBlock::const_iterator A,
                               MachineBasicBlock::const_iterator B) const {
   auto MBBEnd = getMBB().end();
   if (B == MBBEnd)
     return true;
   assert(A->getParent() == B->getParent() &&
          "Iterators should be in same block");
+
+  const SlotIndexes *Indexes = getSlotIndexes();
+  if (Indexes) {
+    SlotIndex SlotA = Indexes->getInstructionIndex(*A);
+    SlotIndex SlotB = Indexes->getInstructionIndex(*B);
+    return SlotIndex::isEarlierInstr(SlotA, SlotB);
+  }
   const MachineBasicBlock *BBA = A->getParent();
   MachineBasicBlock::const_iterator I = BBA->begin();
   for (; &*I != A && &*I != B; ++I)
     ;
   return &*I == A;
 }
 
 MachineInstrBuilder
 CSEMIRBuilder::getDominatingInstrForID(FoldingSetNodeID &ID,
                                        void *&NodeInsertPos) {
   GISelCSEInfo *CSEInfo = getCSEInfo();
   assert(CSEInfo && "Can't get here without setting CSEInfo");
   MachineBasicBlock *CurMBB = &getMBB();
   MachineInstr *MI =
       CSEInfo->getMachineInstrIfExists(ID, CurMBB, NodeInsertPos);
   if (MI) {
     CSEInfo->countOpcodeHit(MI->getOpcode());
     auto CurrPos = getInsertPt();
     auto MII = MachineBasicBlock::iterator(MI);
     if (MII == CurrPos) {
       // Move the insert point ahead of the instruction so any future uses of
       // this builder will have the def ready.
       setInsertPt(*CurMBB, std::next(MII));
     } else if (!dominates(MI, CurrPos)) {
+      ++MII;
       CurMBB->splice(CurrPos, CurMBB, MI);
+      auto *SlotIndexes = getSlotIndexes();
+      if (SlotIndexes) {
+        getSlotIndexes()->removeSingleMachineInstrFromMaps(*MI);
+        // Repair slot indices for the modified range.
+        getSlotIndexes()->repairIndexesInRange(
+            CurMBB, MachineBasicBlock::iterator(MI), MII);
+      }
     }
     return MachineInstrBuilder(getMF(), MI);
   }
   return MachineInstrBuilder();
 }
 
 bool CSEMIRBuilder::canPerformCSEForOpc(unsigned Opc) const {
   const GISelCSEInfo *CSEInfo = getCSEInfo();

llvm/lib/CodeGen/GlobalISel/Legalizer.cpp

 #include "llvm/CodeGen/GlobalISel/CSEInfo.h"
 #include "llvm/CodeGen/GlobalISel/CSEMIRBuilder.h"
 #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
 #include "llvm/CodeGen/GlobalISel/GISelWorkList.h"
 #include "llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
 #include "llvm/CodeGen/GlobalISel/LegalizerHelper.h"
 #include "llvm/CodeGen/GlobalISel/LostDebugLocObserver.h"
 #include "llvm/CodeGen/GlobalISel/Utils.h"
+#include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/SlotIndexes.h"
 #include "llvm/CodeGen/TargetPassConfig.h"
 #include "llvm/CodeGen/TargetSubtargetInfo.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Target/TargetMachine.h"
 
 #include <iterator>

 #endif
 
 char Legalizer::ID = 0;
 INITIALIZE_PASS_BEGIN(Legalizer, DEBUG_TYPE,
                       "Legalize the Machine IR a function's Machine IR", false,
                       false)
 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
 INITIALIZE_PASS_DEPENDENCY(GISelCSEAnalysisWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
 INITIALIZE_PASS_END(Legalizer, DEBUG_TYPE,
                     "Legalize the Machine IR a function's Machine IR", false,
                     false)
 
 Legalizer::Legalizer() : MachineFunctionPass(ID) { }
 
 void Legalizer::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<TargetPassConfig>();
   AU.addRequired<GISelCSEAnalysisWrapperPass>();
   AU.addPreserved<GISelCSEAnalysisWrapperPass>();
+  AU.addRequiredTransitive<SlotIndexes>();
   getSelectionDAGFallbackAnalysisUsage(AU);
   MachineFunctionPass::getAnalysisUsage(AU);
 }
 
 void Legalizer::init(MachineFunction &MF) {
 }
 
 static bool isArtifact(const MachineInstr &MI) {
public:
 
   void changedInstr(MachineInstr &MI) override {
     // When insts change, we want to revisit them to legalize them again.
     // We'll consider them the same as created.
     LLVM_DEBUG(dbgs() << ".. .. Changed MI: " << MI);
     createdOrChangedInstr(MI);
   }
 };
+
+class SlotIndexDeletionObserver : public GISelChangeObserver {
+  SlotIndexes *Indexes;
+
+public:
+  SlotIndexDeletionObserver(SlotIndexes *indexes) : Indexes(indexes) {}
+
+  void erasingInstr(MachineInstr &MI) override {
+    LLVM_DEBUG(dbgs() << "Removing MI: " << MI << " from SlotIndexes");
+    Indexes->removeSingleMachineInstrFromMaps(MI);
+  }
+  void createdInstr(MachineInstr &MI) override {}
+  void changingInstr(MachineInstr &MI) override {}
+  void changedInstr(MachineInstr &MI) override {}
+};
 } // namespace
 
 Legalizer::MFResult
 Legalizer::legalizeMachineFunction(MachineFunction &MF, const LegalizerInfo &LI,
                                    ArrayRef<GISelChangeObserver *> AuxObservers,
                                    LostDebugLocObserver &LocObserver,
                                    MachineIRBuilder &MIRBuilder) {
   MIRBuilder.setMF(MF);
bool Legalizer::runOnMachineFunction(MachineFunction &MF) {
   if (MF.getProperties().hasProperty(
           MachineFunctionProperties::Property::FailedISel))
     return false;
   LLVM_DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n');
   init(MF);
   const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
   GISelCSEAnalysisWrapper &Wrapper =
       getAnalysis<GISelCSEAnalysisWrapperPass>().getCSEWrapper();
+  Indexes = &getAnalysis<SlotIndexes>();
   MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
 
   const size_t NumBlocks = MF.size();
 
   std::unique_ptr<MachineIRBuilder> MIRBuilder;
   GISelCSEInfo *CSEInfo = nullptr;
   bool EnableCSE = EnableCSEInLegalizer.getNumOccurrences()
                        ? EnableCSEInLegalizer
                        : TPC.isGISelCSEEnabled();
   if (EnableCSE) {
     MIRBuilder = std::make_unique<CSEMIRBuilder>();
     CSEInfo = &Wrapper.get(TPC.getCSEConfig());
     MIRBuilder->setCSEInfo(CSEInfo);
   } else
     MIRBuilder = std::make_unique<MachineIRBuilder>();
 
+  MIRBuilder->setSlotIndexes(Indexes);
   SmallVector<GISelChangeObserver *, 1> AuxObservers;
   if (EnableCSE && CSEInfo) {
     // We want CSEInfo in addition to WorkListObserver to observe all changes.
     AuxObservers.push_back(CSEInfo);
   }
+  SlotIndexDeletionObserver SIObserver(Indexes);
+  AuxObservers.push_back(&SIObserver);
   assert(!CSEInfo || !errorToBool(CSEInfo->verify()));
   LostDebugLocObserver LocObserver(DEBUG_TYPE);
   if (VerifyDebugLocs > DebugLocVerifyLevel::None)
     AuxObservers.push_back(&LocObserver);
 
   const LegalizerInfo &LI = *MF.getSubtarget().getLegalizerInfo();
   MFResult Result =
       legalizeMachineFunction(MF, LI, AuxObservers, LocObserver, *MIRBuilder);