[globalisel][combiner] Make the CombinerChangeObserver a MachineFunction::Delegate

[dsanders]

Summary

This allows us to register it with the MachineFunction delegate and be
notified automatically about erasure and creation of instructions. However,
we still need explicit notification for modifications such as those caused
by setReg() or replaceRegWith().

There is a catch with this though. The notification for creation is
delivered before any operands can be added. While appropriate for
scheduling combiner work. This is unfortunate for debug output since an
opcode by itself doesn't provide sufficient information on what happened.
As a result, the work list remembers the instructions (when debug output is
requested) and emits a more complete dump later.

Another nit is that the MachineFunction::Delegate provides const pointers
which is inconvenient since we want to use it to schedule future
modification. To resolve this GISelWorkList now has an optional pointer to
the MachineFunction which describes the scope of the work it is permitted
to schedule. If a given MachineInstr* is in this function then it is
permitted to schedule work to be performed on the MachineInstr's. An
alternative to this would be to remove the const from the
MachineFunction::Delegate interface, however delegates are not permitted
to modify the MachineInstr's they receive.

In addition to this, the observer has three interface changes.

• erasedInstr() is now erasingInstr() to indicate it is about to be erased but still exists at the moment.
• changingInstr() and changedInstr() have been added to report changes before and after they are made. This allows us to trace the changes in the debug output.
• As a convenience changingAllUsesOfReg() and finishedChangingAllUsesOfReg() will report changingInstr() and changedInstr() for each use of a given register. This is primarily useful for changes caused by MachineRegisterInfo::replaceRegWith()

With this in place, both combine rules have been updated to report their
changes to the observer.

Finally, make some cosmetic changes to the debug output and make Combiner
and CombinerHelp

[dsanders]

ping

[aditya_nandakumar]

Hi Daniel, the patch looks mostly good - I just have a couple of minor nitpicks.

include/llvm/CodeGen/GlobalISel/Combiner.h

49 ↗

(On Diff #168532)

It's not very clear from the comments regarding when the clients using the observer should call changingInstr vs changedInstr. What happens if when they are changing instruction, and they forget to call changinginst and only call changedInst?

include/llvm/CodeGen/GlobalISel/GISelWorkList.h

82

I understand what this is for, but I'm not sure if these asserts will ever trigger - and if we should have these.

[aditya_nandakumar]

include/llvm/CodeGen/GlobalISel/CombinerHelper.h

39

Also, should replaceRegWith respect register constraints (such as RegBank/RegClass) and emit copies while replacing?

[dsanders]

include/llvm/CodeGen/GlobalISel/Combiner.h

49 ↗

(On Diff #168532)

It's not an either-or thing, they should call both. There are two events involved in changing an instruction, the first (changingInstr) occurs before the changes are made and the second (changedInstr) occurs after the changes are made.

include/llvm/CodeGen/GlobalISel/CombinerHelper.h

39

It's not necessary for the calls in CombineHelper right now but we will certainly want a variant of this that does that at some point

include/llvm/CodeGen/GlobalISel/GISelWorkList.h

82

Assuming we write our code correctly, they won't trigger :-).

We spoke off-list about this and it's my understanding that your main concern is that GISelWorkList should be able to handle instructions that aren't in a function+bb. We don't have any such instances right now but I see your point. We could potentially tweak the name to make it clearer or we could wait until we have a case that works on MI's that aren't in a block/function and resolve it then. I suspect we're unlikely to find such a case in the near future since it's not common to create an instruction but keep it outside of bbs/functions long term.

lib/CodeGen/GlobalISel/Combiner.cpp

62–63

This line shouldn't be here and is probably the cause of your confusion about the difference between changingInstr() and changedInstr(). It won't cause any trouble but it's not necessary.

[aditya_nandakumar]

include/llvm/CodeGen/GlobalISel/CombinerHelper.h

39

It would be great if you can address this (even with a naive check if constraints are not met insert a copy). This can be a very subtle bug to figure out when it starts happening.

include/llvm/CodeGen/GlobalISel/GISelWorkList.h

82

Yes. Please update the comment to reflect this new change. Also if you're checking that you're inserting valid instructions (with parents), you should move these asserts to the non const method as well.

[dsanders]

Obey constraints in replaceRegWith()
Correct the extending load combine use of replaceRegWith where we replace the
input of an extend to a wider-than-preferred type. Previously we were calling
replaceRegWith() multiple times for the same reg and changing the types of the
vreg in the process. We'd always fix it by the time we were finished but we have
asserts checking the intermediates now.

[dsanders]

include/llvm/CodeGen/GlobalISel/GISelWorkList.h

82

I believe the only remaining review comment is this one. I'm not sure what change you're referring to here w.r.t the comment to be updated (probably because it's taken so long for me to get back to this, sorry).

The asserts are only necessary where it's not clear that you have the right to modify the instructions which is only an issue for the const version. The non-const version is clearly allowed to modify it as it's not const whereas the const version has to know it can find a non-const pointer to the same object.

[dsanders]

Rebase and fix the remaining issue about documenting the right-to-modify
MachineInstrs within the specified function and making the non-const ptr
scheduling have consistent requirements with the const ptr scheduling.

[aditya_nandakumar]

include/llvm/CodeGen/GlobalISel/CombinerHelper.h

42

Consider naming the second parameter something similar to "FromRegOp" for better clarity.

lib/CodeGen/GlobalISel/CombinerHelper.cpp

39

ditto for naming FromReg to indicate it's a MachineOperand.

44

If this MachineOperand is a def, should this call replaceRegWith which also handles the constraining?

320

Should this call CombinerHelper::replaceRegOpWith which will handle the Observer notifying?

327

This also looks like it could go through replaceRegOpWith interface?

[dsanders]

lib/CodeGen/GlobalISel/CombinerHelper.cpp

320

I think this can be done. I just need to re-test it

327

This one is a little special. We reported it changing right back at the start when we changed the opcode and changing/changed should probably be balanced. For the constraints aspect of it, I don't believe we need to do anything here as G_*LOAD and G_TRUNC/G_*EXT should have compatible result constraints by definition. If that's not true, the right thing to do would be to reject the combine.

[aditya_nandakumar]

Thanks Daniel. LGTM with changes to the nitpicks..

include/llvm/CodeGen/GlobalISel/CombinerHelper.h

-//== llvm/CodeGen/GlobalISel/CombinerHelper.h -------------- -*- C++ -*-==//
+//===-- llvm/CodeGen/GlobalISel/CombinerHelper.h --------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===--------------------------------------------------------------------===//
 //

 #define LLVM_CODEGEN_GLOBALISEL_COMBINER_HELPER_H
 
 namespace llvm {
 
 class GISelChangeObserver;
 class MachineIRBuilder;
 class MachineRegisterInfo;
 class MachineInstr;
+class MachineOperand;
 
 class CombinerHelper {
   MachineIRBuilder &Builder;
   MachineRegisterInfo &MRI;
   GISelChangeObserver &Observer;
 
-  void scheduleForVisit(MachineInstr &MI);
-
 public:
   CombinerHelper(GISelChangeObserver &Observer, MachineIRBuilder &B);
 
+  /// MachineRegisterInfo::replaceRegWith() and inform the observer of the changes
+  void replaceRegWith(MachineRegisterInfo &MRI, unsigned FromReg, unsigned ToReg) const;
+
+  /// Replace a single register operand with a new register and inform the
+  /// observer of the changes.
+  void replaceRegOpWith(MachineRegisterInfo &MRI, MachineOperand &FromReg,
+                        unsigned ToReg) const;
+
   /// If \p MI is COPY, try to combine it.
   /// Returns true if MI changed.
   bool tryCombineCopy(MachineInstr &MI);
 
   /// If \p MI is extend that consumes the result of a load, try to combine it.
   /// Returns true if MI changed.
   bool tryCombineExtendingLoads(MachineInstr &MI);
 
   /// Try to transform \p MI by using all of the above
   /// combine functions. Returns true if changed.
   bool tryCombine(MachineInstr &MI);
 };
 } // namespace llvm
 
 #endif

include/llvm/CodeGen/GlobalISel/CombinerInfo.h

public:
   /// If \p IllegalOpsAllowed is false, the CombinerHelper will make use of
   /// the legalizerInfo to check for legality before each transformation.
   bool IllegalOpsAllowed; // TODO: Make use of this.
 
   /// If \p LegalizeIllegalOps is true, the Combiner will also legalize the
   /// illegal ops that are created.
   bool LegalizeIllegalOps; // TODO: Make use of this.
   const LegalizerInfo *LInfo;
+
+  /// Attempt to combine instructions using MI as the root.
+  ///
+  /// Use Observer to report the creation, modification, and erasure of
+  /// instructions. GISelChangeObserver will automatically report certain
+  /// kinds of operations. These operations are:
+  /// * Instructions that are newly inserted into the MachineFunction
+  /// * Instructions that are erased from the MachineFunction.
+  ///
+  /// However, it is important to report instruction modification and this is
+  /// not automatic.
   virtual bool combine(GISelChangeObserver &Observer, MachineInstr &MI,
                        MachineIRBuilder &B) const = 0;
 };
 } // namespace llvm
 
 #endif

include/llvm/CodeGen/GlobalISel/GISelChangeObserver.h

-//== ----- llvm/CodeGen/GlobalISel/GISelChangeObserver.h ---------------------
-//== //
+//===----- llvm/CodeGen/GlobalISel/GISelChangeObserver.h ------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 /// This contains common code to allow clients to notify changes to machine
 /// instr.
 //
 //===----------------------------------------------------------------------===//
 #ifndef LLVM_CODEGEN_GLOBALISEL_GISELCHANGEOBSERVER_H
 #define LLVM_CODEGEN_GLOBALISEL_GISELCHANGEOBSERVER_H
 
+#include "llvm/ADT/SmallPtrSet.h"
+
 namespace llvm {
+class MachineInstr;
+class MachineRegisterInfo;
+
 /// Abstract class that contains various methods for clients to notify about
 /// changes. This should be the preferred way for APIs to notify changes.
 /// Typically calling erasingInstr/createdInstr multiple times should not affect
 /// the result. The observer would likely need to check if it was already
 /// notified earlier (consider using GISelWorkList).
-class MachineInstr;
 class GISelChangeObserver {
+  SmallPtrSet<MachineInstr *, 4> ChangingAllUsesOfReg;
+
 public:
   virtual ~GISelChangeObserver() {}
 
   /// An instruction is about to be erased.
-  virtual void erasingInstr(MachineInstr &MI) = 0;
+  virtual void erasingInstr(const MachineInstr &MI) = 0;
   /// An instruction was created and inserted into the function.
-  virtual void createdInstr(MachineInstr &MI) = 0;
+  virtual void createdInstr(const MachineInstr &MI) = 0;
   /// This instruction is about to be mutated in some way.
-  virtual void changingInstr(MachineInstr &MI) = 0;
+  virtual void changingInstr(const MachineInstr &MI) = 0;
   /// This instruction was mutated in some way.
-  virtual void changedInstr(MachineInstr &MI) = 0;
+  virtual void changedInstr(const MachineInstr &MI) = 0;
+
+  /// All the instructions using the given register are being changed.
+  /// For convenience, finishedChangingAllUsesOfReg() will report the completion
+  /// of the changes. The use list may change between this call and
+  /// finishedChangingAllUsesOfReg().
+  void changingAllUsesOfReg(const MachineRegisterInfo &MRI, unsigned Reg);
+  /// All instructions reported as changing by changingAllUsesOfReg() have
+  /// finished being changed.
+  void finishedChangingAllUsesOfReg();
+
 };
 
 } // namespace llvm
 #endif

include/llvm/CodeGen/GlobalISel/GISelWorkList.h

 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Debug.h"
 
 namespace llvm {
 
 class MachineInstr;
 
-// Worklist which mostly works similar to InstCombineWorkList, but on MachineInstrs.
-// The main difference with something like a SetVector is that erasing an element doesn't
-// move all elements over one place - instead just nulls out the element of the vector.
-// FIXME: Does it make sense to factor out common code with the instcombinerWorkList?
+// Worklist which mostly works similar to InstCombineWorkList, but on
+// MachineInstrs. The main difference with something like a SetVector is that
+// erasing an element doesn't move all elements over one place - instead just
+// nulls out the element of the vector.
+//
+// This worklist operates on instructions within a particular function. This is
+// important for acquiring the rights to modify/replace instructions a
+// GISelChangeObserver reports as the observer doesn't have the right to make
+// changes to the instructions it sees so we use our access to the
+// MachineFunction to establish that it's ok to add a given instruction to the
+// worklist.
+//
+// FIXME: Does it make sense to factor out common code with the
+// instcombinerWorkList?
 template<unsigned N>
 class GISelWorkList {
-  SmallVector<MachineInstr*, N> Worklist;
-  DenseMap<MachineInstr*, unsigned> WorklistMap;
+  MachineFunction *MF;
+  SmallVector<MachineInstr *, N> Worklist;
+  DenseMap<MachineInstr *, unsigned> WorklistMap;
 
 public:
-  GISelWorkList() = default;
+  GISelWorkList(MachineFunction *MF) : MF(MF) {}
 
   bool empty() const { return WorklistMap.empty(); }
 
   unsigned size() const { return WorklistMap.size(); }
 
-  /// Add - Add the specified instruction to the worklist if it isn't already
-  /// in it.
+  /// Add the specified instruction to the worklist if it isn't already in it.
   void insert(MachineInstr *I) {
-    if (WorklistMap.try_emplace(I, Worklist.size()).second) {
-      Worklist.push_back(I);
+    // It would be safe to add this instruction to the worklist regardless but
+    // for consistency with the const version, check that the instruction we're
+    // adding would have been accepted if we were given a const pointer instead.
+    insert(const_cast<const MachineInstr *>(I));
+  }
+
+  void insert(const MachineInstr *I) {
+    // Confirm we'd be able to find the non-const pointer we want to schedule if
+    // we wanted to. We have the right to schedule work that may modify any
+    // instruction in MF.
+    assert(I->getParent() && "Expected parent BB");
+    assert(I->getParent()->getParent() && "Expected parent function");
+    assert((!MF || I->getParent()->getParent() == MF) &&
+           "Expected parent function to be current function or not given");
+
+    // But don't actually do the search since we can derive it from the const
+    // pointer.
+    MachineInstr *NonConstI = const_cast<MachineInstr *>(I);
+    if (WorklistMap.try_emplace(NonConstI, Worklist.size()).second) {
+      Worklist.push_back(NonConstI);
     }
   }
 
-  /// Remove - remove I from the worklist if it exists.
-  void remove(MachineInstr *I) {
+  /// Remove I from the worklist if it exists.
+  void remove(const MachineInstr *I) {
     auto It = WorklistMap.find(I);
     if (It == WorklistMap.end()) return; // Not in worklist.
 
     // Don't bother moving everything down, just null out the slot.
     Worklist[It->second] = nullptr;
 
     WorklistMap.erase(It);
   }
 
   MachineInstr *pop_back_val() {
     MachineInstr *I;
     do {
       I = Worklist.pop_back_val();
     } while(!I);
     assert(I && "Pop back on empty worklist");
     WorklistMap.erase(I);
     return I;
   }
 };
 
 } // end namespace llvm.
 
 #endif

lib/CodeGen/GlobalISel/CMakeLists.txt

 add_llvm_library(LLVMGlobalISel
         CallLowering.cpp
         GlobalISel.cpp
         Combiner.cpp
         CombinerHelper.cpp
+        GISelChangeObserver.cpp
         IRTranslator.cpp
         InstructionSelect.cpp
         InstructionSelector.cpp
         LegalityPredicates.cpp
         LegalizeMutations.cpp
         Legalizer.cpp
         LegalizerHelper.cpp
         LegalizerInfo.cpp

lib/CodeGen/GlobalISel/Combiner.cpp

-//===-- lib/CodeGen/GlobalISel/GICombiner.cpp -----------------------===//
+//===-- lib/CodeGen/GlobalISel/Combiner.cpp -------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //

 
 #define DEBUG_TYPE "gi-combiner"
 
 using namespace llvm;
 
 namespace {
 /// This class acts as the glue the joins the CombinerHelper to the overall
 /// Combine algorithm. The CombinerHelper is intended to report the
-/// modifications it makes to the MIR to the CombinerChangeObserver and the
+/// modifications it makes to the MIR to the GISelChangeObserver and the
 /// observer subclass will act on these events. In this case, instruction
 /// erasure will cancel any future visits to the erased instruction and
 /// instruction creation will schedule that instruction for a future visit.
 /// Other Combiner implementations may require more complex behaviour from
-/// their CombinerChangeObserver subclass.
-class WorkListMaintainer : public GISelChangeObserver {
+/// their GISelChangeObserver subclass.
+class WorkListMaintainer : public GISelChangeObserver,
+                           public MachineFunction::Delegate {
   using WorkListTy = GISelWorkList<512>;
+  MachineFunction &MF;
   WorkListTy &WorkList;
+  /// The instructions that have been created but we want to report once they
+  /// have their operands. This is only maintained if debug output is requested.
+  SmallPtrSet<const MachineInstr *, 4> CreatedInstrs;
 
 public:
-  WorkListMaintainer(WorkListTy &WorkList) : WorkList(WorkList) {}
-  virtual ~WorkListMaintainer() {}
+  WorkListMaintainer(MachineFunction &MF, WorkListTy &WorkList)
+      : GISelChangeObserver(), MF(MF), WorkList(WorkList) {
+    MF.setDelegate(this);
+  }
+  virtual ~WorkListMaintainer() {
+    MF.resetDelegate(this);
+  }
 
-  void erasingInstr(MachineInstr &MI) override {
+  void erasingInstr(const MachineInstr &MI) override {
     LLVM_DEBUG(dbgs() << "Erased: " << MI << "\n");
     WorkList.remove(&MI);
   }
-  void createdInstr(MachineInstr &MI) override {
-    LLVM_DEBUG(dbgs() << "Created: " << MI << "\n");
+  void createdInstr(const MachineInstr &MI) override {
+    LLVM_DEBUG(dbgs() << "Creating: " << MI << "\n");
     WorkList.insert(&MI);
+    LLVM_DEBUG(CreatedInstrs.insert(&MI));
   }
-  void changingInstr(MachineInstr &MI) override {
+  void changingInstr(const MachineInstr &MI) override {
     LLVM_DEBUG(dbgs() << "Changing: " << MI << "\n");
-    WorkList.remove(&MI);
+    WorkList.insert(&MI);
   }
-  // Currently changed conservatively assumes erased.
-  void changedInstr(MachineInstr &MI) override {
+  void changedInstr(const MachineInstr &MI) override {
     LLVM_DEBUG(dbgs() << "Changed: " << MI << "\n");
-    WorkList.remove(&MI);
+    WorkList.insert(&MI);
+  }
+
+  void reportFullyCreatedInstrs() {
+    LLVM_DEBUG(for (const auto *MI
+                    : CreatedInstrs) {
+      dbgs() << "Created: ";
+      MI->print(dbgs());
+    });
+    LLVM_DEBUG(CreatedInstrs.clear());
+  }
+
+  void MF_HandleInsertion(const MachineInstr &MI) override {
+    createdInstr(MI);
+  }
+  void MF_HandleRemoval(const MachineInstr &MI) override {
+    erasingInstr(MI);
   }
 };
 }
 
 Combiner::Combiner(CombinerInfo &Info, const TargetPassConfig *TPC)
     : CInfo(Info), TPC(TPC) {
   (void)this->TPC; // FIXME: Remove when used.
 }
bool Combiner::combineMachineInstrs(MachineFunction &MF) {
   bool MFChanged = false;
   bool Changed;
 
   do {
     // Collect all instructions. Do a post order traversal for basic blocks and
     // insert with list bottom up, so while we pop_back_val, we'll traverse top
     // down RPOT.
     Changed = false;
-    GISelWorkList<512> WorkList;
-    WorkListMaintainer Observer(WorkList);
+    GISelWorkList<512> WorkList(&MF);
+    WorkListMaintainer Observer(MF, WorkList);
     for (MachineBasicBlock *MBB : post_order(&MF)) {
       if (MBB->empty())
         continue;
       for (auto MII = MBB->rbegin(), MIE = MBB->rend(); MII != MIE;) {
         MachineInstr *CurMI = &*MII;
         ++MII;
         // Erase dead insts before even adding to the list.
         if (isTriviallyDead(*CurMI, *MRI)) {
           LLVM_DEBUG(dbgs() << *CurMI << "Is dead; erasing.\n");
           CurMI->eraseFromParentAndMarkDBGValuesForRemoval();
           continue;
         }
         WorkList.insert(CurMI);
       }
     }
     // Main Loop. Process the instructions here.
     while (!WorkList.empty()) {
       MachineInstr *CurrInst = WorkList.pop_back_val();
-      LLVM_DEBUG(dbgs() << "Try combining " << *CurrInst << "\n";);
+      LLVM_DEBUG(dbgs() << "\nTry combining " << *CurrInst;);
       Changed |= CInfo.combine(Observer, *CurrInst, Builder);
+      Observer.reportFullyCreatedInstrs();
     }
     MFChanged |= Changed;
   } while (Changed);
 
   return MFChanged;
 }

lib/CodeGen/GlobalISel/CombinerHelper.cpp

-//== ---lib/CodeGen/GlobalISel/GICombinerHelper.cpp --------------------- == //
+//===-- lib/CodeGen/GlobalISel/GICombinerHelper.cpp -----------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 #include "llvm/CodeGen/GlobalISel/CombinerHelper.h"
 #include "llvm/CodeGen/GlobalISel/Combiner.h"
 #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
 #include "llvm/CodeGen/GlobalISel/Utils.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/TargetInstrInfo.h"
 
-#define DEBUG_TYPE "gi-combine"
+#define DEBUG_TYPE "gi-combiner"
 
 using namespace llvm;
 
 CombinerHelper::CombinerHelper(GISelChangeObserver &Observer,
                                MachineIRBuilder &B)
     : Builder(B), MRI(Builder.getMF().getRegInfo()), Observer(Observer) {}
 
-void CombinerHelper::scheduleForVisit(MachineInstr &MI) {
-  Observer.createdInstr(MI);
+void CombinerHelper::replaceRegWith(MachineRegisterInfo &MRI, unsigned FromReg,
+                                    unsigned ToReg) const {
+  Observer.changingAllUsesOfReg(MRI, FromReg);
+
+  if (MRI.constrainRegAttrs(ToReg, FromReg))
+    MRI.replaceRegWith(FromReg, ToReg);
+  else
+    Builder.buildCopy(ToReg, FromReg);
+
+  Observer.finishedChangingAllUsesOfReg();
+}
+
+void CombinerHelper::replaceRegOpWith(MachineRegisterInfo &MRI,
+                                      MachineOperand &FromReg,
+                                      unsigned ToReg) const {
+  assert(FromReg.getParent() && "Expected an operand in an MI");
+  Observer.changingInstr(*FromReg.getParent());
+
+  FromReg.setReg(ToReg);
+
+  Observer.changedInstr(*FromReg.getParent());
 }
 
 bool CombinerHelper::tryCombineCopy(MachineInstr &MI) {
   if (MI.getOpcode() != TargetOpcode::COPY)
     return false;
   unsigned DstReg = MI.getOperand(0).getReg();
   unsigned SrcReg = MI.getOperand(1).getReg();
   LLT DstTy = MRI.getType(DstReg);
   LLT SrcTy = MRI.getType(SrcReg);
   // Simple Copy Propagation.
   // a(sx) = COPY b(sx) -> Replace all uses of a with b.
   if (DstTy.isValid() && SrcTy.isValid() && DstTy == SrcTy) {
     MI.eraseFromParent();
-    MRI.replaceRegWith(DstReg, SrcReg);
+    replaceRegWith(MRI, DstReg, SrcReg);
     return true;
   }
   return false;
 }
 
 namespace {
 struct PreferredTuple {
   LLT Ty;                // The result type of the extend.
bool CombinerHelper::tryCombineExtendingLoads(MachineInstr &MI) {
 
   // There were no extends
   if (!Preferred.MI)
     return false;
   // It should be impossible to chose an extend without selecting a different
   // type since by definition the result of an extend is larger.
   assert(Preferred.Ty != LoadValueTy && "Extending to same type?");
 
+  LLVM_DEBUG(dbgs() << "Preferred use is: " << *Preferred.MI);
+
   // Rewrite the load to the chosen extending load.
   unsigned ChosenDstReg = Preferred.MI->getOperand(0).getReg();
+  Observer.changingInstr(MI);
   MI.setDesc(
       Builder.getTII().get(Preferred.ExtendOpcode == TargetOpcode::G_SEXT
                                ? TargetOpcode::G_SEXTLOAD
                                : Preferred.ExtendOpcode == TargetOpcode::G_ZEXT
                                      ? TargetOpcode::G_ZEXTLOAD
                                      : TargetOpcode::G_LOAD));
 
   // Rewrite all the uses to fix up the types.
   SmallVector<MachineInstr *, 1> ScheduleForErase;
   SmallVector<InsertionPoint, 4> ScheduleForInsert;
   for (auto &UseMO : MRI.use_operands(LoadValue.getReg())) {
     MachineInstr *UseMI = UseMO.getParent();
 
     // If the extend is compatible with the preferred extend then we should fix
     // up the type and extend so that it uses the preferred use.
     if (UseMI->getOpcode() == Preferred.ExtendOpcode ||
         UseMI->getOpcode() == TargetOpcode::G_ANYEXT) {
       unsigned UseDstReg = UseMI->getOperand(0).getReg();
-      unsigned UseSrcReg = UseMI->getOperand(1).getReg();
+      MachineOperand &UseSrcMO = UseMI->getOperand(1);
       const LLT &UseDstTy = MRI.getType(UseDstReg);
       if (UseDstReg != ChosenDstReg) {
         if (Preferred.Ty == UseDstTy) {
           // If the use has the same type as the preferred use, then merge
           // the vregs and erase the extend. For example:
           //    %1:_(s8) = G_LOAD ...
           //    %2:_(s32) = G_SEXT %1(s8)
           //    %3:_(s32) = G_ANYEXT %1(s8)
           //    ... = ... %3(s32)
           // rewrites to:
           //    %2:_(s32) = G_SEXTLOAD ...
           //    ... = ... %2(s32)
-          MRI.replaceRegWith(UseDstReg, ChosenDstReg);
+          replaceRegWith(MRI, UseDstReg, ChosenDstReg);
           ScheduleForErase.push_back(UseMO.getParent());
         } else if (Preferred.Ty.getSizeInBits() < UseDstTy.getSizeInBits()) {
           // If the preferred size is smaller, then keep the extend but extend
           // from the result of the extending load. For example:
           //    %1:_(s8) = G_LOAD ...
           //    %2:_(s32) = G_SEXT %1(s8)
           //    %3:_(s64) = G_ANYEXT %1(s8)
           //    ... = ... %3(s64)
           /// rewrites to:
           //    %2:_(s32) = G_SEXTLOAD ...
           //    %3:_(s64) = G_ANYEXT %2:_(s32)
           //    ... = ... %3(s64)
-          MRI.replaceRegWith(UseSrcReg, ChosenDstReg);
+          replaceRegOpWith(MRI, UseSrcMO, ChosenDstReg);
         } else {
           // If the preferred size is large, then insert a truncate. For
           // example:
           //    %1:_(s8) = G_LOAD ...
           //    %2:_(s64) = G_SEXT %1(s8)
           //    %3:_(s32) = G_ZEXT %1(s8)
           //    ... = ... %3(s32)
           /// rewrites to:
bool CombinerHelper::tryCombineExtendingLoads(MachineInstr &MI) {
   DenseMap<MachineBasicBlock *, MachineInstr *> EmittedInsns;
   for (auto &InsertionInfo : ScheduleForInsert) {
     MachineOperand *UseMO = InsertionInfo.UseMO;
     MachineBasicBlock *InsertIntoBB = InsertionInfo.InsertIntoBB;
     MachineBasicBlock::iterator InsertBefore = InsertionInfo.InsertBefore;
 
     MachineInstr *PreviouslyEmitted = EmittedInsns.lookup(InsertIntoBB);
     if (PreviouslyEmitted) {
+      Observer.changingInstr(*UseMO->getParent());
       UseMO->setReg(PreviouslyEmitted->getOperand(0).getReg());
+      Observer.changedInstr(*UseMO->getParent());
       continue;
     }
 
     Builder.setInsertPt(*InsertIntoBB, InsertBefore);
     unsigned NewDstReg = MRI.cloneVirtualRegister(MI.getOperand(0).getReg());
     MachineInstr *NewMI = Builder.buildTrunc(NewDstReg, ChosenDstReg);
     EmittedInsns[InsertIntoBB] = NewMI;
+    Observer.changingInstr(*UseMO->getParent());
     UseMO->setReg(NewDstReg);
-    Observer.createdInstr(*NewMI);
+    Observer.changedInstr(*UseMO->getParent());
   }
   for (auto &EraseMI : ScheduleForErase) {
     Observer.erasingInstr(*EraseMI);
     EraseMI->eraseFromParent();
   }
   MI.getOperand(0).setReg(ChosenDstReg);
+  Observer.changedInstr(MI);
 
   return true;
 }
 
 bool CombinerHelper::tryCombine(MachineInstr &MI) {
   if (tryCombineCopy(MI))
     return true;
   return tryCombineExtendingLoads(MI);
 }

lib/CodeGen/GlobalISel/GISelChangeObserver.cpp

+//===-- lib/CodeGen/GlobalISel/GISelChangeObserver.cpp --------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file constains common code to combine machine functions at generic
+// level.
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+
+using namespace llvm;
+
+void GISelChangeObserver::changingAllUsesOfReg(
+    const MachineRegisterInfo &MRI, unsigned Reg) {
+  for (auto &ChangingMI : MRI.use_instructions(Reg)) {
+    changingInstr(ChangingMI);
+    ChangingAllUsesOfReg.insert(&ChangingMI);
+  }
+}
+
+void GISelChangeObserver::finishedChangingAllUsesOfReg() {
+  for (auto *ChangedMI : ChangingAllUsesOfReg)
+    changedInstr(*ChangedMI);
+}
+

lib/CodeGen/GlobalISel/Legalizer.cpp

 class LegalizerWorkListManager : public GISelChangeObserver {
   InstListTy &InstList;
   ArtifactListTy &ArtifactList;
 
 public:
   LegalizerWorkListManager(InstListTy &Insts, ArtifactListTy &Arts)
       : InstList(Insts), ArtifactList(Arts) {}
 
-  void createdInstr(MachineInstr &MI) override {
+  void createdInstr(const MachineInstr &MI) override {
     // Only legalize pre-isel generic instructions.
     // Legalization process could generate Target specific pseudo
     // instructions with generic types. Don't record them
     if (isPreISelGenericOpcode(MI.getOpcode())) {
       if (isArtifact(MI))
         ArtifactList.insert(&MI);
       else
         InstList.insert(&MI);
     }
     LLVM_DEBUG(dbgs() << ".. .. New MI: " << MI);
   }
 
-  void erasingInstr(MachineInstr &MI) override {
+  void erasingInstr(const MachineInstr &MI) override {
     LLVM_DEBUG(dbgs() << ".. .. Erasing: " << MI);
     InstList.remove(&MI);
     ArtifactList.remove(&MI);
   }
 
-  void changingInstr(MachineInstr &MI) override {
+  void changingInstr(const MachineInstr &MI) override {
     LLVM_DEBUG(dbgs() << ".. .. Changing MI: " << MI);
   }
 
-  void changedInstr(MachineInstr &MI) override {
+  void changedInstr(const 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);
     createdInstr(MI);
   }
 };
 
 bool Legalizer::runOnMachineFunction(MachineFunction &MF) {
   // If the ISel pipeline failed, do not bother running that pass.
   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>();
   MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
 
   const size_t NumBlocks = MF.size();
   MachineRegisterInfo &MRI = MF.getRegInfo();
 
   // Populate Insts
-  InstListTy InstList;
-  ArtifactListTy ArtifactList;
+  InstListTy InstList(&MF);
+  ArtifactListTy ArtifactList(&MF);
   ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
   // Perform legalization bottom up so we can DCE as we legalize.
   // Traverse BB in RPOT and within each basic block, add insts top down,
   // so when we pop_back_val in the legalization process, we traverse bottom-up.
   for (auto *MBB : RPOT) {
     if (MBB->empty())
       continue;
     for (MachineInstr &MI : *MBB) {

test/CodeGen/AArch64/GlobalISel/prelegalizercombiner-extending-loads-cornercases.mir

 # RUN: llc -O0 -run-pass=aarch64-prelegalizer-combiner -global-isel %s -o - | FileCheck %s
+# RUN: llc -O0 -run-pass=aarch64-prelegalizer-combiner -global-isel %s -o - \
+# RUN:   -debug-only=aarch64-prelegalizer-combiner,gi-combiner 2>&1 >/dev/null \
+# RUN:   | FileCheck %s --check-prefix=CHECK-WORKLIST
 
 --- |
   target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128"
   target triple = "aarch64--"
 
   define void @multiple_copies(i8* %addr) {
   entry:
     br i1 0, label %if, label %else
; CHECK: bb.3.exit:
     %8:_(s8) = G_PHI %6:_(s8), %bb.1, %7:_(s8), %bb.2
     ; CHECK: [[T5:%[0-9]+]]:_(s8) = G_PHI [[T2]](s8), %bb.1, [[T4]](s8)
     %9:_(s32) = G_ZEXT %8
     ; CHECK: [[T6:%[0-9]+]]:_(s32) = G_ZEXT [[T5]](s8)
     ; CHECK: $w0 = COPY [[T0]](s32)
     ; CHECK: $w1 = COPY [[T6]](s32)
     $w0 = COPY %3
     $w1 = COPY %9
+
+# Check that we report the correct modifications to the observer. This acts as
+# a test of the debug output and a test.
+#
+# CHECK-WORKLIST-LABEL: Generic MI Combiner for: multiple_copies
+# CHECK-WORKLIST:       Try combining [[IN0:%[0-9]+]]:_(s8) = G_LOAD [[IN1:%[0-9]+]]:_(p0) :: (load 1 from %ir.addr)
+# CHECK-WORKLIST:       Preferred use is: [[IN2:%[0-9]+]]:_(s32) = G_SEXT [[IN0]]:_(s8)
+# CHECK-WORKLIST-DAG:   Changing: [[IN0]]:_(s8) = G_LOAD [[IN1]]:_(p0) :: (load 1 from %ir.addr)
+# CHECK-WORKLIST-DAG:   Changing: [[IN3:%[0-9]+]]:_(s8) = G_ADD [[IN0]]:_, [[IN4:%[0-9]+]]:_
+# CHECK-WORKLIST-DAG:   Changed: [[IN3]]:_(s8) = G_ADD [[NEW1:%[0-9]+]]:_, [[IN4]]:_
+# CHECK-WORKLIST-DAG:   Changing: [[IN5:%[0-9]+]]:_(s8) = G_SUB [[IN0]]:_, [[IN6:%[0-9]+]]:_
+# CHECK-WORKLIST-DAG:   Changed: [[IN5]]:_(s8) = G_SUB [[NEW2:%[0-9]+]]:_, [[IN6]]:_
+# CHECK-WORKLIST-DAG:   Erased: [[IN2]]:_(s32) = G_SEXT [[IN0]]:_(s8)
+# CHECK-WORKLIST-DAG:   Changed: [[IN2]]:_(s32) = G_SEXTLOAD [[IN1]]:_(p0) :: (load 1 from %ir.addr)
+# CHECK-WORKLIST-DAG:   Created: [[NEW1]]:_(s8) = G_TRUNC [[IN2]]:_(s32)
+# CHECK-WORKLIST-DAG:   Created: [[NEW2]]:_(s8) = G_TRUNC [[IN2]]:_(s32)
+# CHECK-WORKLIST:       Try combining
 ...
 
 ---
 name:            sink_to_phi_trivially_dominating
 # CHECK-LABEL: name: sink_to_phi_trivially_dominating
 # This test currently tests that we don't sink if we would sink to a phi. This
 # is needed to avoid inserting into the middle of the leading G_PHI instructions
 # of a BB

 body: |
   bb.0.entry:
     liveins: $x0, $w1
     successors: %bb.1(0x40000000), %bb.2(0x40000000); %bb.1(50.00%), %bb.2(50.00%)
     ; CHECK: [[T0:%[0-9]+]]:_(s32) = G_SEXTLOAD
     %0:_(p0) = COPY $x0
     %1:_(s32) = COPY $w1
     %2:_(s8) = G_LOAD %0 :: (load 1 from %ir.addr)
-    %3:_(s32) = G_SEXT %2
-    %4:_(s32) = G_CONSTANT i32 1
-    %5:_(s1) = G_ICMP intpred(ne), %1:_(s32), %4:_
-    G_BRCOND %5:_(s1), %bb.1
+    %3:_(s32) = G_CONSTANT i32 1
+    %4:_(s1) = G_ICMP intpred(ne), %1:_(s32), %3:_
+    G_BRCOND %4:_(s1), %bb.1
     G_BR %bb.2.else
   bb.1.if:
   ; CHECK: bb.1.if:
     successors: %bb.3(0x80000000)
-    %10:_(s8) = G_CONSTANT i8 1
+    %5:_(s8) = G_CONSTANT i8 1
     ; CHECK: [[T1:%[0-9]+]]:_(s8) = G_TRUNC [[T0]](s32)
-    %6:_(s8) = G_ADD %2, %10
+    %6:_(s8) = G_ADD %2, %5
     ; CHECK: [[T2:%[0-9]+]]:_(s8) = G_ADD [[T1]], {{.*}}
     G_BR %bb.3.exit
   bb.2.else:
   ; CHECK: bb.2.else:
     successors: %bb.3(0x80000000)
-    %11:_(s8) = G_CONSTANT i8 1
+    %7:_(s8) = G_CONSTANT i8 1
     ; CHECK: [[T3:%[0-9]+]]:_(s8) = G_TRUNC [[T0]](s32)
-    %7:_(s8) = G_SUB %2, %11
+    %8:_(s8) = G_SUB %2, %7
     ; CHECK: [[T4:%[0-9]+]]:_(s8) = G_SUB [[T3]], {{.*}}
     G_BR %bb.3.exit
   bb.3.exit:
   ; CHECK: bb.3.exit:
-    %8:_(s8) = G_PHI %6:_(s8), %bb.1, %7:_(s8), %bb.2
+    %9:_(s8) = G_PHI %6:_(s8), %bb.1, %8:_(s8), %bb.2
     ; CHECK: [[T5:%[0-9]+]]:_(s8) = G_PHI [[T2]](s8), %bb.1, [[T4]](s8)
-    %9:_(s32) = G_ZEXT %8
+    %10:_(s32) = G_SEXT %2
+    %11:_(s32) = G_ZEXT %9
     ; CHECK: [[T6:%[0-9]+]]:_(s32) = G_ZEXT [[T5]](s8)
     ; CHECK: $w0 = COPY [[T0]](s32)
     ; CHECK: $w1 = COPY [[T6]](s32)
-    $w0 = COPY %3
-    $w1 = COPY %9
+    $w0 = COPY %10
+    $w1 = COPY %11
+# CHECK-WORKLIST-LABEL: Generic MI Combiner for: sink_to_phi_nondominating
+# CHECK-WORKLIST:       Try combining [[IN0:%[0-9]+]]:_(s8) = G_LOAD [[IN1:%[0-9]+]]:_(p0) :: (load 1 from %ir.addr)
+# CHECK-WORKLIST:       Preferred use is: [[IN2:%[0-9]+]]:_(s32) = G_SEXT [[IN0]]:_(s8)
+# CHECK-WORKLIST-DAG:   Changing: [[IN0]]:_(s8) = G_LOAD [[IN1]]:_(p0) :: (load 1 from %ir.addr)
+# CHECK-WORKLIST-DAG:   Creating: G_TRUNC
+# CHECK-WORKLIST-DAG:   Changing: [[IN3:%[0-9]+]]:_(s8) = G_ADD [[IN0]]:_, [[IN4:%[0-9]+]]:_
+# CHECK-WORKLIST-DAG:   Changed: [[IN3]]:_(s8) = G_ADD [[OUT1:%[0-9]+]]:_, [[IN4]]:_
+# CHECK-WORKLIST-DAG:   Creating: G_TRUNC
+# CHECK-WORKLIST-DAG:   Changing: [[IN5:%[0-9]+]]:_(s8) = G_SUB [[IN0]]:_, [[IN6:%[0-9]+]]:_
+# CHECK-WORKLIST-DAG:   Changed: [[IN5]]:_(s8) = G_SUB [[OUT2:%[0-9]+]]:_, [[IN6]]:_
+# CHECK-WORKLIST-DAG:   Erased: [[IN2]]:_(s32) = G_SEXT [[IN0]]:_(s8)
+# CHECK-WORKLIST-DAG:   Changed: [[IN2]]:_(s32) = G_SEXTLOAD [[IN1]]:_(p0) :: (load 1 from %ir.addr)
+# CHECK-WORKLIST-DAG:   Created: [[OUT1]]:_(s8) = G_TRUNC [[IN2]]:_(s32)
+# CHECK-WORKLIST-DAG:   Created: [[OUT2]]:_(s8) = G_TRUNC [[IN2]]:_(s32)
+# CHECK-WORKLIST:       Try combining
 ...
 
 ---
 name:            sink_to_phi_emptyblock
 # CHECK-LABEL: name: sink_to_phi_emptyblock
 tracksRegLiveness: true
 body: |
   bb.0.entry:

unittests/CodeGen/GlobalISel/LegalizerHelperTest.cpp

 //===- PatternMatchTest.cpp -----------------------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "LegalizerHelperTest.h"
 
 namespace {
 
 class DummyGISelObserver : public GISelChangeObserver {
 public:
-  void changingInstr(MachineInstr &MI) override {}
-  void changedInstr(MachineInstr &MI) override {}
-  void createdInstr(MachineInstr &MI) override {}
-  void erasingInstr(MachineInstr &MI) override {}
+  void changingInstr(const MachineInstr &MI) override {}
+  void changedInstr(const MachineInstr &MI) override {}
+  void createdInstr(const MachineInstr &MI) override {}
+  void erasingInstr(const MachineInstr &MI) override {}
 };
 
 // Test CTTZ expansion when CTTZ_ZERO_UNDEF is legal or custom,
 // in which case it becomes CTTZ_ZERO_UNDEF with select.
 TEST_F(LegalizerHelperTest, LowerBitCountingCTTZ0) {
   if (!TM)
     return;