[globalisel] Add lost debug locations verifier

[dsanders]

Summary

This verifier tries to ensure that DebugLoc's don't just disappear as
we transform the MIR. It observes the instructions created, erased, and
changed and at checkpoints chosen by the client algorithm verifies the
locations affected by those changes.

In particular, it verifies that:

• Every DebugLoc for an erased/changing instruction is still present on at least one new/changed instruction
• Failing that, that there is a line-0 location in the new/changed instructions. It's not possible to confirm which locations were merged so it conservatively assumes all unaccounted for locations are accounted for by any line-0 location to avoid false positives.

If that fails, it prints the lost locations in the debug output along with
the instructions that should have accounted for them.

In theory, this is usable by the legalizer, combiner, selector and any other
pass that performs incremental changes to the MIR. However, it has so far
only really been tested on the legalizer (not including the artifact
combiner) where it has caught lots of lost locations, particularly in Custom
legalizations. The tests in this patch are those the verifier detected a problem in after applying it to all the .mir tests for AArch64 and AMDGPU.

Depends on D77575, D77446

[dsanders]

llvm/lib/CodeGen/GlobalISel/Legalizer.cpp

169

The addition of this argument is rather unfortunate given the AuxObservers list. The reason is the LocObserver needs to be more tightly integrated into the algorithm than most observers. The fewer changes that are made between checkpoints, the more accurately it can detect lossage, particularly given the conservative behaviour for line-0 locations.

In the end I settled on a separate argument over finding the observer within the AuxObservers list as we currently don't have isa/dyn_cast support in observers

[paquette]

llvm/lib/CodeGen/GlobalISel/Legalizer.cpp

369

Can this use NV?

E.g. something like

R << "lost " << NV("NumLostDebugLocs", LocObserver.getNumLostDebugLocs()) << " debug locations during pass";

I think that would make optimization records easier to parse, if you choose to save them.

It would also be nice to have a testcase for the remarks.

[arsenm]

llvm/include/llvm/CodeGen/GlobalISel/LostDebugLocObserver.h

2

Missing C++ mode comment

37–40

Defined to no-op calls in debug build?

llvm/lib/CodeGen/GlobalISel/Legalizer.cpp

64

Missing static const?

370

Missing newline?

llvm/test/CodeGen/AMDGPU/GlobalISel/legalize-fdiv.mir

3 ↗

(On Diff #255416)

Do we really need to double the number of run lines in every test?

[paquette]

llvm/lib/CodeGen/GlobalISel/Legalizer.cpp

369

Although that being said, any testcase that exposes this is a bug we should fix, so... maybe it's not reasonable to test it. :)

It would be nice to know what the opt remark output looks like though.

[vsk]

llvm/test/CodeGen/AMDGPU/GlobalISel/legalize-fdiv.mir

3 ↗

(On Diff #255416)

There are some alternatives:

• Get rid of the non-mir debugify check lines. This is fine by me, but some pass authors might not like this.
• Run the tests with llvm-lit -Dopt='opt -debugify -Dllc='llc -run-pass=mir-debugify'`. That means only a subset of users/bots are test with debug info.

[dsanders]

llvm/include/llvm/CodeGen/GlobalISel/LostDebugLocObserver.h

37–40

I assume you mean the non-debug build.

I suppose we could do as there's a small code-size saving from it. It shouldn't affect execution time though as we just decline to install the observer for that case

llvm/lib/CodeGen/GlobalISel/Legalizer.cpp

369

Can this use NV?

I didn't know about NV. Fixed in my working copy

It would also be nice to have a testcase for the remarks.

A test case is tricky because as you say, we should fix all the cases where this actually happens.

It would be nice to know what the opt remark output looks like though.

I'll add an example in a comment

370

As far as I know, it's not needed for remarks. The other two above don't have a newline at least

llvm/test/CodeGen/AMDGPU/GlobalISel/legalize-fdiv.mir

3 ↗

(On Diff #255416)

Do we really need to double the number of run lines in every test?

I kept it to the ones that actually reveal something but I agree it's not great to have the extra run lines. Not least because they don't actually do anything different to the main ones on non-asserts builds because the LostDebugLocObserver doesn't get installed. For that build, they're just wasting time.

I want to end up at a -verify-mir-debug-locations similar to -verify-machineinstrs (however that spelling is a bit misleading because each pass must cooperate to verify anything) or -mir-debugify-before-all -mir-strip-debug-after-all or something along those lines. At that point injecting the options via lit makes a lot of sense.

[dsanders]

C++ mode comment
Use ore::NV
Fix build errors in legalizer unit test

[dsanders]

Removed test changes, now covered by llvm-lit -Dllc='llc --debugify-and-strip-all-safe --debugify-level=locations'

[vsk]

llvm/lib/CodeGen/GlobalISel/LostDebugLocObserver.cpp

44

Why not delete HasUnseenLineZeroLoc and return early here?

84

Please have this return early, ideally like 'if (MI.isConstant()) return;'

I don't mean to suggest that you make tangential changes, it's just that it seems like there's a need for such a predicate (e.g. https://llvm.org/doxygen/AMDGPUInstructionSelector_8cpp_source.html#l01470 defines isConstant for MIs but leaves out G_FCONSTANT).

92

Ditto.

[dsanders]

Add missing opcodes that never have locations
Predicate
Early returns

llvm/lib/CodeGen/GlobalISel/LostDebugLocObserver.cpp

84

I looked at this again and found I'd missed G_IMPLICIT_DEF and G_GLOBAL_VALUE which also have their debug locations removed by the IRTranslator to avoid 'jumpy' behaviour in the debugger. I've added a predicate so we don't have two copies of the code in this file but it's not really meaningful for other code.

[vsk]

I think this is in good shape overall, but I'll defer to someone with more GISel experience to lgtm this patch.

llvm/include/llvm/CodeGen/GlobalISel/LostDebugLocObserver.h

29

Can analyzeDebugLocations be private?

33

The checkpoint method could use some doxygen (when exactly should clients call it, and when should CheckDebugLocs be false)?

llvm/lib/CodeGen/GlobalISel/Legalizer.cpp

64

This is still missing.

[dsanders]

static const
Doxygen comment
Make a function private

[aprantl]

llvm/lib/CodeGen/GlobalISel/LostDebugLocObserver.cpp

2

Please don't put -*- C++ -*- markers into .cpp files, that's redundant. They are only needed for .h files, where it is ambiguous whether it's C or C++.

[paquette]

After you address @aprantl's comment, I think that this looks fine.

[qcolombet]

Hi Daniel,

What is the compile time impact of this change?

Is there a way to make the callers agnostic to the kind of observers we are dealing with?

Basically, I like the observer idea for checking the debug information, but I don't like that:

1. We have to add a bunch of checkpoint calls all over the place
2. We have to specifically carry this observer around instead of having it being with the other observers (AuxObservers argument)

Bottom line, it feels intrusive and if we have to do that everywhere I am afraid we won't be able to scale.

I am fine with moving forward with that patch for the time being, but I think we have to rethink our strategy long term.

Cheers,
-Quentin

[dsanders]

In D77576#1978914, @qcolombet wrote:

Hi Daniel,

What is the compile time impact of this change?

That depends on VerifyDebugLocs. When it's None (default for release), there shouldn't be a measurable impact as the observer doesn't get installed. I haven't measured it for Locations (current default for asserts) yet as I've been more focused on fixing the bugs it finds in our out-of-tree target so far. I don't expect it to be noticable as it's a fairly simple matcher on small search spaces but if it is we can change the default to None at the cost of needing to use an extra option in out llvm-lit -Dllc='llc ...' command.

Is there a way to make the callers agnostic to the kind of observers we are dealing with?

In general, not really as each observer implementation will have different requirements depending on what they're for. That said, two of the three observers so far wrap logical changes (transactions except we don't really have that concept) to the IR and the third just follows the events as they happen. So while we can't really solve it in general, we could add another event to observer interface. There's no guarantee we won't need something else in the future though that causes the observers to diverge again though.

Basically, I like the observer idea for checking the debug information, but I don't like that:

1. We have to add a bunch of checkpoint calls all over the place

There's not really any avoiding these calls. The verifier needs to check often to minimize the times it just gives up but not so often that it checks while the IR is expected to be in a broken state. Only the algorithm knows when it's safe to have the verifier check the locations. Maybe a transaction-complete style event is common enough that we can add it to the observer interface and leave it very vague as to what a transaction is.

2. We have to specifically carry this observer around instead of having it being with the other observers (AuxObservers argument)

FWIW, it's 'as well as it being with the other observers' but that makes no real difference to your point. I dislike this too both because AuxObservers is trying to force common behaviour where it doesn't really exist but also because if it's going to be there then there shouldn't need to be separate arguments as well. It's possible to fix this but only if we design the observer interface to suit the observers that exist today rather than what they are in principle.

[dsanders]

One more last-minute fix: If there was a line-0 location in the input
and the output it was matching them up. If another location folded
into that line-0 location it would falsely be considered lost despite
being handled correctly because the code to treat line-0 locations
as covering everything was not reached.

[dsanders]

In D77576#1979013, @dsanders wrote:

In D77576#1978914, @qcolombet wrote:

Hi Daniel,

What is the compile time impact of this change?

That depends on VerifyDebugLocs. When it's None (default for release), there shouldn't be a measurable impact as the observer doesn't get installed. I haven't measured it for Locations (current default for asserts) yet as I've been more focused on fixing the bugs it finds in our out-of-tree target so far. I don't expect it to be noticable as it's a fairly simple matcher on small search spaces but if it is we can change the default to None at the cost of needing to use an extra option in out llvm-lit -Dllc='llc ...' command.

Running CTMark with -j20 (because I'm not looking at individual tests, just the rough total), I get:

• X86 -fglobal-isel -g: 3215s without this patch, 3209s with it
• X86 -fglobal-isel: 3133s without this patch, 3133s with it
• AArch64 -fglobal-isel -g: 3065s without this patch, 3053s with it
• AArch64 -fglobal-isel: 2972s without this patch, 2979s with it

So I'd say that leaving it on by default for asserts has no significant impact on compile time

I did run into an interesting issue in some other testing I was doing though. A verifier failure can cause GlobalISel to fall back on DAGISel when fallbacks are enabled, changing codegen. I'm going to have to tweak how failures are reported to fix that

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

 #define LLVM_CODEGEN_GLOBALISEL_LEGALIZEMACHINEIRPASS_H
 
 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.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;
public:
   bool combineExtracts(MachineInstr &MI, MachineRegisterInfo &MRI,
                        const TargetInstrInfo &TII);
 
   bool runOnMachineFunction(MachineFunction &MF) override;
 
   static MFResult
   legalizeMachineFunction(MachineFunction &MF, const LegalizerInfo &LI,
                           ArrayRef<GISelChangeObserver *> AuxObservers,
+                          LostDebugLocObserver &LocObserver,
                           MachineIRBuilder &MIRBuilder);
 };
 } // End namespace llvm.
 
 #endif

llvm/include/llvm/CodeGen/GlobalISel/LostDebugLocObserver.h

+//===----- llvm/CodeGen/GlobalISel/LostDebugLocObserver.h -------*- 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
+//
+//===----------------------------------------------------------------------===//
+//
+/// Tracks DebugLocs between checkpoints and verifies that they are transferred.
+//
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_CODEGEN_GLOBALISEL_LOSTDEBUGLOCOBSERVER_H
+#define LLVM_CODEGEN_GLOBALISEL_LOSTDEBUGLOCOBSERVER_H
+
+#include "llvm/ADT/SmallSet.h"
+#include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
+
+namespace llvm {
+class LostDebugLocObserver : public GISelChangeObserver {
+  StringRef DebugType;
+  SmallSet<DebugLoc, 4> LostDebugLocs;
+  SmallPtrSet<MachineInstr *, 4> PotentialMIsForDebugLocs;
+  unsigned NumLostDebugLocs = 0;
+
+public:
+  LostDebugLocObserver(StringRef DebugType) : DebugType(DebugType) {}
+
+  unsigned getNumLostDebugLocs() const { return NumLostDebugLocs; }
+
+  /// Call this to indicate that it's a good point to assess whether locations
+  /// have been lost. Typically this will be when a logical change has been
+  /// completed such as the caller has finished replacing some instructions with
+  /// alternatives. When CheckDebugLocs is true, the locations will be checked
+  /// to see if any have been lost since the last checkpoint. When
+  /// CheckDebugLocs is false, it will just reset ready for the next checkpoint
+  /// without checking anything. This can be helpful to limit the detection to
+  /// easy-to-fix portions of an algorithm before allowing more difficult ones.
+  void checkpoint(bool CheckDebugLocs = true);
+
+  void createdInstr(MachineInstr &MI) override;
+  void erasingInstr(MachineInstr &MI) override;
+  void changingInstr(MachineInstr &MI) override;
+  void changedInstr(MachineInstr &MI) override;
+
+private:
+  void analyzeDebugLocations();
+};
+
+} // namespace llvm
+#endif // ifndef LLVM_CODEGEN_GLOBALISEL_LOSTDEBUGLOCOBSERVER_H

llvm/lib/CodeGen/GlobalISel/CMakeLists.txt

add_llvm_component_library(LLVMGlobalISel
         InstructionSelect.cpp
         InstructionSelector.cpp
         LegalityPredicates.cpp
         LegalizeMutations.cpp
         Legalizer.cpp
         LegalizerHelper.cpp
         LegalizerInfo.cpp
         Localizer.cpp
+        LostDebugLocObserver.cpp
         MachineIRBuilder.cpp
         RegBankSelect.cpp
         RegisterBank.cpp
         RegisterBankInfo.cpp
         Utils.cpp
 
         DEPENDS
         intrinsics_gen
   )

llvm/lib/CodeGen/GlobalISel/Legalizer.cpp

 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SetVector.h"
 #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/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;
 
 static cl::opt<bool>
     EnableCSEInLegalizer("enable-cse-in-legalizer",
                          cl::desc("Should enable CSE in Legalizer"),
                          cl::Optional, cl::init(false));
 
+enum class DebugLocVerifyLevel {
+  None,
+  Legalizations,
+  LegalizationsAndArtifactCombiners,
+};
+#ifndef NDEBUG
+static cl::opt<DebugLocVerifyLevel> VerifyDebugLocs(
+    "verify-legalizer-debug-locs",
+    cl::desc("Verify that debug locations are handled"),
+    cl::values(clEnumVal(DebugLocVerifyLevel::None, "No verification"),
+               clEnumVal(DebugLocVerifyLevel::Legalizations,
+                         "Verify legalizations"),
+               clEnumVal(DebugLocVerifyLevel::LegalizationsAndArtifactCombiners,
+                         "Verify legalizations and artifact combines")),
+    cl::init(DebugLocVerifyLevel::Legalizations));
+#else
+// Always disable it for release builds by preventing the observer from being
+// installed.
+static const DebugLocVerifyLevel VerifyDebugLocs = DebugLocVerifyLevel::None;
+#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_END(Legalizer, DEBUG_TYPE,
                     "Legalize the Machine IR a function's Machine IR", false,
void changedInstr(MachineInstr &MI) override {
     createdOrChangedInstr(MI);
   }
 };
 } // namespace
 
 Legalizer::MFResult
 Legalizer::legalizeMachineFunction(MachineFunction &MF, const LegalizerInfo &LI,
                                    ArrayRef<GISelChangeObserver *> AuxObservers,
+                                   LostDebugLocObserver &LocObserver,
                                    MachineIRBuilder &MIRBuilder) {
   MachineRegisterInfo &MRI = MF.getRegInfo();
 
   // Populate worklists.
   InstListTy InstList;
   ArtifactListTy ArtifactList;
   ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
   // Perform legalization bottom up so we can DCE as we legalize.
do {
     unsigned NumArtifacts = ArtifactList.size();
     while (!InstList.empty()) {
       MachineInstr &MI = *InstList.pop_back_val();
       assert(isPreISelGenericOpcode(MI.getOpcode()) &&
              "Expecting generic opcode");
       if (isTriviallyDead(MI, MRI)) {
         LLVM_DEBUG(dbgs() << MI << "Is dead; erasing.\n");
         MI.eraseFromParentAndMarkDBGValuesForRemoval();
+        LocObserver.checkpoint();
         continue;
       }
 
       // Do the legalization for this instruction.
       auto Res = Helper.legalizeInstrStep(MI);
       // Error out if we couldn't legalize this instruction. We may want to
       // fall back to DAG ISel instead in the future.
       if (Res == LegalizerHelper::UnableToLegalize) {
while (!InstList.empty()) {
           (void)NumArtifacts;
           RetryList.push_back(&MI);
           continue;
         }
         Helper.MIRBuilder.stopObservingChanges();
         return {Changed, &MI};
       }
       WorkListObserver.printNewInstrs();
+      LocObserver.checkpoint();
       Changed |= Res == LegalizerHelper::Legalized;
     }
     // Try to combine the instructions in RetryList again if there
     // are new artifacts. If not, stop legalizing.
     if (!RetryList.empty()) {
       if (!ArtifactList.empty()) {
         while (!RetryList.empty())
           ArtifactList.insert(RetryList.pop_back_val());
       } else {
         LLVM_DEBUG(dbgs() << "No new artifacts created, not retrying!\n");
         Helper.MIRBuilder.stopObservingChanges();
         return {Changed, RetryList.front()};
       }
     }
+    LocObserver.checkpoint();
     while (!ArtifactList.empty()) {
       MachineInstr &MI = *ArtifactList.pop_back_val();
       assert(isPreISelGenericOpcode(MI.getOpcode()) &&
              "Expecting generic opcode");
       if (isTriviallyDead(MI, MRI)) {
         LLVM_DEBUG(dbgs() << MI << "Is dead\n");
         RemoveDeadInstFromLists(&MI);
         MI.eraseFromParentAndMarkDBGValuesForRemoval();
+        LocObserver.checkpoint();
         continue;
       }
       SmallVector<MachineInstr *, 4> DeadInstructions;
       LLVM_DEBUG(dbgs() << "Trying to combine: " << MI);
       if (ArtCombiner.tryCombineInstruction(MI, DeadInstructions,
                                             WrapperObserver)) {
         WorkListObserver.printNewInstrs();
+        LocObserver.checkpoint(
+            VerifyDebugLocs ==
+            DebugLocVerifyLevel::LegalizationsAndArtifactCombiners);
         for (auto *DeadMI : DeadInstructions) {
           LLVM_DEBUG(dbgs() << *DeadMI << "Is dead\n");
           RemoveDeadInstFromLists(DeadMI);
           DeadMI->eraseFromParentAndMarkDBGValuesForRemoval();
         }
+        LocObserver.checkpoint();
         Changed = true;
         continue;
       }
       // If this was not an artifact (that could be combined away), this might
       // need special handling. Add it to InstList, so when it's processed
       // there, it has to be legal or specially handled.
       else {
         LLVM_DEBUG(dbgs() << ".. Not combined, moving to instructions list\n");
if (EnableCSE) {
     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()));
+  LostDebugLocObserver LocObserver(DEBUG_TYPE);
+  if (VerifyDebugLocs > DebugLocVerifyLevel::None)
+    AuxObservers.push_back(&LocObserver);
 
   const LegalizerInfo &LI = *MF.getSubtarget().getLegalizerInfo();
-  MFResult Result = legalizeMachineFunction(MF, LI, AuxObservers, *MIRBuilder);
+  MFResult Result =
+      legalizeMachineFunction(MF, LI, AuxObservers, LocObserver, *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 (LocObserver.getNumLostDebugLocs()) {
+    MachineOptimizationRemarkMissed R("gisel-legalize", "LostDebugLoc",
+                                      MF.getFunction().getSubprogram(),
+                                      /*MBB=*/&*MF.begin());
+    R << "lost "
+      << ore::NV("NumLostDebugLocs", LocObserver.getNumLostDebugLocs())
+      << " debug locations during pass";
+    reportGISelWarning(MF, TPC, MORE, R);
+    // Example remark:
+    // --- !Missed
+    // Pass:            gisel-legalize
+    // Name:            GISelFailure
+    // DebugLoc:        { File: '.../legalize-urem.mir', Line: 1, Column: 0 }
+    // Function:        test_urem_s32
+    // Args:
+    //   - String:          'lost '
+    //   - NumLostDebugLocs: '1'
+    //   - String:          ' debug locations during pass'
+    // ...
+  }
+
   // 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/LostDebugLocObserver.cpp

+//===----- llvm/CodeGen/GlobalISel/LostDebugLocObserver.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
+//
+//===----------------------------------------------------------------------===//
+//
+/// Tracks DebugLocs between checkpoints and verifies that they are transferred.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/GlobalISel/LostDebugLocObserver.h"
+
+using namespace llvm;
+
+#define LOC_DEBUG(X) DEBUG_WITH_TYPE(DebugType.str().c_str(), X)
+
+void LostDebugLocObserver::analyzeDebugLocations() {
+  if (LostDebugLocs.empty()) {
+    LOC_DEBUG(dbgs() << ".. No debug info was present\n");
+    return;
+  }
+  if (PotentialMIsForDebugLocs.empty()) {
+    LOC_DEBUG(
+        dbgs() << ".. No instructions to carry debug info (dead code?)\n");
+    return;
+  }
+
+  LOC_DEBUG(dbgs() << ".. Searching " << PotentialMIsForDebugLocs.size()
+                   << " instrs for " << LostDebugLocs.size() << " locations\n");
+  SmallPtrSet<MachineInstr *, 4> FoundIn;
+  for (MachineInstr *MI : PotentialMIsForDebugLocs) {
+    if (!MI->getDebugLoc())
+      continue;
+    // Check this first in case there's a matching line-0 location on both input
+    // and output.
+    if (MI->getDebugLoc().getLine() == 0) {
+      LOC_DEBUG(
+          dbgs() << ".. Assuming line-0 location covers remainder (if any)\n");
+      return;
+    }
+    if (LostDebugLocs.erase(MI->getDebugLoc())) {
+      LOC_DEBUG(dbgs() << ".. .. found " << MI->getDebugLoc() << " in " << *MI);
+      FoundIn.insert(MI);
+      continue;
+    }
+  }
+  if (LostDebugLocs.empty())
+    return;
+
+  NumLostDebugLocs += LostDebugLocs.size();
+  LOC_DEBUG({
+    dbgs() << ".. Lost locations:\n";
+    for (const DebugLoc &Loc : LostDebugLocs) {
+      dbgs() << ".. .. ";
+      Loc.print(dbgs());
+      dbgs() << "\n";
+    }
+    dbgs() << ".. MIs with matched locations:\n";
+    for (MachineInstr *MI : FoundIn)
+      if (PotentialMIsForDebugLocs.erase(MI))
+        dbgs() << ".. .. " << *MI;
+    dbgs() << ".. Remaining MIs with unmatched/no locations:\n";
+    for (const MachineInstr *MI : PotentialMIsForDebugLocs)
+      dbgs() << ".. .. " << *MI;
+  });
+}
+
+void LostDebugLocObserver::checkpoint(bool CheckDebugLocs) {
+  if (CheckDebugLocs)
+    analyzeDebugLocations();
+  PotentialMIsForDebugLocs.clear();
+  LostDebugLocs.clear();
+}
+
+void LostDebugLocObserver::createdInstr(MachineInstr &MI) {
+  PotentialMIsForDebugLocs.insert(&MI);
+}
+
+bool irTranslatorNeverAddsLocations(unsigned Opcode) {
+  switch (Opcode) {
+  default:
+    return false;
+  case TargetOpcode::G_CONSTANT:
+  case TargetOpcode::G_FCONSTANT:
+  case TargetOpcode::G_IMPLICIT_DEF:
+  case TargetOpcode::G_GLOBAL_VALUE:
+    return true;
+  }
+}
+
+void LostDebugLocObserver::erasingInstr(MachineInstr &MI) {
+  if (irTranslatorNeverAddsLocations(MI.getOpcode()))
+    return;
+
+  PotentialMIsForDebugLocs.erase(&MI);
+  if (MI.getDebugLoc())
+    LostDebugLocs.insert(MI.getDebugLoc());
+}
+
+void LostDebugLocObserver::changingInstr(MachineInstr &MI) {
+  if (irTranslatorNeverAddsLocations(MI.getOpcode()))
+    return;
+
+  PotentialMIsForDebugLocs.erase(&MI);
+  if (MI.getDebugLoc())
+    LostDebugLocs.insert(MI.getDebugLoc());
+}
+
+void LostDebugLocObserver::changedInstr(MachineInstr &MI) {
+  PotentialMIsForDebugLocs.insert(&MI);
+}

llvm/unittests/CodeGen/GlobalISel/LegalizerTest.cpp

 //===- LegalizerTest.cpp --------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
-#include "GISelMITest.h"
 #include "llvm/CodeGen/GlobalISel/Legalizer.h"
+#include "GISelMITest.h"
+#include "llvm/CodeGen/GlobalISel/LostDebugLocObserver.h"
+
+#define DEBUG_TYPE "legalizer-test"
 
 using namespace LegalizeActions;
 using namespace LegalizeMutations;
 using namespace LegalityPredicates;
 
 namespace {
 
 ::testing::AssertionResult isNullMIPtr(const MachineInstr *MI) {
StringRef MIRString = R"(
     %v:_(<2 x s8>) = G_LOAD %vptr:_(p0) :: (load 2, align 1)
     $h4 = COPY %v:_(<2 x s8>)
   )";
   setUp(MIRString.rtrim(' '));
   if (!TM)
     return;
 
   ALegalizerInfo LI(MF->getSubtarget());
+  LostDebugLocObserver LocObserver(DEBUG_TYPE);
 
-  Legalizer::MFResult Result =
-      Legalizer::legalizeMachineFunction(*MF, LI, {}, B);
+  Legalizer::MFResult Result = Legalizer::legalizeMachineFunction(
+      *MF, LI, {&LocObserver}, LocObserver, B);
 
   EXPECT_TRUE(isNullMIPtr(Result.FailedOn));
   EXPECT_TRUE(Result.Changed);
 
   StringRef CheckString = R"(
     CHECK:      %vptr:_(p0) = COPY $x4
     CHECK-NEXT: [[LOAD_0:%[0-9]+]]:_(s16) = G_LOAD %vptr:_(p0) :: (load 1)
     CHECK-NEXT: [[OFFSET_1:%[0-9]+]]:_(s64) = G_CONSTANT i64 1
StringRef MIRString = R"(
     %v0_ext:_(s16) = G_ANYEXT %v0:_(s8)
     $h4 = COPY %v0_ext:_(s16)
   )";
   setUp(MIRString.rtrim(' '));
   if (!TM)
     return;
 
   ALegalizerInfo LI(MF->getSubtarget());
+  LostDebugLocObserver LocObserver(DEBUG_TYPE);
 
   // The events here unfold as follows:
   // 1. First, the function is scanned pre-forming the worklist of artifacts:
   //
   //      UNMERGE  (1): pushed into the worklist first, will be processed last.
   //         |
   //       ANYEXT  (2)
   //
TEST_F(AArch64GISelMITest, UnorderedArtifactCombiningTest) {
   //       fully eliminates all the artifacts and legalization succeeds.
   //
   //  We're looking into making sure that (4.B) happens here, not (4.A). Note
   //  that in that case the first scan through the artifacts worklist, while not
   //  being done in any guaranteed order, only needs to find the innermost
   //  pair(s) of artifacts that could be immediately combined out. After that
   //  the process follows def-use chains, making them shorter at each step, thus
   //  combining everything that can be combined in O(n) time.
-  Legalizer::MFResult Result =
-      Legalizer::legalizeMachineFunction(*MF, LI, {}, B);
+  Legalizer::MFResult Result = Legalizer::legalizeMachineFunction(
+      *MF, LI, {&LocObserver}, LocObserver, B);
 
   EXPECT_TRUE(isNullMIPtr(Result.FailedOn));
   EXPECT_TRUE(Result.Changed);
 
   StringRef CheckString = R"(
     CHECK:      %vptr:_(p0) = COPY $x4
     CHECK-NEXT: [[LOAD_0:%[0-9]+]]:_(s16) = G_LOAD %vptr:_(p0) :: (load 1)
     CHECK:      %v0_ext:_(s16) = COPY [[LOAD_0]]:_(s16)
StringRef MIRString = R"(
     $w4 = COPY %v0_zext:_(s32)
     $w5 = COPY %v1_sext:_(s32)
   )";
   setUp(MIRString.rtrim(' '));
   if (!TM)
     return;
 
   ALegalizerInfo LI(MF->getSubtarget());
+  LostDebugLocObserver LocObserver(DEBUG_TYPE);
 
-  Legalizer::MFResult Result =
-      Legalizer::legalizeMachineFunction(*MF, LI, {}, B);
+  Legalizer::MFResult Result = Legalizer::legalizeMachineFunction(
+      *MF, LI, {&LocObserver}, LocObserver, B);
 
   EXPECT_TRUE(isNullMIPtr(Result.FailedOn));
   EXPECT_TRUE(Result.Changed);
 
   StringRef CheckString = R"(
     CHECK:      %vptr:_(p0) = COPY $x4
     CHECK-NEXT: [[LOAD_0:%[0-9]+]]:_(s16) = G_LOAD %vptr:_(p0) :: (load 1)
     CHECK-NEXT: [[OFFSET_1:%[0-9]+]]:_(s64) = G_CONSTANT i64 1