[GlobalISel]: Fix some non determinism exposed in CSE due to not notifying observers about mutations + add verification for CSE

[aditya_nandakumar]

Summary

While investigating some non determinism (CSE doesn't produce wrong code, it just doesn't CSE some times) in GISel CSE on an out of tree target, I realized that the core issue was that there were lots of code that mutates (setReg, setRegClass etc), but doesn't notify observers (CSE in this case but this could be any other observer). In order to make the Observer be available in various parts of code and to avoid having to thread it through various API, the MachineFunction now has the observer as field. This allows it to be easily used in helper functions such as constrainOperandRegClass. One of the other option I considered was to have some sort of unique_ptr<GISelContext> GISelCtxt and move the various GISel related properties into this as well but for now I didn't do this.

Also added some invariant verification method in CSEInfo which can catch these issues (when CSE is enabled). Right now it's at the end the legalizer and a few tests in AArch64,AMDGPU,X86 fail. I haven't fixed these yet, but will get to them hopefully this week while we get some eyes on this patch. Also it's not clear to me if this should be always run at the end of each pass (where CSE is enabled in DEBUG?)?

One of the options considered was to automatically track mutations but this is very invasive and the overhead is likely a lot.

[paquette]

llvm/lib/CodeGen/GlobalISel/Legalizer.cpp

329–330

Should this be under #ifndef NDEBUG?

[aditya_nandakumar]

llvm/lib/CodeGen/GlobalISel/Legalizer.cpp

329–330

Definitely. Thanks for catching.

[qcolombet]

llvm/lib/CodeGen/GlobalISel/Legalizer.cpp

329–330

I would rather have verify returns a bool and do:
assert(!CSEInfo || CSEInfo->Info());

[dsanders]

LGTM with the changes Jessica and Quentin mentioned (or the XRay style Error verify() version).

llvm/include/llvm/CodeGen/GlobalISel/GISelChangeObserver.h

104

It predates this patch but the reference to CSEInfo here is inaccurate. That's only one usage of the delegate mechanism.

llvm/lib/CodeGen/GlobalISel/IRTranslator.cpp

2383–2385

Is there ever a time when we want to do one of these and not the other? As far as I can see, installing the observer is always coupled with installing the delegate

llvm/lib/CodeGen/GlobalISel/Legalizer.cpp

329–330

I would rather have verify returns a bool and do:
assert(!CSEInfo || CSEInfo->Info());

Offline, I commented to Aditya that the precedent was for verify() functions that return void and abort on failure but I do agree with this.

That said, I would like to point out that there's another possibility of returning an Error object like in XRay's BlockVerifier.h. That style has the benefit of being able to report exactly what's wrong and potentially annotate the state dump with indications as to which bit is invalid/stale.

[aemerson]

Ping. Can we combine the delegate and observer installers?

[aditya_nandakumar]

In D67133#1677499, @aemerson wrote:

Ping. Can we combine the delegate and observer installers?

Thanks Amara for the feedback. The reason I haven't responded here (or committed this) is that I haven't had the chance to track and fix the issues in the various backends where this fails (probably missing Observer calls). Maybe for now, I will disable the verification by default and get this patch in, and we can work on enabling it by default in a follow up patch?

[aemerson]

In D67133#1679497, @aditya_nandakumar wrote:

In D67133#1677499, @aemerson wrote:

Ping. Can we combine the delegate and observer installers?

Thanks Amara for the feedback. The reason I haven't responded here (or committed this) is that I haven't had the chance to track and fix the issues in the various backends where this fails (probably missing Observer calls). Maybe for now, I will disable the verification by default and get this patch in, and we can work on enabling it by default in a follow up patch?

Either way is fine for me, it can wait until the bugs are found.

[aditya_nandakumar]

Updated based on feedback.
CSEInfo::verify now returns Error which we can assert.

[aditya_nandakumar]

I'll go ahead and get this in (as it already received a LGTM before) - just posted an updated patch since it's been a while since received updates.

[aditya_nandakumar]

Committed in b91d9ec0bb8

llvm/include/llvm/CodeGen/GlobalISel/CSEInfo.h

 
 public:
   GISelCSEInfo() = default;
 
   virtual ~GISelCSEInfo();
 
   void setMF(MachineFunction &MF);
 
+  Error verify();
+
   /// Records a newly created inst in a list and lazily insert it to the CSEMap.
   /// Sometimes, this method might be called with a partially constructed
   /// MachineInstr,
   //  (right after BuildMI without adding any operands) - and in such cases,
   //  defer the hashing of the instruction to a later stage.
   void recordNewInstruction(MachineInstr *MI);
 
   /// Use this callback to inform CSE about a newly fully created instruction.

llvm/include/llvm/CodeGen/GlobalISel/GISelChangeObserver.h

void changedInstr(MachineInstr &MI) override {
     for (auto &O : Observers)
       O->changedInstr(MI);
   }
   // API for MachineFunction::Delegate
   void MF_HandleInsertion(MachineInstr &MI) override { createdInstr(MI); }
   void MF_HandleRemoval(MachineInstr &MI) override { erasingInstr(MI); }
 };
 
-/// A simple RAII based CSEInfo installer.
+/// A simple RAII based Delegate installer.
 /// Use this in a scope to install a delegate to the MachineFunction and reset
 /// it at the end of the scope.
 class RAIIDelegateInstaller {
   MachineFunction &MF;
   MachineFunction::Delegate *Delegate;
 
 public:
   RAIIDelegateInstaller(MachineFunction &MF, MachineFunction::Delegate *Del);
   ~RAIIDelegateInstaller();
 };
 
+/// A simple RAII based Observer installer.
+/// Use this in a scope to install the Observer to the MachineFunction and reset
+/// it at the end of the scope.
+class RAIIMFObserverInstaller {
+  MachineFunction &MF;
+
+public:
+  RAIIMFObserverInstaller(MachineFunction &MF, GISelChangeObserver &Observer);
+  ~RAIIMFObserverInstaller();
+};
+
+/// Class to install both of the above.
+class RAIIMFObsDelInstaller {
+  RAIIDelegateInstaller DelI;
+  RAIIMFObserverInstaller ObsI;
+
+public:
+  RAIIMFObsDelInstaller(MachineFunction &MF, GISelObserverWrapper &Wrapper)
+      : DelI(MF, &Wrapper), ObsI(MF, Wrapper) {}
+  ~RAIIMFObsDelInstaller() = default;
+};
+
 } // namespace llvm
 #endif

llvm/include/llvm/CodeGen/MachineFunction.h

 class Pass;
 class PseudoSourceValueManager;
 class raw_ostream;
 class SlotIndexes;
 class TargetRegisterClass;
 class TargetSubtargetInfo;
 struct WasmEHFuncInfo;
 struct WinEHFuncInfo;
+class GISelChangeObserver;
 
 template <> struct ilist_alloc_traits<MachineBasicBlock> {
   void deleteNode(MachineBasicBlock *MBB);
 };
 
 template <> struct ilist_callback_traits<MachineBasicBlock> {
   void addNodeToList(MachineBasicBlock* N);
   void removeNodeFromList(MachineBasicBlock* N);
struct ArgRegPair {
     }
   };
   /// Vector of call argument and its forwarding register.
   using CallSiteInfo = SmallVector<ArgRegPair, 1>;
   using CallSiteInfoImpl = SmallVectorImpl<ArgRegPair>;
 
 private:
   Delegate *TheDelegate = nullptr;
+  GISelChangeObserver *Observer = nullptr;
 
   using CallSiteInfoMap = DenseMap<const MachineInstr *, CallSiteInfo>;
   /// Map a call instruction to call site arguments forwarding info.
   CallSiteInfoMap CallSitesInfo;
 
   /// A helper function that returns call site info for a give call
   /// instruction if debug entry value support is enabled.
   CallSiteInfoMap::iterator getCallSiteInfo(const MachineInstr *MI);
public:
   void setDelegate(Delegate *delegate) {
     assert(delegate && !TheDelegate &&
            "Attempted to set delegate to null, or to change it without "
            "first resetting it!");
 
     TheDelegate = delegate;
   }
 
+  void setObserver(GISelChangeObserver *O) { Observer = O; }
+
+  GISelChangeObserver *getObserver() const { return Observer; }
+
   MachineModuleInfo &getMMI() const { return MMI; }
   MCContext &getContext() const { return Ctx; }
 
   PseudoSourceValueManager &getPSVManager() const { return *PSVManager; }
 
   /// Return the DataLayout attached to the Module associated to this MF.
   const DataLayout &getDataLayout() const;
 

llvm/lib/CodeGen/GlobalISel/CSEInfo.cpp

void GISelCSEInfo::releaseMemory() {
   CSEOpt.reset();
   MRI = nullptr;
   MF = nullptr;
 #ifndef NDEBUG
   OpcodeHitTable.clear();
 #endif
 }
 
+Error GISelCSEInfo::verify() {
+#ifndef NDEBUG
+  handleRecordedInsts();
+  // For each instruction in map from MI -> UMI,
+  // Profile(MI) and make sure UMI is found for that profile.
+  for (auto &It : InstrMapping) {
+    FoldingSetNodeID TmpID;
+    GISelInstProfileBuilder(TmpID, *MRI).addNodeID(It.first);
+    void *InsertPos;
+    UniqueMachineInstr *FoundNode =
+        CSEMap.FindNodeOrInsertPos(TmpID, InsertPos);
+    if (FoundNode != It.second)
+      return createStringError(std::make_error_code(std::errc::not_supported),
+                               "CSEMap mismatch, InstrMapping has MIs without "
+                               "corresponding Nodes in CSEMap");
+  }
+
+  // For every node in the CSEMap, make sure that the InstrMapping
+  // points to it.
+  for (auto It = CSEMap.begin(), End = CSEMap.end(); It != End; ++It) {
+    const UniqueMachineInstr &UMI = *It;
+    if (!InstrMapping.count(UMI.MI))
+      return createStringError(std::make_error_code(std::errc::not_supported),
+                               "Node in CSE without InstrMapping", UMI.MI);
+
+    if (InstrMapping[UMI.MI] != &UMI)
+      return createStringError(std::make_error_code(std::errc::not_supported),
+                               "Mismatch in CSE mapping");
+  }
+#endif
+  return Error::success();
+}
+
 void GISelCSEInfo::print() {
   LLVM_DEBUG(for (auto &It
                   : OpcodeHitTable) {
     dbgs() << "CSEInfo::CSE Hit for Opc " << It.first << " : " << It.second
            << "\n";
   };);
 }
 /// -----------------------------------------
const GISelInstProfileBuilder &GISelInstProfileBuilder::addNodeIDMachineOperand(
   // Handle other types
   return *this;
 }
 
 GISelCSEInfo &
 GISelCSEAnalysisWrapper::get(std::unique_ptr<CSEConfigBase> CSEOpt,
                              bool Recompute) {
   if (!AlreadyComputed || Recompute) {
+    Info.releaseMemory();
     Info.setCSEConfig(std::move(CSEOpt));
     Info.analyze(*MF);
     AlreadyComputed = true;
   }
   return Info;
 }
 void GISelCSEAnalysisWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
   MachineFunctionPass::getAnalysisUsage(AU);
 }
 
 bool GISelCSEAnalysisWrapperPass::runOnMachineFunction(MachineFunction &MF) {
   releaseMemory();
   Wrapper.setMF(MF);
   return false;
 }

llvm/lib/CodeGen/GlobalISel/GISelChangeObserver.cpp

RAIIDelegateInstaller::RAIIDelegateInstaller(MachineFunction &MF,
                                              MachineFunction::Delegate *Del)
     : MF(MF), Delegate(Del) {
   // Register this as the delegate for handling insertions and deletions of
   // instructions.
   MF.setDelegate(Del);
 }
 
 RAIIDelegateInstaller::~RAIIDelegateInstaller() { MF.resetDelegate(Delegate); }
+
+RAIIMFObserverInstaller::RAIIMFObserverInstaller(MachineFunction &MF,
+                                                 GISelChangeObserver &Observer)
+    : MF(MF) {
+  MF.setObserver(&Observer);
+}
+
+RAIIMFObserverInstaller::~RAIIMFObserverInstaller() { MF.setObserver(nullptr); }

llvm/lib/CodeGen/GlobalISel/IRTranslator.cpp

bool IRTranslator::runOnMachineFunction(MachineFunction &CurMF) {
   if (EnableCSE && CSEInfo)
     WrapperObserver.addObserver(CSEInfo);
   {
     ReversePostOrderTraversal<const Function *> RPOT(&F);
 #ifndef NDEBUG
     DILocationVerifier Verifier;
     WrapperObserver.addObserver(&Verifier);
 #endif // ifndef NDEBUG
     RAIIDelegateInstaller DelInstall(*MF, &WrapperObserver);
+    RAIIMFObserverInstaller ObsInstall(*MF, WrapperObserver);
     for (const BasicBlock *BB : RPOT) {
       MachineBasicBlock &MBB = getMBB(*BB);
       // Set the insertion point of all the following translations to
       // the end of this basic block.
       CurBuilder->setMBB(MBB);
       HasTailCall = false;
       for (const Instruction &Inst : *BB) {
         // If we translated a tail call in the last step, then we know
         // everything after the call is either a return, or something that is

llvm/lib/CodeGen/GlobalISel/Legalizer.cpp

 #include "llvm/CodeGen/GlobalISel/LegalizerHelper.h"
 #include "llvm/CodeGen/GlobalISel/Utils.h"
 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
 #include "llvm/CodeGen/MachineRegisterInfo.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>
 
 #define DEBUG_TYPE "legalizer"
 
 using namespace llvm;
 
Legalizer::legalizeMachineFunction(MachineFunction &MF, const LegalizerInfo &LI,
   // We want both WorkListObserver as well as all the auxiliary observers (e.g.
   // CSEInfo) to observe all changes. Use the wrapper observer.
   GISelObserverWrapper WrapperObserver(&WorkListObserver);
   for (GISelChangeObserver *Observer : AuxObservers)
     WrapperObserver.addObserver(Observer);
 
   // Now install the observer as the delegate to MF.
   // This will keep all the observers notified about new insertions/deletions.
-  RAIIDelegateInstaller DelInstall(MF, &WrapperObserver);
+  RAIIMFObsDelInstaller Installer(MF, WrapperObserver);
   LegalizerHelper Helper(MF, LI, WrapperObserver, MIRBuilder);
   LegalizationArtifactCombiner ArtCombiner(MIRBuilder, MRI, LI);
   auto RemoveDeadInstFromLists = [&WrapperObserver](MachineInstr *DeadMI) {
     WrapperObserver.erasingInstr(*DeadMI);
   };
   bool Changed = false;
   SmallVector<MachineInstr *, 128> RetryList;
   do {
bool Legalizer::runOnMachineFunction(MachineFunction &MF) {
   } else
     MIRBuilder = std::make_unique<MachineIRBuilder>();
 
   SmallVector<GISelChangeObserver *, 1> AuxObservers;
   if (EnableCSE && CSEInfo) {
     // We want CSEInfo in addition to WorkListObserver to observe all changes.
     AuxObservers.push_back(CSEInfo);
   }
+  assert(!CSEInfo || !errorToBool(CSEInfo->verify()));
 
   const LegalizerInfo &LI = *MF.getSubtarget().getLegalizerInfo();
   MFResult Result = legalizeMachineFunction(MF, LI, AuxObservers, *MIRBuilder);
 
   if (Result.FailedOn) {
     reportGISelFailure(MF, TPC, MORE, "gisel-legalize",
                        "unable to legalize instruction", *Result.FailedOn);
     return false;
   }
   // For now don't support if new blocks are inserted - we would need to fix the
   // outer loop for that.
   if (MF.size() != NumBlocks) {
     MachineOptimizationRemarkMissed R("gisel-legalize", "GISelFailure",
                                       MF.getFunction().getSubprogram(),
                                       /*MBB=*/nullptr);
     R << "inserting blocks is not supported yet";
     reportGISelFailure(MF, TPC, MORE, R);
     return false;
   }
+  // If for some reason CSE was not enabled, make sure that we invalidate the
+  // CSEInfo object (as we currently declare that the analysis is preserved).
+  // The next time get on the wrapper is called, it will force it to recompute
+  // the analysis.
+  if (!EnableCSE)
+    Wrapper.setComputed(false);
   return Result.Changed;
 }

llvm/lib/CodeGen/GlobalISel/Utils.cpp

 //===- llvm/CodeGen/GlobalISel/Utils.cpp -------------------------*- 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 utility functions used by the GlobalISel
 /// pipeline.
 //===----------------------------------------------------------------------===//
 
 #include "llvm/CodeGen/GlobalISel/Utils.h"
 #include "llvm/ADT/APFloat.h"
 #include "llvm/ADT/Twine.h"
+#include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
 #include "llvm/CodeGen/GlobalISel/RegisterBankInfo.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/StackProtector.h"
 #include "llvm/CodeGen/TargetInstrInfo.h"
 #include "llvm/CodeGen/TargetPassConfig.h"
if (RegMO.isUse()) {
               TII.get(TargetOpcode::COPY), ConstrainedReg)
           .addReg(Reg);
     } else {
       assert(RegMO.isDef() && "Must be a definition");
       BuildMI(MBB, std::next(InsertIt), InsertPt.getDebugLoc(),
               TII.get(TargetOpcode::COPY), Reg)
           .addReg(ConstrainedReg);
     }
+  } else {
+    if (GISelChangeObserver *Observer = MF.getObserver()) {
+      if (!RegMO.isDef()) {
+        MachineInstr *RegDef = MRI.getVRegDef(Reg);
+        Observer->changedInstr(*RegDef);
+      }
+      Observer->changingAllUsesOfReg(MRI, Reg);
+      Observer->finishedChangingAllUsesOfReg();
+    }
   }
   return ConstrainedReg;
 }
 
 Register llvm::constrainOperandRegClass(
     const MachineFunction &MF, const TargetRegisterInfo &TRI,
     MachineRegisterInfo &MRI, const TargetInstrInfo &TII,
     const RegisterBankInfo &RBI, MachineInstr &InsertPt, const MCInstrDesc &II,